Eulerjev obhod

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Eulerjev obhod grafa je tak obhod, ki vsebuje vsako povezavo natanko enkrat. Problem, ali ima dani graf Eulerjev obhod, izhaja iz problema königsberških mostov.

Obstoj Eulerjevega obhoda

Kdaj bo v grafu obstajal Eulerjev obhod?

Vidimo lahko, da mora vsakič, ko "obiščemo" neko vozlišče obstajati možnost, da to vozlišče tudi "zapustimo" po drugi povezavi. Zato mora imeti v Eulerjevem grafu vsako vozlišče sodo stopnjo. Velja celo več, kar bomo sedaj tudi pokazali:

Izrek: Naj bo G povezan graf. Če je G Eulerjev, so vsa vozlišča sode stopnje in obratno, če so vsa vozlišča sode stopnje, je graf Eulerjev.

O prvem delu dokaza smo že razmislili tik pred izrekom, drugega pa dokažemo z indukcijo na število povezav.

Zgledi

Za primer, kateri graf je Eulerjev, si oglejmo naslednje štiri grafe. Najprej si oglejmo kar graf, ki nastopa v problemu königsberških mostov:

image:euler3.jpg

Zanj smo ugotovili, da je tako Eulerjev kot Hamiltonov. Pa sedaj ta graf nekoliko preoblikujmo in poglejmo kaj dobimo:

image:euler6.jpg image:euler4.jpg image:euler5.jpg

Graf (a) je Eulerjev, saj vsebuje Eulerjev obhod BCGFEGB. Drugi graf (b) ni pa Eulerjev, ravno tako kot tudi zadnji graf (c).

Iz problema iskanja Eulejevega obhoda lahko dobimo tudi nekaj zanimivih ugank in nalog iz zabavne matematike, najdejo pa se tudi čisto pravi problemi, kot je na primer iskanje najkrajše poti pri čiščenju snega v večjem mestu.

Pa si za začetek oglejmo uganke Eulerjevega tipa, na katere lahko večkrat naletimo v kakšni knjigi:

Poskusimo narisati dani diagram s čim manj potezami in pri tem paziti, da kakšen del ne narišemo dvakrat. Tako je na primer spodnji diagram čisto preprosto narisati s štirimi potezami. Toda, ali se ga da narisati tudi z manj (s tremi potezami)?

image:euler7.jpg

Leta 1809 je L. Poinsot pokazal, da se da diagrame z n-paroma povezanimi točkami narisati z eno samo potezo, če je n lih.

Za lažje razumevanje si poglejmo nekaj preprostih primerov:

image:euler8.jpg image:euler9.jpg image:euler10.jpg image:euler11.jpg image:euler12.jpg

V jeziku teorije grafov to lahko povemo tako: polni graf Kn (to je graf, v katerem nastopajo vse možne povezave med točkami) je Eulerjev samo za lihe vrednosti n, kot sledi iz zgornjega izreka.

Pa si oglejmo: Vemo, da je polni graf K7 Eulerjev, saj imajo vse njegove točke sodo stopnjo. Če sedaj vozlišča grafa označimo z 0,1,2,3,4,5 in 6, potem dobimo Eulerjev obhod, če povezave prehodimo v naslednjem vrstnem redu: 10, 12, 23, 34, 45, 56, 60, 02, 24, 46, 61, 13, 35, 50, 03, 36, 62, 25, 51, 14, 40.

image:euler13.jpg
Osebna orodja