Matematické Fórum

honza33 · 27. 11. 2009 12:36

Pan Wassermann bydlí v městečku, které je postaveno uprostřed jezera. Každý z obyvatel vlastní jeden dům plující na vodě. Domy jsou mezi sebou spojeny lávkami, a to tak, že každý dům je spojen lávkou s minimálně dvěma dalšími domy. Víme, že pokud se jedna libovolná lávka utrhne, je stále možno dostat se z každého domu do všech ostatních. Pan Wassermann rád navštěvuje své přátele. Ukažte, že si pan Wassermann může vždy naplánovat cestu k nějakému (libovolnému) příteli tak, že na zpáteční cestě do svého domu nepoužije žádnou lávku, kterou použil na cestě tam.

Příjde mi logické, že pokud ke každému domu vedou 2 mosty, tak prostě po jednom přijde a po druhém odejde, ale jak to vypočítat a dokázat? Mohl bych si nakreslit graf, ale tudy asi cesta nevede, když přesně nevím, jak jsou domy pospojovány. Poradí někdo, jak na to?
Díky

Kondr · 27. 11. 2009 13:12

↑ honza33:Důležitá je tam ta podmínka s utržením lávky. Z ní odvodíme, že každé dva sousední vrcholy leží na nějaké kružnici, což snadno rozšíříme na tvrzení, že každé dva vrcholy leží na nějaké kružnici. Pan Wasserman půjde po této kružnici jednou cestou tam a druhou zpět.

honza33 · 28. 11. 2009 12:38

Jak to myslíte, že každé 2 sousední vrcholy leží na nějaké kružnici? Nějak nechápu, co si pod tím představit

Kondr · 29. 11. 2009 18:50

↑ honza33:Znáš z teorie grafů pojmy jako vrchol, kružnice, ... ? Je jasné, že úloha popisuje graf (hrana=lávka a vrchol=dům)?

ridick777 · 29. 11. 2009 20:43

↑ honza33: na bani berem cyklus grafu = kružnice ;-)

petrkovar · 01. 12. 2009 17:07

↑ ridick777:Přesněji řečeno nerozlišujeme pojem cyklus a kružnice. Něktří autoři rozlišují cyklus jako samostatný graf a kružnice jako podgraf a někteří jiní zase naopak cyklus jako podgraf a kružnice jako graf. Nechci to studentům komplikovat, protože obě dostupné knížky se v tom liší. Já se snažím rozlišovat graf a podgraf pomocí dovětku nebo přívlastku a preferuji jediný termín cyklus. Pak máme cyklus (graf) nebo cuklus v grafu (podgraf). Takhle podrobně to na přednášce nevysvětluji. Třeba si to tady přečte více lidí než na přednášce.

honza33 · 01. 12. 2009 17:29

no znám, no. Kružnice je serie propojených vrcholů a vrcholy jsou jednotlivé prvky.
Pokud vezmu podmínku s utržením lávky, tak vlastně celý graf je kružnice, už jsem to asi pochopil.

Kondr · 01. 12. 2009 17:56

↑ honza33:Ne. Třeba tento graf:

o-o-o
| | |
o-o-o
| | |
o-o-o

je 2-souvislý (má vlastnost s utržením lávky) a není Hamiltonovský (všechny vrcholy neleží na stejné kružnici). Pouze každé dva vrcholy leží na nějaké kružnici.

Matematické Fórum

#1 27. 11. 2009 12:36

Teorie grafů - lávky mezi domy

#2 27. 11. 2009 13:12

Re: Teorie grafů - lávky mezi domy

#3 28. 11. 2009 12:38

Re: Teorie grafů - lávky mezi domy

#4 29. 11. 2009 18:50

Re: Teorie grafů - lávky mezi domy

#5 29. 11. 2009 20:43

Re: Teorie grafů - lávky mezi domy

#6 01. 12. 2009 17:07

Re: Teorie grafů - lávky mezi domy

#7 01. 12. 2009 17:29

Re: Teorie grafů - lávky mezi domy

#8 01. 12. 2009 17:56

Re: Teorie grafů - lávky mezi domy

Zápatí