Matematické Fórum

hmyzak · 17. 11. 2009 18:01

Zdravím, mám tuto úlohu:

Trianglie je malá ostrovní země, ve které žádná cesta nekončí jinak, než křižovatkou ve tvaru Y. Mladý princ se vydá na cesty po ostrově. Nasedne na koně a chystá se odjet. Když projíždí cestou pod okny paláce, volá na něj královna z balkónu: "Ale princi, jak najdeš cestu zpět do paláce?" On ji odpověděl: "Neboj matko, vždy na každé druhé křižovatce odbočím vpravo a jinak budu odbočovat vlevo. Takto jistě dříve nebo později přijedu zpět před palác." Měl princ pravdu?
Návod: Úlohu namodelujte grafem, který je konečný. Dále si všimněte, že budete-li nějaký sled v~grafu stále prodlužovat, tak dříve nebo později se musí některé vrcholy nebo hrany zopakovat.

Podle mě, to není možné, namodeloval jsem si graf z hexů jakožto poskládaných z Y a pořád od hradu jako by utíkám, buď vodorovně nebo po diagonále (záleží z jakého bodu princ vyjede), návod zase hovoří o konečném grafu, takže to asi vyjde, jen nevím jak, kdyžtak děkuji za naťuknutí

jelena · 19. 11. 2009 08:50

↑ hmyzak:

Zdravím,

řekla bych, že pan učitel umístil nápovědu hned do 1. slova zadání (je to jen nápad).

-------------
Příčin bylo více. K poklesu tržeb přispělo mimo jiné počasí, které letos více než loni odpovídalo běžnému charakteru zimního období, a také přesun Velikonoc z dubna na březen.

hmyzak · 19. 11. 2009 20:54

↑ jelena:

Taky jsem o tom přemýšlel, ale z trojúhelníků to s křižovatkama Y prostě poskládat nejde :-)

Wotton · 19. 11. 2009 21:40

Nevým jestli to pomůže, ale zkus prohodit hrany a vrcholy. To je celkem oblíbený trik v grafech. Tim ti vznikne jiny graf, ktery bude taky roviny, a navic uz tam budeš opravdu mit ty trojůhelníky.

jelena · 20. 11. 2009 00:15

↑ hmyzak:

tak nějak bych to viděla atd. otočeno a spojováno ve spravných úhlech, ale je to vyrobeno v tomto editoru. To je malo trojuhelnikové?

-----
Nejvýznamnější přepravovanou komoditní skupinou byly v hodnoceném období surové nezpracované nerosty a písek.

gladiator01

Tady se řeší to samé http://forum.matweb.cz/viewtopic.php?id=11903 , třeba ti pomůže Kondrova odpověď.

edit: odkaz nefunguje

dreek · 29. 11. 2009 21:54 — Editoval dreek (29. 11. 2009 21:55)

viz. odkaz
Špatný požadavek. Objekt, který jste požadovali, je nesprávný nebo starý. :(

Prosím o zopakování odpovědi ;) děkuju

gladiator01

↑ dreek:
On to asi někdo smazal, já to nemůžu najít. Třeba Kondr zopakuje co řekl.

jelena · 29. 11. 2009 22:14 — Editoval jelena (29. 11. 2009 22:43)

Takový uživatel zbyněk smazal odkazované téma. V 2. příspěvku bylo doporučení od kolegy Kondra:

1) počet hran je konečný, bude-li bloudit dostatečně dlouho, projde tutéž hranu stejným směrem
2) když podruhé (zde bylo, myslím editováno na "potřetí") projde hranu stejným směrem, znamená to že se od té doby bude pohybovat po kružnici.
3) ze střídavého zatáčení má ta kružnice sudou délku
4) proto se na kružnici nemohl napojit, pohybuje se po ní celou dobu
5) palác leží na kružnici => zase se do něj vratí

Snad kolega Kondr doplní, co tam bylo.

Tak nějak to bylo.

Tomu nerozumím, co sleduje: http://forum.matweb.cz/viewtopic.php?id=11902

Kondr · 30. 11. 2009 00:47

Pro náhodné kolemjdoucí: bylo to trochu jinak, své vysvětlení jsem uvedl zde: http://forum.matweb.cz/viewtopic.php?pid=80198#p80198

↑ jelena:Díky za obdivuhodnou všímavost.

chlebo · 01. 12. 2009 10:41

↑ jelena:
Takze graf bude cyklicky?
Prosim o potrobnejsie instrukcie. Vecsina prispevkov je zmazana

jelena · 01. 12. 2009 10:58

↑ chlebo:

"na bani berem cyklus grafu = kružnice ;-)" (c).

Doporučuji podrobně číst pokyny kolegy Kondra (v příspěvku č. 9 je zachraněný text kolegy ze "smazaného tématu") a konzultovat to s kolegou). Autoritu srdečně zdravím.

Kondr · 01. 12. 2009 11:09

↑ chlebo:Každý les má listy. Acyklický graf = les. Může mít triangle listy? Může být acyklická?

Jinak zkuste kouknout na moje hinty a napsat nějakou ideu, jak by se daly dokázat. Třeba si vzpomenout na Dirichletův princip. Fakt se mi nechce rozepisovat triviality, které všichni chápeme, radši bych jen dovysvětlil to, co není jasné.

osel · 02. 12. 2009 20:17

Dobrý den, chtěl bych Vás poprosit o odpověď, jak byste resili tento příklad aby byl vyporesen správně, pokud by se Vám to nechtelo zde vypracovavat, tak by stacil jen nakreslit graf ;-) Děkuji za pripadnou odpoved. Vazim si toho.

Kondr · 03. 12. 2009 00:43

↑ osel:Vypracovávat a šířit se mi ho nechce, zvlášť, když jsem byl panem Kovářem informován, že počet tupých opisovačů výrazně převyšuje počet těch, kteří si návod přečtou, pochopí a samostatně zpracují.

Nakreslení konkrétního grafu ti nepomůže -- možných tvarů trianglie je nekonečně mnoho. Zkus kouknout na moje hinty a nějak se k nim vyjádřit, ať vím, jakým směrem radit. Znáš Dirichletův princip?

elnino · 03. 12. 2009 10:28

↑ Kondr:
Nakreslit to vie aj male decko cest vinimkam, horsie je to vysvetlit ako som na to prisiel. Normalne....ceruzkou

elnino · 03. 12. 2009 10:50

Tak tu je taka mensia napoveda, musis mat parny-sudy pocet vrcholov, Y znamena ze bude mat 3 hrany. Cervenou je znazornene ako by mohol ist.

Kondr · 03. 12. 2009 11:14

Každý možný pohyb prince po jedné hraně umíme popsat trojicí $(x,y,p)$ , kde x je počáteční vrchol, y koncový vrchol, p je 0, pokud se jedná o jeho sudý tah a p je 1, jde-li o lichý. Nechť f je zobrazení, které trojici $(x,y,p)$ přiřadí trojici $(y,z,1-p)$ tak, že po tahu $(x,y,p)$ provede princ tah $(y,z,1-p)$ . Vidíme, že f je bijekce na množině všech možných tahů. Každá bijekce je součinem cyklů, takže jsme hotovi.

osel · 03. 12. 2009 11:40

A nemohl bych pouzit Petersenuv graf? Take jsou zde krizovatky ve tvaru Y a pocet vrcholu je take sudy.

Kondr · 03. 12. 2009 11:54

↑ osel:Ty to potřebuješ pro všechny grafy, ne pro jeden konkrétní.

osel · 03. 12. 2009 11:58

↑ Kondr: Aha aha, takze neco na zpusob obrazku, ktery tu dal elnino, asi ze? A ten tvuj postup co si tady psal je vse co staci dokazat?

elnino · 03. 12. 2009 12:44 — Editoval elnino (03. 12. 2009 13:20)

↑ Kondr:
Tak ako to mam dokazat pre lichy pocet vrcholov ked mi bude chybat este jedna hrana.

Kondr · 03. 12. 2009 12:50

↑ osel:Stačí dokázat to, co jsem nastínil v citovaném příspěvku (↑ jelena:) a formalizoval (↑ Kondr:).

↑ elnino:Možná jsem se špatně vyjádřil: ne pro všechny grafy celkově, ale pro všechny grafy splňující podmínku pro trianglii (Petersonův graf má 10 vrcholů, pokud vím, Trianglie může mít obecný počet).

petrkovar · 03. 12. 2009 14:17

V grafu reprezentujícím Trianglii nemůže být libovolný počet vrcholů, ale vždy sudý. To plyne z věty, které říkáme Věta 1.1. (Princip sudosti). Na správné řešení úlohy to ale nemá vliv. Máte ukázat, že princ se dřív nebo později vrátí k paláci, nebo ukázat že se tak stát nemusí. To jde ukázat aniž se řeší pro které počty křižovat příslušný graf existuje.

elnino · 03. 12. 2009 14:50

↑ petrkovar:
Vsetkemu som pochopel okrem tej poslednej vety.Lebo ja sa drzim len tych poctov vrcholov(sudy, lichy)

Matematické Fórum

#1 17. 11. 2009 18:01

teorie grafu s princem

#2 19. 11. 2009 08:50

Re: teorie grafu s princem

#3 19. 11. 2009 20:54

Re: teorie grafu s princem

#4 19. 11. 2009 21:40

Re: teorie grafu s princem

#5 20. 11. 2009 00:15

Re: teorie grafu s princem

#6 20. 11. 2009 00:26 — Editoval gladiator01 (29. 11. 2009 22:13)

Re: teorie grafu s princem

#7 29. 11. 2009 21:54 — Editoval dreek (29. 11. 2009 21:55)

Re: teorie grafu s princem

#8 29. 11. 2009 22:12 — Editoval gladiator01 (29. 11. 2009 22:17)

Re: teorie grafu s princem

#9 29. 11. 2009 22:14 — Editoval jelena (29. 11. 2009 22:43)

Re: teorie grafu s princem

#10 30. 11. 2009 00:47

Re: teorie grafu s princem

#11 01. 12. 2009 10:41

Re: teorie grafu s princem

#12 01. 12. 2009 10:58

Re: teorie grafu s princem

#13 01. 12. 2009 11:09

Re: teorie grafu s princem

#14 02. 12. 2009 20:17

Re: teorie grafu s princem

#15 03. 12. 2009 00:43

Re: teorie grafu s princem

#16 03. 12. 2009 10:28

Re: teorie grafu s princem

#17 03. 12. 2009 10:50

Re: teorie grafu s princem

#18 03. 12. 2009 11:14

Re: teorie grafu s princem

#19 03. 12. 2009 11:40

Re: teorie grafu s princem

#20 03. 12. 2009 11:54

Re: teorie grafu s princem

#21 03. 12. 2009 11:58

Re: teorie grafu s princem

#22 03. 12. 2009 12:44 — Editoval elnino (03. 12. 2009 13:20)

Re: teorie grafu s princem

#23 03. 12. 2009 12:50

Re: teorie grafu s princem

#24 03. 12. 2009 14:17

Re: teorie grafu s princem

#25 03. 12. 2009 14:50

Re: teorie grafu s princem

Zápatí