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
Stránky: 1
- Hlavní strana
- » Vysoká škola: úvod do studia
- » teorie grafů - kreslení jedním tahem (TOTO TÉMA JE VYŘEŠENÉ)
#1 14. 05. 2011 13:34
teorie grafů - kreslení jedním tahem
Mám úkol: Je dán souvislý graf, v němž je k uzlů lichého stupně, určete nejmenší počet tahů, kterými ho lze nakreslit. ??
nevím si s tím rady, vím, že graflze nakreslit jedním tahme, práve když je souvislý a obsahuje buď právě dva a nebo žádný uzel lichého stupně.
ale jak mam urcit nejmensi pocet tahu?
Offline
- (téma jako vyřešené označil(a) ajucha)
#2 14. 05. 2011 14:07
Re: teorie grafů - kreslení jedním tahem
Už starý dobrý Euler věděl, že jedním tahem lze nakreslit graf, který má maximálně 2 uzly lichého stupně.
(Pokud jsou2 pak v jednom začneš a ve druhém skončíš)
Tak tedy poděl počet uzlů lichého stupně 2 a pokud to bude celé číslo tak bude i počtem potřebých tahů (pro nulový počet uzlů lichého stupně to bude samozřejmě 1 tah)
Offline
#4 14. 05. 2011 14:39
- check_drummer
- Příspěvky: 5559
- Reputace: 106
Re: teorie grafů - kreslení jedním tahem
↑ ajucha:
Je nutno definovat co se myslí tahem - tah není totéž co hrana.
"Máte úhel beta." "No to nemám."
Offline
#5 14. 05. 2011 14:48
Re: teorie grafů - kreslení jedním tahem
↑ check_drummer:
pravda vlastne, nejak jsme se do toho zapomtala...
a jak pises, ze: poděl počet uzlů lichého stupně 2 a pokud to bude celé číslo tak bude i počtem potřebých tahů
Tak co kdyz to nebude cele cislo?
Offline
#6 14. 05. 2011 14:53
- check_drummer
- Příspěvky: 5559
- Reputace: 106
Re: teorie grafů - kreslení jedním tahem
↑ Honzc:
Asi nejlépe je to vidět tak, že spojíme libovolné dva vrcholy s lichým stupněm pomocnou hranou, tak aby z každého vrcholu lichého stupně vycházela jedna pomocná hrana. Pak dle eulerovského tahu sestrojíme jeden tah a odebráním pomocných hran se graf rozpadne na nejvýše k tahů, kde 2k je počet vrcholů s lichým stupněm. Tedy k tahů opravdu stačí.
Že je to nutné, je zřejmé z toho, že každý tah obsahuje nejvýše dva vrcholy s lichým stupněm (koncové vrcholy tahu).
Honzc napsal(a):
Tak tedy poděl počet uzlů lichého stupně 2 a pokud to bude celé číslo ...
To bude vždy.
"Máte úhel beta." "No to nemám."
Offline
#7 14. 05. 2011 14:54
- check_drummer
- Příspěvky: 5559
- Reputace: 106
Re: teorie grafů - kreslení jedním tahem
ajucha napsal(a):
↑ check_drummer:
a jak pises, ze: poděl počet uzlů lichého stupně 2 a pokud to bude celé číslo ..
To jsem nepsal já. :-)
"Máte úhel beta." "No to nemám."
Offline
#8 15. 05. 2011 20:46
Re: teorie grafů - kreslení jedním tahem
↑ check_drummer:Přidáváním hran se může snadno stát, že dostaneme multigraf (s násobnými hranami). Třeba takový graf 
obsahuje 6 vrcholů lichého stupně a přidat hranu, aniž bychom dostali násobnou hranu, už nejde. Obvyklý trik spočívá v přidání (jediného) pomocného vrcholu a *patřičného* počtu *správných* hran.
Ne že by tvrzení pro multigrafy neplatilo, ale pokud se pracuje jen s grafy...
Offline
#9 15. 05. 2011 22:05
- check_drummer
- Příspěvky: 5559
- Reputace: 106
Re: teorie grafů - kreslení jedním tahem
↑ petrkovar:
Děkuji za postřeh. Ovšem bylo by pak vhodné (abychom co nejvíce dodrželi mnou navržený postup) místo hrany xy přidat vrcholy x',y' a hrany xx',x'y',y'y. Tedy pomocných vrcholů bude stejně jako je vrcholů lichého stupně.
"Máte úhel beta." "No to nemám."
Offline
#10 16. 05. 2011 09:23
Re: teorie grafů - kreslení jedním tahem
↑ check_drummer:Ano, to je samozřejmě možné.
Na druhou stranu, protože 
je sudé číslo, stačí přidat jediný nový vrchol a nových hran.
Offline
#11 16. 05. 2011 09:56
Re: teorie grafů - kreslení jedním tahem
↑ check_drummer:
Já samozřejmě vím, že počet "lichých" vrcholů je vždy sudé číslo (pokud v tomto případě i nulu započteme mezi sudá)
To přeci plyne z toho, že každá hrana má dva vrcholy lichého stupně. Tedy při přidání jedné hrany můžeme dostat pouze tyto možnosti.
1.Snížíme počet "lichých" vrcholů o 2.
2.Zvýšíme počet "lichých" vrcholů o 2.
3.Počet "lichých" vrcholů zůstane stejný.
Tedy počet "lichých" vrcholů je vždy sudé číslo (nebo 0)
Offline
#12 16. 05. 2011 20:06
- check_drummer
- Příspěvky: 5559
- Reputace: 106
Re: teorie grafů - kreslení jedním tahem
↑ Honzc:
Je to tak, jen mě zmátla ta poznámka - ... a pokud to bude celé číslo ... kterou jsem chápal tak, že to dle Tvých ne vždy musí nastat.
"Máte úhel beta." "No to nemám."
Offline
Stránky: 1
- Hlavní strana
- » Vysoká škola: úvod do studia
- » teorie grafů - kreslení jedním tahem (TOTO TÉMA JE VYŘEŠENÉ)