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 29. 12. 2013 19:01
- Sandrastrelcova
- Příspěvky: 36
- Škola: VŠE
- Reputace: 0
Důkaz vyváženého grafu
Ahoj, mám tady následující problémek. Dokaž že pokud má graf všechny stupně sudé tak existuje vyvážená orientace. Což žnamená že vstupní stupeň vrcholu se rovná tomu výstupnímu.
Uvažovala jsem že bych na to šla sporem, a zvolila všechny stupně liché a pro ty dokázala že orientace není vyvážená, jen nemůžu přijít na to jak, asi by to chtělo jít trošku jinak. Jako třeba přidat dva vrcholy lichého stupně a dokázat že po přidání už není vyvážený? Děkuji za pomoc
Offline
#2 29. 12. 2013 21:26
Re: Důkaz vyváženého grafu
↑ Sandrastrelcova:Zaprvé: Opak "všechny stupně sudé" není "všechny stupně liché", ale alespoň jeden lichý stupeň.
Zadruhé, doporučuji zcela jiný (konstruktivní) postup. Nápověda: co říká Eulerova věta? Jak zní a jak ji můžeme využít?
Offline
#3 30. 12. 2013 22:23
- Sandrastrelcova
- Příspěvky: 36
- Škola: VŠE
- Reputace: 0
Re: Důkaz vyváženého grafu
↑ petrkovar:: Eulerova hm..graf G je Eulerovská právě tehdy když je souvislý, a každý vrchol G má sudý stupeň, nebo graf je eulerovský když obsahuje eulerovský tah, v kterém se každá hrana vyskytuje právě jednou, a každý vrchol alespoň jednou. Ale jak to aplikovat, jestli je myšleno tohle opravdu netuším..
Offline
#4 04. 01. 2014 11:50
Re: Důkaz vyváženého grafu
↑ Sandrastrelcova:Ano, tak je to myšleno.
Když máme ten tah (uzavřený), tak bychom jej mohli nějak využít pro tu vyváženou orientaci. Jak?
Offline