Page 111 - vol1

Térjünk most rá a labirintus problémák tanulmányozására. Az előbbi két
példa esetén a séta aránylag könnyen megvalósítható volt, hiszen semmiféle
akadály, zsákutca nem volt. Ellenben a labirintusokban zsákutcák is vannak, ezek
teszik bonyolulttá és egyben érdekesebbé egy labirintus bejárását. Ugyanakkor
könnyen elképzelhető, hogy egy labirintusban rengeteget lehet fölöslegesen
bolyongani, de minket az érdekel, hogyan lehet egy labirintusból minél
hamarabb (minél rövidebb úton) kijutni. Ezért lesz szükség arra, hogy a
gráfelmélet segítségével vizsgáljuk a legrövidebb kiutat a labirintusból.

3. A labirintus minden folyosóját végig kell járjuk, a lehető legrövidebb
úton, és az x-ből indulva, ugyancsak az x-be kell megérkezzünk. Hogyan
lehetséges ez?

A labirintusnak egy gráfja a mellékelt ábrán látható. A gráf minden élén
pontosan 2-szer kell végig haladnunk, az x-ből indulva, az x-be kell érkezni. Az
éleket megszámoztuk.
Egy Euler-kör a következő: 1, 2, 3, 4, 5, 5, 13, 12, 12, 13, 4, 3, 9, 10, 6, 6, 7, 7,
10, 11, 11, 8, 8, 2, 1.

4. Az ábrán látható labirintust a lehető legrövidebb úton kell bejárni
úgy, hogy az x-ből indulunk, minden folyóson körbe kell járjunk, aztán
visszaérjünk az x-be.
Hogyan lehetséges ez úgy, hogy minél rövidebb utat tegyünk meg?

111