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
! 04. 11. 2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17. 01. 2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17. 01. 2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
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)

loplpo
Zelenáč
Příspěvky: 8
Reputace:   
 

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)

jarrro
Příspěvky: 4765
Škola: UMB BB Matematická analýza
Pozice: doktorand
Reputace:   268 
Web
 

Re: Podgrafy v kružincovém grafu

1) Dobre, ale jednoduchšie je $2^5$ (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

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson