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 08. 03. 2010 14:05
Graf - nakreslení pomocí tahů
Zdravím, je zadáno toto:
Rozhodněte, zda lze každý souvislý graf G, který má 2k vrcholů lichého stupně a ostatní sudého, nakreslit pomocí k disjunktních ne nutně uzavřených tahů.
Řekl bych, že tvrzení neplatí, protože uvážíme-li kružnici na n vrcholech, máme nula vrcholů lichého stupně, tedy 2k=0. Potom k=0 a tento graf má jít nakreslit nula tahy, jenže on jde jedním.
Je to správná úvaha, nebo je v tom nějaký háček, zdá se mi to až moc jednoduché. Předem díky.
Offline
#2 08. 03. 2010 14:20 — Editoval musixx (08. 03. 2010 14:25)
Re: Graf - nakreslení pomocí tahů
S tím k=0 máš pravdu, ale přidejme podmínku, že alespoň jeden vrchol lichého stupně existuje. Je to aplikace na větu, že souvislý graf jde nakreslit jedním tahem právě tehdy, když obsahuje jen uzly sudého stupně, resp. navíc právě dva uzly lichého stupně (a pak je cesta neuzavřená a začíná a končí v nich).
EDIT: Zbývá domyslet, jak se graf po odebrání jedné takové cesty změní, resp. ne každá taková cesta je použitelná (stejně jako v originální větě -- takový ten populární domeček jedním tahem také mohu začít kreslit nešikovně, a proto nedokončit).
Offline
#3 08. 03. 2010 15:25
Re: Graf - nakreslení pomocí tahů
U všech vrcholů, kterými procházela odebraná cesta, se sníží jejich stupeň o 2, pokud to byl list, tak o 1. Nejlepší je asi odebírat cesty tak, aby se graf nerozpadl na komponenty obsahující ještě nějaké hrany, to by počet cest zbytečně zvýšilo.
Když budeme cesty vybírat šikovně, budou se vrcholy lichého stupně alespoň tři chovat jako ty sudého, dokud se z nich nestanou listy. V průběhu odebírání vznikne celkem tolik listů, kolik je vrcholů lichého stupně (2k). A každá cesta může obsahovat max. 2 listy, proto jde (pro k>0) nakreslit graf k tahy?
Offline
#4 09. 03. 2010 21:07
Re: Graf - nakreslení pomocí tahů
↑ nordec:Existuje legantnější zdůvodnění. nápověda:
Předpokládejme, že umíme najít uzavřený tah v souvislém grafu se všemi vrcholy sudého stupně (eulerovský graf).
Do našeho grafu něco přidáme (co?) a dostaneme eulerovský graf. Potom zase to něco odebereme a z jednoho uzavřeného tahu dostaneme rázem hledané řešení.
Offline
#7 12. 03. 2010 19:54
Re: Graf - nakreslení pomocí tahů
No, když bude přidaných všech k hran mezi vrcholy lichého stupně, tak podle věty uvedené výše víme, že tento graf nakreslíme jedním tahem a pokud z něj odebereme hranu, také půjde nakreslit jedním tahem... Jak to elegantněji dokázat je mi stále záhadou.
Offline
#8 12. 03. 2010 21:06
Re: Graf - nakreslení pomocí tahů
↑ nordec:Neporozuměl jsi námitce. Není zaručeno, že do grafu s 2k vrcholy lichého stupně půjde přidat hrany mezi vrcholy lichého stupně. Co když už tam hrany jsou? Například v kompletním grafu 
je šest vrcholů lichého stupně 5, ale žádnou hranu mezi ně přidat nemůžeme, protože už mezi těmito vrcholy všechny hrany jsou. Samozřejmě jde nakreslit třemi otevřenými tahy. Jak to dokázat? Co přidáme, aby vznikl sudý graf?
Offline