Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

II. rész: Bolyongások a gráfban

II. rész: Bolyongások a gráfban

A következőkben egy gráfban való „bolyongásokkal” fogunk foglalkozni. Ez alatt azt értjük, hogy egy csúcsból elindulva élek mentén csúcsról csúcsra lépünk, mindig véletlenszerűen választva ki azt az élt, amelyen haladni fogunk.

Nagyon sok érdekes kérdés tehető fel egy ilyen bolyongással kapcsolatban; ezekből csak ízelítőt tudunk adni.

Egy fontos kérdés az, hogy átlagosan hány lépéssel jutunk el egy csúcsból egy másikba. Először vizsgáljuk meg a legegyszerűbb esetet, egy három csúcsból álló összefüggő láncot:

(a csúcsokat balról jobbra számozzuk)! Itt az 1. végpontból kell eljutni a 3-dikba. Legyen a lépések átlagos száma H . Az 1. csúcsból a 2-dikba 1 lépéssel jutunk el, mivel itt nincs más lehetőség. A 2. csúcsból 1 lépéssel 1 / 2 valószínűséggel a 3-dikba, 1 / 2 valószínűséggel pedig az 1-be jutunk, ahonnan átlagban ismét H lépéssel juthatunk a 3. csúcsba. Így H = 1 + 1 2 · 1 + 1 2 · ( H + 1 ) , innen pedig H = 4 . Amennyiben egy 5 pontból álló láncot veszünk, előző eredményeink felhasználásával megkönnyítjük a megoldást. Itt is a két végpont közötti utat kell megtennünk. Az 1. csúcsból a 3-dikba átlagosan 4 lépéssel jutunk el, majd innen ismét 4 lépéssel a lánc valamelyik végébe, 1 / 2 eséllyel a célpontba, 1 / 2 eséllyel pedig a kiindulási pontba, ahonnan átlagosan újabb H lépéssel jutunk a célhoz. Így H = 4 + 4 + 1 2 H , ahonnan H = 16 . Most vizsgáljuk meg a 4 pontból álló lánc esetét! A kiindulási (1.) pontból átlagosan H lépéssel jutunk el a végpontba, a 3. csúcsból pedig legyen szükségünk átlagban G lépésre a táv teljesítéséhez! Ekkor H = 4 + G . A 3. csúcsból 1 lépéssel az esetek fele részében a 4., a másik felében a 2. csúcsba jutunk, ahonnan ismét 1 lépéssel 1 / 2 eséllyel a kezdőpontba (innen átlagosan H lépés kell a célhoz), illetve a 3. csúcsba jutunk (innen G lépés kell). Az elmondottakat összegezve G = 1 + 1 2 · 1 + 1 2 · H + 1 2 · G , az előző egyenletből H -t helyettesítve G = 5 -öt kapunk, ahonnan H = 9 . Általánosan is belátható, hogy egy n hosszúságú úton a szükséges lépések átlagos száma n 2 .

A következőkben teljes gráfokra vetjük fel a kérdést: Átlagosan hány lépést kell sétálni, hogy minden pontot lássunk? Először vizsgáljuk meg az n = 6 esetet! Ha már láttunk pl. 3 csúcsot, akkor egyből kiindulva 1 lépést lépve 3 / 5 valószínűséggel olyan csúcsba lépünk, ahol még eddig nem voltunk, 2 / 5 valószínűséggel pedig olyanba, ahol már jártunk. Így ha átlagosan H lépéssel jutunk el egy olyan csúcsba, ahol még nem jártunk, akkor H = 1 + 2 5 · H , ahonnan H = 5 3 . Így a keresett teljes lépésszám

5 5 + 5 4 + 5 3 + 5 2 + 5 1 = 5 · 1 + 1 2 + 1 3 + 1 4 + 1 5 .

Gondolatmenetünk általánosítható: egy n csúcsból álló gráfra a lépésszám

n - 1 · 1 + 1 2 + + 1 n - 1 ? ( n - 1 ) · ln n .

Erre a feladatra még nem született tetszőleges gráfra vonatkozó megoldás, azonban az egy konkrét pontba való eljutásra már igen. Erre a feladatra a legrosszabb eset egy „sárkány” alakú gráf, amely egy n / 3 csúcsú teljes gráfból és egy hozzá kapcsolódó 2 n / 3 csúcsú láncból áll.

Egy újabb kérdés a témához kapcsolódva: adott csúcsból indulva bolyongunk egy gráfon. Ha az összes csúcsát láttuk, megállunk. Melyik pontban állunk meg a leggyakrabban? Legyen a gráf először egy kör. azt gondolnánk, hogy a kiindulási ponttal szemközti csúcsban állunk meg leggyakrabban, de meglepő módon nem így van: bármely csúcsban (természetesen az induló csúcsot kivéve) ugyanolyan valószínűséggel állunk meg (jó gyakorló feladat!). Nyilvánvaló, hogy a teljes gráf is hasonló tulajdonságú. Be lehet látni, hogy csak a körgráfok és a teljes gráfok rendelkeznek ilyen tulajdonsággal, az összes többiben ezek a valószínűségek nem egyenlők.

Ez is jó feladat: Ha egy gráfból kiválasztunk egy d fokú csúcsot, és a gráfban az élek száma m , akkor ahhoz, hogy visszajussak a kiválasztott pontba, átlagosan 2 m / d lépés szükséges.

Végül a véletlen sétáknak egy szórakoztató alkalmazása: egy városban minden kereszteződésből négy utca fut ki. Beszállunk egy taxiba, de nem tudjuk a címét annak a háznak, ahová megyünk (bár ha elhaladunk előtte, felismerjük); azt se tudjuk, honnan indulunk; és lehet, hogy még abban sem vagyunk biztosak, melyik városban vagyunk. Ennek ellenére, meg tudunk adni a taxisofőrnek egy útvonalat: Bal–Jobb–Egyenes–Vissza–Bal–… úgy, hogy ha ennek megfelelően kanyarodik az egyes kereszteződésekben, akkor biztosan célhoz érünk.

A trükk az, hogy a kanyarodásokat egymástól függetlenül véletlenszerűen írjuk elő. Ha a városban n db kereszteződés van, akkor nagy valószínűséggel egy n 3 hosszú véletlen sorozat végig fog vinni az egész városon.