ISSN 0351-6652 Letnik 29 (2001/2002) Številka 5 Strani 292-297
Štefko Miklavic in Martin Juvan:
IME ROŽE, LABIRINT IN PREGLED GRAFA
Ključne besede: matematika, teorija grafov, labirint, Tarryjev algoritem.
Elektronska verzija:
http://www.presek.si/29/1483-Miklavic-Juvan.pdf
© 2002 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo
IME ROŽE, LABIRINT IN PREGLED GRAFA
V znanem detektivsko-zgodovinskem romanu italijanskega pisatelja Umberta Eca Ime rože (1] menili Viljem 111 njegov pisar Adson raziskujeta niz skrivnostnih umorov v samostanu nekje v severni Italiji. Ključ do razrešitve skrivnosti je knjiga v samostanski knjižnici. Knjižnica je zgrajena kot labirint; ima namreč 56 sob, od katerih so nekatere povezane z vrati, druge pa ne. Ko se v noči z drugega na tretji dan Viljem in Adson izgubita v tej knjižnici, pravi Viljem Adsonu:
"Samo en način je, kako najdeš pot iz labirinta. Na, vsakem novem križišču, se pravi takem, kjer še nisi bil, je treba mesto, kjer si vstopil, zaznamovati s tremi znaki. Če po znamenjih na svoji poti vidiš, da si že bil tam, označiš kraj, skozi katerega si prišel tja, z enim samim znakom. Če so vsi prehodi že označeni, se moraš vrniti po isti poti nazaj. Če pa je kakšen prehod šc brez znakov, izbereš tega in ga označiš z dvema, znakom a. Če greš skozi prehod, ki nosi en sam znak, m» dodaš še dva, tako da bo imel tisti prehod potlej tri. Prehodi! si vse dele labirinta, če takrat, ko prideš do razpotja, nikdar ne greš skozi prehod s tremi znaki, razen če ni še kakšen prehod neoznačen."
Recept je podan zelo nejasno in nenatančno. V literaturi in na internetu se pojavljala dva algoritma, ki bi lahko "ustrezala" zgornjemu opisu. Prvega je leta 1882 objavil francoski inženir Tremaux. Njegov opis lahko bralec najde v članku Marije Venci j eve Hoja, po labirintu [2] aH pa na internetncm naslovu www. astrolog. org/labyrnth/algrittun. htm. Drugi algoritem, ki se zdi nekoliko bližji opisu iz knjige, je leta 1895 predstavil Gaston Tarry1. Ta algoritem je s sicer bolj skopo razlago opisan v knjigi Wilsona in Watkinsa Uvod v teorijo grafov [3]. Pri tem naj bo bralec pozoren na drobno napako ob koncu pravila (a), V tem prispevku pa bomo Tarrvjev algoritem natančno opisali in podrobno utemeljili, da nas res zmeraj pripelje iz labirinta.
Algoritem sestavljajo tri skupine pravil: po prvi skupini pravil se ravnamo pri odhodu iz križišča, drugo skupino uporabljamo ob prihodu v križišče, zadnje pravilo pa uporabimo le tedaj, ko zaidemo v slepo ulico. Pravila so naslednja:
1 Gaston Tarry (1843 1913), francoski matematik
01; če obstaja izhod iz križišča, ki še ni označen, ga izberi in ga označi z dvema znakoma.
02: Če neoznačen izhod ne obstaja, izberi izhod z enim znakom ter mu dodaj še en znak.
03: Ce neoznačenih izhodov in izhodov z enim znakom ni, izberi izhod s tremi znaki ter mu izbriši en znak.
Pl: Če prideš v križišče, kjer še nisi bil. označi vhod, skozi katerega si prišel, s tremi znaki.
P2: Če prideš v že obiskano križišče po poti, po kateri še nisi šel, označi vhod, skozi katerega si prišel, z enim znakom.
S: Če prideš v slepo ulico, se obrni in pojdi nazaj po isti poti (kaj pa ti sploh preostane drugega).
Zgornja pravila naj bi nam omogočila, da obiščemo vsa križišča labirinta, ne da bi šli po katerikoli poti več kot dvakrat. Pa poglejmo, ali ta trditev drži.
Najprej opišimo matematično formulacijo problema. Labirint predstavimo z grafom; križišča labirinta bodo točke grafa, poli med križišči pa povezave grafa. Pri tem nas ne moti, če ima tako dobljeni graf zanke ali večkratne povezave (če je, recimo, kako križišče s povezavo povezano samo s sabo ah pa če sta dve križišči povezani z več povezavami). Morebitne slepe poti v labirintu v grafu predstavimo s povezavo in točko na koncu (to si lahko predstavljamo tudi tako, da smo na koncu slepih hodnikov naredili sobe; po taki razširitvi labirinta pravila S ne potrebujemo več). V nadaljevanju bomo privzeli, daje tako dobljeni graf povezan, da se torej iz vsake točke grafa da priti po povezavah v vsako drugo točko. Če to ne drži, potem imamo opravka z več povsem ločenimi labirinti.
Nahajamo se torej v neki točki grafa, radi pa bi prišli v neko drugo, "odlikovano" točko grafa (to je, recimo, izhod iz labirinta). Če bi po nekem postopku znali obiskati vse točke grafa, potem bi slej ko prej našli tudi odlikovano točko. Pri tem ne smemo pozabiti pomembnega dejstva, da graf vidimo samo lokalno. Namreč, v vsaki točki je edina informacija, ki jo imamo o grafu, število povezav, ki izhajajo iz te točke, in podatek, kolikokrat smo že šli po teh povezavah. To je kar huda omejitev, ki nam močno oteži iskanje izhoda.
Poglejmo si labirint in njemu prirejeni graf s slike 1. Recimo, da se nahajamo v točki 1, radi pa bi prišli v točko 4. Na začetku izberemo po pravilu 01 eno od dveh povezav, ki vodita iz točke 1, recimo, povezavo do točke 2. Ta povezava dobi na svojem koncu pri točki 1 dva znaka.
Slika 1. Labirint in njemu prirejeni graf,
pri točki 2 pa tri znake. Po pravilu 01 imamo sedaj dve možnosti, izberimo, recinto, povezavo do točke 3. Ta povezava dobi spet dva znaka na koncu pri točki 2 ter tri znake pri točki 3, Od točke 3 spet po 01 izberemo npr. povezavo do točke 1 (povezava dobi dva znaka pri točki 3 ter en znak pri točki 1 - glej sliko 2(a), kjer polni krožeč pomeni trenutni položaj). Zaradi pravila 02 se moramo vrniti v točko 3 (povezava ima sedaj pri točki 1 dva znaka - glej sliko 2(b)). Ostane nam še povezava do točke 5, ki dobi dva (oziroma tri) znake - glej sliko 2(c). Od tu se zaradi pravila 03 spet vrnemo v točko 3 ter pri tem izbrišemo en znak pri točki 5 (slika 2(d)). Po pravilu 03 gremo nazaj v točko 2 in tej povezavi izbrišemo en znak pri točki 3. Od tu pa gremo po pravilu 01 končno do točke 4 (slika 2(e)). Seveda je bralec že sam ugotovil, da je število povezav, ki jih prehodimo, preden dosežemo želeno točko, precej odvisno tudi od sreče, ki jo imamo pri izbiri povezav.
Slika 2, Sprehod po labirintu.
V nadaljevanju bomo naredili natančno analizo obnašanja Tarryje-vega algoritma in pri tem opisali nekaj lastnosti, ki veljalo med pregledovanjem grafa. Začnimo z nekaj preprostimi ugotovitvami. Povezave grafa med pregledovanjem na obeh koncih označujemo z izbranimi znaki (npr. pikami ali črticami). Pravila so postavljena tako, da povezava bodisi na nobenem koncu nima nobenega znaka (povezava še ni bila prehojena ne v eni ne v drugi smeri) bodisi je označena na obeh koncih (kar pomeni, da je že bila prehojena vsaj v eni smeri), pri čemer sta na enem koncu dva znaka, na drugem pa en, dva ali trije znaki. Nadalje velja, da se koncu povezave, ki je že označen z dvema znakoma, število znakov ne bo več spremenilo. Ker nobeno pravilo ne dopušča, da bi trenutno točko zapustili po povezavi, ki ima začetek že označen z dvema znakoma, hkrati pa ob odhodu vedno poskrbimo, da začetek izhodne povezave postane označen z dvema znakoma, od tod sledi, da nobene povezave v nobeni smeri ne prehodimo več kot enkrat.
Med sprehajanjem po grafu se premikamo iz točke v točko in pri tem spreminjamo oznake na koncih povezav. Naša analiza temelji na naslednjih ugotovitvah:
(i)	Med sprehajanjem v vsakem trenutku za vsako točko v velja, da smo jo doslej zapustili natanko tolikokrat, kot je koncev povezav, ki so pri v označeni z dvema znakoma.
Utemeljitev. Točko vedno zapustimo po enem od pravil 01-03. To pa so tudi edina pravila, ki omogočajo (in vedno tudi dosežejo) postavitev dveh znakov.
(ii)	Med sprehajanjem v vsakem trenutku za vsako točko v velja, da smo doslej vanjo prišli natanko tolikokrat, kot je takih povezav s koncem pri v, katerih drugi konec je označen z dvema znakoma. Lastnost utemeljimo na enak način kot točko (i).
Opozorimo, da nam v (i) in v (ii) zanka v točki v, ki ima na obeh koncih dva znaka, pomeni dva prihoda in dva odhoda iz točke v, zanka z dvema znakoma le na enem koncu pa en odhod in prihod.
Naj bo 2 točka, v kateri začnemo pregled grafa. Kdaj pa se Tarryev algoritem konča? Takrat, kadar ne moremo uporabiti nobenega pravila več. Torej tedaj, ko iz trenutne točke sprehoda ne moremo več nadaljevati. To pa pomeni, da imajo vsi izhodi, ki vodijo iz točke, kjer se trenutno nahajamo, dva znaka. Ali se to lahko zgodi v točki, ki je različna od z7 Seveda ue. Če bi se to zgodilo, potem bi morali v končno točko priti enkrat več, kot smo iz nje odšli. To pa po (i) in (ii) ni mogoče, saj v točko ne moremo priti večkrat, kot je koncev povezav pri tej točki, vsi ti pa so označeni z dvema znakoma in po (i) predstavljajo odhode. Pokazali smo torej naslednjo lastnost Tarryjevega algoritma:
Lastnost 1. Tarryjev algoritem se vedno konča v začetni točki z.
Iz lastnosti 1 sledi, da smo ob koncu algoritma iz vsake točke odšli natanko tolikokrat, kot srno v njo prišli. Od tod pa ob upoštevanju (i) in (ii) že sledi naslednja lastnost:
Lastnost 2. Ce so ob zaključku Tarryjevega algoritma v neki točki vsi konci povezav označeni z dvema znakoma, potem so z dvema znakoma označeni tudi vsi nasprotni konci teh povezav.
Za konec pokažimo, da s Tarryjcvim algoritmom res prehodimo vsako povezavo grafa natanko dvakrat, po enkrat v vsaki smeri. Pa recimo, da temu ni tako.
Potem ob koncu algoritma obstaja povezava, ki ni na obeh koncih označena z dvema znakoma. Imenujmo take povezave aepregledane, točkam, ki so krajišče nepregledane povezave, pa bomo rekli s/abo pregledane. Zaradi povezanosti grafa obstaja vsaj ena slabo pregledana točka, ki smo jo med sprehodom po grafu obiskali. (Premislite, da tako točko lahko dobimo npr. tako, da vzamemo prvo obiskano točko na poljubni poti od katerekoli slabo pregledane točke do začetne točke z.) Med vsemi obiskanimi, a slabo pregledanimi točkami, naj bo v tista, ki jo s Tarrvjevim
algoritmom obiščemo prvo. Gotovo v ni točka z, sicer se pregled grafa še ne bi končal. Ker točko zapustimo po povezavi, označeni s treini znaki, šele tedaj, ko ni več nobene druge možnosti, pri v obstaja nepregledana povezava, ki ima tri znake (glej sliko 3). Naj bo točka u drugo krajišče te povezave (u v, saj zanka nikoli nima treh znakov). Točka ti je prav tako bila obiskana med pregledom grafa, in sicer neposredno pred prihodom v točko V (morda pa tudi že kdaj prej). Ker pa je hkrati it tudi krajišče nepregledane povezave med u in v, je tudi u ena od slabo pregledanih točk. To pa je v protislovju z izbiro točke v. ki naj bi bila med vsemi slabo pregledanimi točkami prva obiskana.
Lastnost 3. S Tarryjevim algoritmom prehodimo vsako povezavo grafa
natanko dvakrat.
Tako, analiza algoritma je opravljena in njegova pravilnost dokazana. Seveda pa podani opis algoritma ni edini možni. Če nas npr. moti brisanje znakov, lahko označevanje koncev povezav zasnujemo tako, da imamo ob koncu namesto dveh povsod po tri znake (in znake med sprehajanjem ves čas samo dodajamo). V bistvu je treba le zamenjati vlogo dveh in treh znakov (ter primerno prilagoditi pravila). Poskusite sestaviti tako prilagojena pravila!
Na koncu pa še povabilo: Če knjige Ime rožo še niste prebrali, si vsekakor vzemite čas zanjo. Lahko pa si ogledate tudi istoimenski film s Seanom Conneryjem v glavni vlogi. Zemljevid samostanske knjižnice, ki je omenjena na začetku tega sestavka, lahko dobite na
www,uni-weimar.de/~kleppe/studium/rose/.
Za vajo lahko poskusite, ali znate pregledati labirint z opisanim algoritmom. Izhod je v sedemkotni sobi desno zgoraj.
Literatura
[1]	U. Eco: Ime rože, Mladinska knjiga, Ljubljana, 1985
[2]	M. Vencelj: Hoja po labirintu, Presek, letnik 17 (1989/90), št. 3, str. 154-159
[3]	Ii.. J. Wilson in J. J. Watkins: Uvod v teorijo grafov. Knjižnica Sigma 63, DMFAS, Ljubljana, 1997
Štefko Miklavič. Martin Juvan