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
#2 29. 12. 2013 21:17
Re: eulerovsky graf
↑ rama27:Myslím, že tvrzení neplatí. Stačí, aby graf nebyl souvislý a skládal se ze dvou vrcholově (a tedy i hranově) disjunktních cyklů, potom na hranově disjunktní cykly rozložit jde a přitom není eulerovský.
Leda že by byl i souvislý. Potom doporučuji použít Eulerovu větu. Jak zní?
Offline
#3 30. 12. 2013 11:56
Re: eulerovsky graf
Eulerových vět je několik :) Ale myslíš asi tu, která říká, že graf je eulerovský, právě když je souvislý a každý jeho stupeň je sudý. Jak dokáži, že když stupně jsou sudé, když graf lze rozložit na hranově disjunktní cykly? Když si to kreslím, tak to vidím, ale jak to dokázat? Dík
Offline
#4 04. 01. 2014 11:53
Re: eulerovsky graf
↑ rama27:Indukcí vzhledem k počtu hran. Základní krok indukce ponechám na Tobě a v indukčním kroku bude nutno něco předpokládat, co?
Potom najdeme nějaký cyklu, odebereme jeho hrany z grafu a využijeme indukční předpoklad...
Jak bude vypadat základní krok?
Jak idnukční předpoklad?
Offline
#5 04. 01. 2014 19:05
Re: eulerovsky graf
↑ rama27:Ještě doplním, že v původním zadání se mělo ukázat něco jiného: že když jde (asi souvislý) graf rozložit na disjunktní cykly, tak je eulerovský. Tady se využije Eulerova věta. Stačí si uvědomit, jak to bude se stupni vrcholů.
V pozdějším příspěvku se řeší opačná implikace: Má-li graf všechny vrcholy sudého stupně, půjde jej rozložit na cykly. Lze využít indukci, jak jsem psal výše, případně jednu z Petersenových vět, které se berou jen v některých kurzech.
Offline