Matematické Fórum

nordec · 14. 05. 2009 20:01

Ahoj, můžu poprosit o kontrolu mých odpovědí?

2. Rozhodněte, zda
(a) každý graf obsahující hamiltonovskou kružnici je vrcholově 2-souvislý. ANO

(b) každý graf obsahující uzavřený eulerovský tah je vrcholově 2-souvislý. NE

(c) každý graf obsahující uzavřený eulerovský tah je hranově 2-souvislý. ANO

4. Rozhodněte, zda každý graf na n >= 3 vrcholech, z nichž každý má stupeň alespoň d, kde d >= (n − 1)/2, je
(a) hranově d-souvislý. NE

(b) vrcholově d-souvislý. NE

5. Pro každé sudé n >= 4 najděte graf G na n vrcholech, které mají stupně alespoň d = (n − 2)/2, a přitom G není hranově d-souvislý.

Takový graf G má vrcholy (v1,v2,v3,....,vn). Pro n > 4 musí existovat mezi v2 a v3 max. jedna hrana, ostatní hrany doplníme, aby byla splněna podmínka, že stupně vrcholů jsou alespoň d. Pro n = 4 mezi v2 a v3 neexistuje hrana, spojeny jednou hranou jsou jen v1 s v2 a v3 s v4.

Kondr · 14. 05. 2009 21:35

4a) řekněme, že je graf není vrcholově d-souvislý, tedy že stačí odebrat méně než d hran a graf se rozpadne na komponenty velikostí k a (n-k), kde k<=n-k. Zůstane v něm nejvýše k*(k-1) hran v první komponentě a (n-k)d ve druhé, celkem nd-(d+1-k)k hran. Protože je k mezi 1 a d (a daná funkce je maximální v krajních bodech tohoto intervalu), je tato hodnota vždy alespoň nd-d. Před odebráním hran bylo v grafu nejvýše nd-1 hran, spor.

Jinak s tím souhlasím, akorát u pětky to nějak nevidím, proč by to mělo platit. Vlastně ani nevím, jak ten tvůj graf vypadá. Když zní zadání "sestrojte", měl by být popsán konkrétněji.

nordec · 15. 05. 2009 13:50

To 4a) si stále myslím, že NE, ale je možné, že špatně chápu něco v zadání. Proto zde názorně vysvětluji, jak jsem postupoval při řešení 4a) a 5). V 5) se vyskytla jedna nenapsaná myšlenka, bez níž si to opravdu nejde představit.

U tvrzení 4a) "...zda každý graf..." stačí najít jeden protipříklad aby neplatilo, např.:

zde n=5 a splňuje podmínku d>=2. Přitom není už hranově 2-souvislý (stačí odebrat červenou hranu a rozpadne se), takže není ani více-souvislý.

U 5) stačí aby mezi libovolnými dvěma vrcholy existovala jen jedna hrana "e", tak bude zaručeno pro d>=2, že graf nebude hranově d-souvislý (vždy stačí odebrat tu jednu hranu e, aby se graf rozpadl). Jen jsem to předtím popsal konkrétněji, že mezi v2 a v3 je právě hrana e.
Ostatní hrany a vrcholy (patří do množiny M1 nebo M2) mohou být libovolně, jen další hrany nesmí být mezi dvěma vrcholy spojenými e, a všechny vrcholy musí mít stupeň alespoň d.
Teď až z obrázku vidím další podmínku, kterou jsem si myslel, ale nenapsal, totiž, že žádná hrana nesmí vést mezi M1 a M2, jinak by to celé nemělo smysl.
To bylo pro n>4.
Pro n=4 je d=1, aby graf nebyl 1-souvislý (tj. po obebrání 0 hran nebude souvislý), nesmí být souvislý vůbec.

Kondr · 15. 05. 2009 16:13

↑ nordec:U 4a) je problém v tom, že mezi každými dvěma vrcholy může vést jen jedna hrana (jinak nemluvíme o grafuale multigrafu), proto tvůj protipříklad nefunguje. Možná efektivnější než hledat protipříklad jen tak bude projít si můj důkaz a najít protipříklad k něčemu v tom důkazu. Doufám ale, že v důkazu chyba není ;)

Ad 5: teď ještě popsat, jak vypadají M1 a M2. Podle mě to pro n sudé musí být úplné grafy na d+1 vrcholech, pro n liché to vyjde podobně. Nemám teď moc času, zkus to domyslet.

nordec · 28. 05. 2009 14:22

↑ Kondr:Pokud mezi 2 vrcholy nevede násobná hrana pak s 4a) souhlasím.

U 5) původně M1 obsahovala vlastně 1 vrchol (v1) a M2 všechny od v4 po vn . Ale v M1 by vznikla vícenásobná hrana. Tvé řešení grafu je asi nejlepší možné. Podle zadání je n sudé, takže ještě velikost M1 = velikost M2.

Díky za objasnění, s těmi multigrafy by se hrany naskládaly kamkoli a příklad na to by se dal vyřešit triviálně, to by bylo moc jednoduché.

Matematické Fórum

#1 14. 05. 2009 20:01

Souvislost grafu

#2 14. 05. 2009 21:35

Re: Souvislost grafu

#3 15. 05. 2009 13:50

Re: Souvislost grafu

#4 15. 05. 2009 16:13

Re: Souvislost grafu

#5 28. 05. 2009 14:22

Re: Souvislost grafu

Zápatí