Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 12. 10. 2017 21:59 — Editoval loplpo (13. 10. 2017 11:17)
Podgrafy v kružincovém grafu
Pro graf C5 (kružnice s 5 vrcholy) určete
1) počet podgrafů na pěti vrcholech
2) počet indukovaných podgrafů na libovolném počtu vrcholů
3) počet neizomorfních podgrafů na libovolném počtu vrcholů.
Jedničku jsem zkoušel následující úvahou:
- podgraf s 5 vrcholy a žádnou hranou: jenom 1
- s 1 hranou: 5 (jelikož C5 kružnice má 5 hran)
- se 2 hranami: 10 (5*4 / 2 - dělím 2 jelikož na pořadí výběru hran nezáleží)
- se 3 hranami: 10 (5*4*3 / 3! - dělim 3 faktoriálem, na pořadí nezáleží)
- se 4 hranami: 5 (5*4*3*2 / 4!)
- s 5 hranami: 1
Dohromady 1 + 5 + 10 + 10 + 5 + 1 = 32 podgrafů. Je ten výsledek a/nebo postup správně?
U druhého a třetího úkolu si nevím rady.
Předem děkuji za odpověď.
Offline
#2 13. 10. 2017 14:13 — Editoval jarrro (13. 10. 2017 14:14)
Re: Podgrafy v kružincovém grafu
1) Dobre, ale jednoduchšie je 
(každá hrana má dve možnosti (byť alebo nebyť v podgrafe) resp. Každá podmnožina množiny hrán určuje jeden podgraf na 5 vrcholoch a naopak.
2) Indukovaný podgraf je jednoznačne určený podmnožinou množiny vrcholov
3) na 0 vrcholoch 1 graf (prázdny)
na 1 vrchole je 1 graf (vrchol)
na 2 vrcholoch sú 2 grafy (2 vrcholy,2-cesta)
na 3 vrcholoch 3 ( 3 vrcholy, 2-cesta a vrchol, 3-cesta)
na 4 vrcholoch 5 (4 vrcholy, 2-cesta a 2 vrcholy, 3-cesta a vrchol, 2 2-cesty, 4-cesta)
na 5 vrcholoch 8 (5 vrcholov, 2-cesta a 3 vrcholy, 3-cesta a 2 vrcholy, 2 2-cesty a vrchol, 4-cesta a vrchol, 3-cesta a 2cesta, 5-cesta, 5-kružnica)
Snáď som na nič nezabudol
MATH IS THE BEST!!!
Offline