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 07. 02. 2012 18:41
Grafy, příklady
Ahoj, řeším následující příklady a byl bych rád kdyby mi někdo pomohl.
1.
Nakreslete graf, ktery lze nakreslit jednim tahem, ale neni eulerovsky. Dale rozhodnete, zda kazdy rovinny graf se sudym poctem vrcholu a hran lze uz nutne nakreslit jednm tahem. Vsechna sva tvrzen a rozhodnut radne dokazte.
- K té první větě: To tedy znamená, že máme najít takový graf, který NEOBSAHUJE eulerovský tah, ale přitom lze nakreslit jedním tahem. Myslím, že takový graf neexistuje, ale nevím jak to dokázat. Druhá věta podle mě určitě neplatí, k vyvrácení jsem nalezl protipříklad. Je to tak?
2.
Necht' n je prirozene cslo. Rozhodnete, pro ktera n existuje graf G s n vrcholy a k nemu dualni graf G' takovy, ze je isomorfni s grafem G. Napiste sva pozorovani do tvrzeni, jehoz platnost radne zduvodnete.
- Tady celkem tápu. Mám pár poznámek, ale potřeboval bych postrčit.
Díky
Offline
#2 07. 02. 2012 22:48
Re: Grafy, příklady
Nevim jak presne mate definovany Eulerovsky graf, obcas se ty definice lisej (znam asi 3). Kazdopadne obas muze byt finta treba v tom, ze nakreslis graf jenom s jednim vrcholem a zadnou hranou. Podivej se sem pro inspiraci a porovnej s vasi definici: http://mathworld.wolfram.com/EulerianGraph.html
2)opet mam trochu probelm s definic. Je dualni graf ten, ktery ma stejne vrcholy, ale hrany ma jen tam kde puvodni graf ne a naopak? V anglictine se totiz tomuhle rika komplementarni a dualni je neco z teorie rovinych grafu - kdyztak se podivej na wiki
Jestli je to to, co si myslim, tak bych postupoval takhle:
uplny graf na n vrcholech ma n(n-1)/2 hran. Ty budes muset mit stejny pocet hran v puvodnim i v dualnim grafu, tedy n(n-1)/4 v kazdem. Tzn potrebujs aby bud n nebo n-1 bylo delitelne 4mi beze zbytku. Mozna v tom bude neco vic, ale takhle nejak bych uvazoval
Offline
#3 07. 02. 2012 23:42
Re: Grafy, příklady
↑ Alkac:
Graf je eulerovský, když má aspoň jeden uzavřený eulerovský tah. Uzavřený eulerovský tah je sled (v0,e1,v1....e(m-1),v(m-1),e(m),v0) v němž se každá hrana vyskytuje právě jednou.
2) je na mysli tato definice http://cs.wikipedia.org/wiki/Du%C3%A1ln%C3%AD_graf . K tomu: napadlo mě, že (jak už si i napsal) původní i duální graf bude mít stejný počet hran. Dále aby byl zachován počet vrcholů, tak musí mít původní graf stejný počet vrcholů jako stěn (stěny budou v duálním grafu vrcholy a je nutné, aby se počet vrcholů zachoval vzhledem k isomorfismu). Potom by šlo z Eulerovy věty nahlédnout, že: V-E+S=2 => 2V-E=2 => E=2V-2. Mám představu, jak by takové grafy měli vypadat (n-úhelník s vrcholem uprostřed). Takže to bude zřejmě platit pro všechna n>=3. Teď to ještě formálně dotáhnout.
Offline
#4 07. 02. 2012 23:57
Re: Grafy, příklady
1) pri tehle definici staci nakreslit dva vrcholy a spojit je hranou, to je nakresleni jednim tahem, ale nema to Eulerovsky tah. Dale nakreslim 4 vrcholy a spojim 1-2 a 3-4. To ma sudy pocet vrcholy i hran, ale nejde to nakreslit jednim tahem.
2)aha, takze me se plete dualni a komplementarni....ale tvoje reseni se mi zda dobre
Offline