#1 03. 12. 2015 15:01 — Editoval jelena (03. 12. 2015 16:13)
Teorie grafů
Edit: aktuální projekt 3.3 - viz pravidla pro diskusi.
Mějme souvislý graf G se stupni {x, 4, 3, 2, 2, 2, 2, 1, 1}. Určete, jakých hodnot může číslo x nabývat, aby graf G obsahoval alespoň 3 hranově disjunktní cykly (pokud v grafu existují cykly, které nejsou hranově disjunktní, nevadí). Všechny nalezené hodnoty x zapište jako x ∈ {x1, x2, . . . , xn}. Vaši odpověď pečlivě zdůvodněte (například výpočtem) a nakreslete alespoň dva různé grafy s danými stupňovými posloupnostmi, každý pro jinou hodnotu x.
Zatím jsem si určil, že x musí být liché číslo <= 7
pro nějaká x jsem si už grafy nakreslil a 3 hranově disjunktní cykly našel, ale pouze při té konstrukci.
Z čeho jsem jelen je: odpověď pečlivě zdůvodněte (například výpočtem)
Mohl by mě někdo prosím jednou větou nasměrovat, jak se dá toto ukázat výpočtem?
Offline
#2 03. 12. 2015 15:41 — Editoval gygabyte (03. 12. 2015 18:09)
Re: Teorie grafů
Aby byly v souvislem grafu cykly, musí mít počet hran >= počet vrcholů. nejmenší cyklus má 3 hrany. když má můj graf 9 vrcholů, stačí tedy aby byl počet hran 8 + 3x3 (cykly) + 2 hrany navíc jako "oddělovače" aby se zajistilo, že budou hranově disjunktní?
Offline
