i
i
“Vencelj-labirint” — 2010/6/16 — 12:57 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 17 (1989/1990)
Številka 3
Strani 154–159
Marija Vencelj:
HOJA PO LABIRINTU
Ključne besede: matematika, teorija grafov, graf, Trémauxov algori-
tem.
Elektronska verzija:
http://www.presek.si/17/982-Vencelj-labirint.pdf
c© 1989 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
154
HOJA PO LABIRINTU
Oto k Kret a je bil v sivi davnini središče egejske civilizac ije, prve v
Evro pi, ki je cvete la sto letja pred obdobjem klasične Grčije. Ohranj ena je
pripoved o mogočnem kralju Minosu s Knososa na Kr eti, ki je s po morsko
silo vlada l v Egeju. Zdi se, da so bile kralju Min osu podrejen e tudi Aten e,
155
saj JC od njih zahteval letno dajatev sedem deklet in fantov za hrano
Minotavru, pošasti z bikovo glavo, ki je živela v globinah labirinta pod
kraljevo palačo.
Krožile so govorice, da ima kralj grdo navado zapreti v labirint
Minotavru na voljo tudi vsakega nepovabljenega tujca, ki se je pojavil na
otoku. Če natančneje pomislimo, je bila to bržčas samoobramba otočanov
pred potujočimijunaki in drugimi morskimi roparji .
Mit iz zgodnjega junaškega obdobja pripoveduje, da te govorice niso
prav nič ganile atenskega junaka Tezeja. Kot se za junaka spodobi , se je
nemudoma podal v nevarnosti na Kreto . Tam mu je šlo sprva vse narobe.
Ujeli so ga in postal naj bi Minotavrova žrtev.
Toda lepa Minosova hči Ariadna - v vseh pripovedkah so kralji čne lepe -
se je vanj zaljubila in ga sklenila rešiti . Mogoče je bila sama tako zvita, ali
pa ji je dala njena dojilja dober nasvet - vsekakor je našla rešitev. Svojemu
Tezeju je dala klobčič preje. Junak je en konec niti privezal ob vhodu v
labirint in se z odvijajočo se klobko veni in z mečem v drugi roki pognal
junaštvu nasproti v podzemlje. Tam je našel in ubil Minotavra. Nato je
moral samo še na klobčič navijati nit, ki ga je vodila k srečnemu koncu.
Prav lahko bi se zgodilo, da Tezej Minotavra sploh ne bi srečal in ga
tako ne bi rnoqel ubiti. In nič ne bi bilo ne z junaštvom ne z zgodbo!
Zato Tezeju pri iskanju raje pomagajmo! Najprej moramo seveda
predpostaviti, da je labirint končen in da je mesto, kjer tiči Minotaver, res
dosegljivo z vhoda v labirint. Razen tega bomo našega kandidata za junaka,
namesto s klob či čem preje, opremili s kosom snovi, ki se v temi sveti. V
skrajni sili bo dober tudi trhel les, ki se je svetil že v tistih davnih časih. Z
njim bo moral Tezej zaznamovati začetek in konec vsake prehojene poti
med dvema križiš černa in to vsakokrat, ko bo šel po njej. Po prihodu v
posamezno križišče - z izjemo začetnega - bo imel v križišču liho mnogo
oznak, po odhodu iz njega pa sodo mnogo. Za začetno križišče velja ravno
obratno. Razen tega bo lahko v vsakem križišču med seboj ločil
neprehojene poti, enkrat, dvakrat prehojene poti itd. Seveda mu to
razlikovanje samo po sebi še ne bo jamčilo, da bo preiskal res ves labirint in
na koncu tudi našel izhod iz njega. Za to potrebuje še zanesljiva in čimbolj
preprosta navodila .
Labirint lahko preprosto skiciramo tako, da vsako križišče predstavimo
s točko, posamezni hodniki pa so povezave med temi točkami. Tako skico
imenujemo graf (slika 1) .1l V grafu moramo zaznamovati vhod, to je
začetno križišče. Na skici je označeno s črko A . Pogoj, naj bo Minotavrov
neznani položaj dosegljiv iz vhoda v labirint, pomeni, da mora biti graf
156
povezan. Tezej mora začeti v točki A , prehoditi vse povezave grafa in se
vrniti v točko A . Rekli bomo, da mora napraviti popoln obhod grafa. Le
tako bo Minotavra zanesljivo našel in se vrnil iz podzemlja.
A
Slika 1 Slika 2
Načelno je to prav gotovo mogoče. Če Tezeja zamenjamo s konico
svinčnika, ki drsi od točke A po povezavah grafa, se sicer lahko vrnemo vA
prej, kot konica svinčnika opiše ves graf. Toda to ni nič hudega. Gremo pač
ponovno na pot, le da tokrat v tisti del grafa, ki ga še nismo obšli. To
počnemo tako dolgo, dokler ne izčrpamo vseh povezav grafa. Pri tem bomo
sicer morda kakšno povezavo prehodili večkrat, a to za nalogo ni bistveno.
Toda Tezejeva naloga je težja. On labirinta oziroma grafa ne pozna. Ob
povratku vA ne more vedeti, ali je še kaj labirinta neprehojenega, niti ne
ve, v katero smer naj ponovno krene, da bo naletel na tak predel. Navodila,
ki mu jih bomo dali, morajo biti taka, da bodo razrešila te dileme in da bo
napravil popoln obhod.
V teoriji grafov so zanimivi tako imenovani Eulerjevi obhodi. Pri njih
začnemo in končamo v isti točki in preidemo vse povezave grafa natanko
enkrat. Seveda bi bilo najbolj gospodarno, če bi lahko sestavili taka
navodila, ki bi Tezeja vodila po vsaki povezavi samo enkrat. Toda obst ajajo
grafi, ki ne premorejo Eulerjevega obhoda. Preprost primer takega grafa
imamo na sliki 2.
Torej s takimi navodili ne bo nič. Velja pa naslednja trditev:
Dani povezani graj premore Eulerjev obhod natanko takrat, ko se v
vsaki njegovi točki steka sodo mnogo povezav. 2)
1 ) Študij grafov je v matematiki posebna veja. Nekaj osnov sta za bralce
Preseka zbrala Drago Bajc in Tomaž Pisanski v knjižici Najnujnejše o
grafih, ki je pred 4 leti izšla pri Presekovi knjižnici. Še vedno jo je moč
kupiti pri Komisiji za tisk DMFA.
157
Od tod sledi naslednja ugotovitev:
Vsak povezan graf premore obhod, pri katerem gremo po vsaki
povezavi natanko dvakrat.
Res. Mislimo si, da v grafu vsako povezavo podvojimo. Potem se v vsaki
točki tako popravljenega grafa steka sodo mnogo povezav in torej zanj
obstaja Eulerjev obhod. Ta obhod pa ni nič drugega kot obhod prvotnega
grafa, pr i katerem gremo po vsaki povezavi natanko dvakrat.
Ker labirinta oziroma grafa ne poznamo, borno torej morali biti
zadovoljni z navodili , ki bodo usmerjala našega junaka tako, da bo prehodil
vsako povezavo labirinta natanko dvakrat in pri tem zaključil pohod v
začetni točki. Možnih načinov je več. Mi si borno ogledali le enega, ki je v
teoriji grafov znan pod imenom Tršrnauxov algoritem. Poglejmo njegovo
vsebino:
Ko pridemo v dano točkografa, ravnamo takole:
1: Če v točki še nismo bili, jo zapustimo po še neprehojeni povezavi, če
taka povezava obstaja. Sicer se vmemo po isti povezavi.
II : Če smo v točki že bili, potem gremo
Ila: nazaj po zadnji povezavi, če smo jo uporabili prvič
Ilb: v neprehojeno povezavo, če taka povezava obstaja in smo
zadnjo povezavo prehodili že dvakrat
Ilc: v enkrat prehojeno povezavo v ostalih primerih
Pravila so ilustrirana na sliki 3. Številka pri posamezni povezavi pomeni,
kolikokrat je bila povezava prehojena pred obravnavanim prihodom v
križišče.
V vsaki od A različni točki pride vsakokrat v poštev natanko eno od
zgornjih štirih navodil. Ne more se zgod iti, da bi v kakšni taki točki obtičali,
to je, da bi vanjo prišli in je ne bi mogli zapustiti . Morda je to še najmanj
jasno pri zadnjem navodilu. Toda po prihodu v tako od A različno točko,
kjer naj bi uporabili zadnje pravilo, je število oznak povezav liho . Ker srno
prišli po drugič uporabljeni povezavi , ki ima tedaj dve oznaki, mora biti na
razpolago vsaj ena povezava z eno oznako, torej vsaj ena samo enkrat
prehojena povezava.
Potovanje nadaljujemo tako dolgo, dokler je mogoče. Ker je labirint
končen in so pravila taka, da nobene povezave ne prehodimo več kot
dvakrat, se pot zanesljivo konča. To se lahko zgodi le v začetni točki A, ker
smo ugotovili , da ne moremo obtičati v nobeni drugi točki.
Sedaj pa hitro svinčnike v roke, narišite poljuben povezan graf in
2 ) Tudi dokaz te trditve najdemo v knjižici Najnujnejše o grafih.
158
preskusite pravila! Slika 4. - Vam je uspelo prehoditi vse povezave grafa
natanko dvakrat in zaključiti v začetni točki?
o
o
o
1
llb
Slika 3
o
~
11
Ila
1
Ilc
Po tem oddihu še dokažimo, da se to res mora zgoditi. Dokazati
moramo le še, da ob uporabi pravilI - II cizčrpamo vse povezave grafa,
vsako natanko dvakrat.
Dokaz: Denimo, da poti ne moremo več nadaljevati. Torej smo po
zgornji ugotovitvi v začetni točki A. Vrnimo se korak za korakom po že
opravljeni poti v obratni smeri. Pri tem se domenimo, da bomo na tej poti
preskočili vse slepe povezave in vse povezave, ki smo jih v skladu s pravilom
Ila prehodili dvakrat zapored. Zanje ni kaj dokazovati, saj so dvakrat
prehojene.
A
Slika 4