Ojlerov put

U teoriji grafova, Ojlerov put je put u okviru grafa, koji obilazi svaku granu tačno jednom. Na sličan način, Ojlerov ciklus je put koji počinje i završava se u istom čvoru. Leonard Ojler je prvi diskutovao o njima pri rešavanju poznatih sedam Kenigsbergovih mostova, 1736. godine. Problem može biti formulisan matematički:

S obzirom na graf na slici, da li je moguće da se izgradi put (ili ciklus, to je put koji počinje i završava se u jednom istom čvoru), koji poseti svaku granu tačno jednom?

Ojler je pokazao da je neophodan uslov, za postojanje Ojlerovog ciklusa, da su svi čvorovi u grafu parnog stepena, i rekao je, bez dokaza, da povezan graf kod kojeg su svi čvorovi parnog stepena jeste Ojlerov graf. Prvi kompletan dokaz ove poslednje izjave objavio je, posthumno 1873. godini, Karl Hirholcer.^[1]

Pojam Ojlerov graf ima dva opšta značenja u teoriji grafova. Prvo - to je graf koji sadrži Ojlerov put, a drugo - graf, čiji su svi čvorovi parnog stepena. Ove definicije se poklapaju za povezane grafove.^[2]

Za postojanje Ojlerovog puta neophodno je da su nula ili dva čvora neparnog stepena; to znači da Kenigsbergov graf nije Ojlerov. Ako ne postoje čvorovi neparnog stepena, svi Ojlerovi putevi su ciklusi. Ako postoje tačno dva čvora neparnog stepena, svi Ojlerovi putevi počinju u jednom od čvorova i završavaju se u drugom. Graf koji ima Ojlerov put, ali ne i Ojlerov ciklus se naziva polu-Ojlerov.

Definicija

Ojlerov put,^[3] u neusmerenom grafu, je put, koji koristi svaku granu tačno jednom. Ako ovaj put postoji, onda se graf zove polu-Ojlerov.^[4]

Ojlerov ciklus,^[3] u neusmerenom grafu, je ciklus , koji koristi svaku granu tačno jednom. Ako takav ciklus postoji, onda se graf zove Ojlerov.^[5] Termin "Ojlerov graf" se ponekad koristi u slabijem značenju da označi graf, gde je svaki čvor parnog stepena. Za krajnje povezane grafove ove dve definicije su ekvivalentne, iako, nepovezan graf je Ojler u slabijem značenju, ako i samo ako svaka komponenta povezanosti ima Ojlerov ciklus.

Za usmerene grafove, "put" treba zameniti na usmeren put i "ciklus" sa usmeren ciklus.

Definicija i osobine Ojlerovih puteva, ciklusa i grafova važe i za multigrafove.

Ojlerova orijentacija neusmerenog grafa je ustupanje pravca svake grane u grafu G tako da je za svaki čvor v, ulazni stepen od v jednak izlaznom stepenu od v. Takva orijentacija postoji za bilo koji neusmereni graf, u kojem je svaki čvor parnog stepena, i može se naći izgradnjom Ojlerovog puta u svaku komponentu povezanosti od G i ciljanjem ivice na osnovu puta.^[6] Svaka Ojlerova orijentacija povezanog grafa je jaka orijentacija, orijentacija koja čini dobijeni usmereni graf jako povezan.

Osobine

Neusmereni graf ima Ojlerov ciklus, ako i samo ako svaki čvor ima parni stepen, i svi čvorovi sa ne-nula stepenom pripadaju jednoj komponenti povezivanosti.
Neusmereni graf može da se rastavi na cikluse disjunktnih čvorova, ako i samo ako su svi njihovi čvorovi parnog stepena. Dakle, graf ima Ojlerov ciklus, ako i samo ako on može da se rastavi na cikluse disjunktnih čvorova i njegovi čvorovi ne-nula stepena pripadaju jednoj komponenti povezanosti.
Neusmereni graf ima Ojlerov put ako i samo ako tačno nula ili dva čvora su neparnog stepena, i ako svi čvorovi nultnog stepena pripadaju jednoj komponenti povezanosti.
Usmereni graf ima Ojlerov ciklus, ako i samo ako svaki čvor ima jednake ulazne i izlazne stepene i svi čvorovi ne-nultog stepena pripadaju jednoj čvrstoj komponenti povezanosti. Ekvivalentno, usmeren graf ima Ojlerov ciklus, ako i samo ako on može da bude razložen na cikluse disjunktnih čvorova i svi njegovi čvorovi ne-nultog stepena pripadaju jednoj čvrstoj komponenti povezanosti.
Usmereni graf ima Ojlerov put, ako, i samo ako najviše jedan čvor ima (izlazni stepen) − (ulazni stepen) = 1, najviše jedan čvor ima (ulazni stepen) − (izlazni stepen) = 1, svaki drugi čvor ima jednake ulazne i izlazne stepene, i svi čvorovi ne-nultog stepena pripadaju jednoj komponenti povezanosti neusmerenog grafa.

Konstrukcija Ojlerovih puteva i ciklusa

Flerijev algoritam

Flerijev algoritam je elegantan ali neefikasan algoritam, koji datira iz 1883.^[7] Uočiti graf koji ima sve čvorove u istoj komponentu i tačno dva čvora neparnog stepena. Algoritam počinje u jednom od čvorova neparnog stepena, ili, ako ga graf nema, počinje u proizvoljno izabranom čvoru. Na svakom koraku on bira sledeću ivicu na putu, čijim uklanjanjem graf ostaje povezan, a ako ne postoji takva grana, u ovom slučaju, on uzima preostale grane u odnosu na trenutnu. On zatim prelazi na druge čvorove i uklanja izabranu granu. Na kraju algoritma nema grana, i niz grana koje su redom izabrane formira Ojlerov ciklus, ako u grafu nema čvorova neparnog stepena, ili Ojlerov put, ako postoje tačno dva čvora neparnog stepena.

Dok izbegavanje grafa u Flerijevom algoritmu ima linearnu zavisnost od broja grana, odnosno O(|E|), takođe treba uzeti u obzir složenost otkrivanja mostova. Ako želimo da ponovo pokrenete Tarjanov algoritam za pretragu mosta za linearno vreme, nakon uklanjanja svake grane, Flerijev algoritam će imati vremensku složenost O(|E|²).^[8] dinamički algoritam za pretragu mosta omogućava da bude poboljšana $O(|E|\log ^{3}|E|\log \log |E|)$ , ali je i dalje znatno sporiji nego alternativni algoritmi.

Hirholcerov algoritam

Hirholcerov članak iz 1873. koji pruža drugačiji način za pronalaženje Ojlerovog ciklusa, je efikasniji od Flerijevog algoritma:

Izabrati bilo koji početni čvor v, i pratiti put grana od tog čvora, pa sve do povratka u v. Nije moguće da se zaglavi na bilo kom čvoru osim u v, jer parni stepen svih čvorova garantuje da kada je sledeća staza g na putu tamo mora da bude slobodna grana, ostavljajući g. Put formiran na taj način je začarani krug, ali ne može da pokrije sve čvorove i grane originalnog grafa.
Dokle god postoji čvor u, koji pripada tekućem putu, ali ima susednih grana koji nisu deo puta, pokrenuti još jedanput od u, koristiti sledeće neiskorišćene grane, dok se ne vratimo na u, i pridružiti put, formiran na ovaj način, na prethodni put.

Koristeći strukturu podataka, kao što je dvostruko povezana lista, za održavanje skupa neiskorišćenih grana incidentnih sa svakim čvorom, za održavanje liste čvorova na trenutnom putu koje imaju neiskorišćene grane, i za održavanje samog puta, pojedinačne operacije algoritma (pronalaženje neiskorišćenih grana za izlaz svakog čvora, i povezivanje dva puta koji dele granu) može da bude izvršena za konstantno vreme svaki put, dakle, za opšti algoritam je potrebno linearno vreme, $O(|E|)$ .^[9]

Brojanje Ojlerovih ciklusa

Problemi složenosti

Broj Ojlerovih ciklusa u usmerenim grafovima može se izračunati pomoću tzv. BEST teoreme, nazvane u čast de Brujin, Van Ardene-Erenfest, Samit i Tute. Formula glasi da je broj Ojlerovih ciklusa u usmerenom grafu proizvod stepena faktorijela i determinante, preko teoreme matrice stabla, dajući algoritam (polinomijalne vremenske složenosti).

BEST teorema, prvi put formulisana u takvom obliku u "Napomena objavljena u dokazu" od strane Ardene-Erenfesta i u članku de Brujina (1951). Originalni dokaz je bijektivan i generalizovao de Brujinove nizove. On je varijacija na ranijem rezultatu Smita i Tutea (1941).

Brojanje Ojlerovih ciklusa neusmerenog grafa je mnogo teže. Ovaj problem je #P-kompletan.^[10] U pozitivnom smeru, Markov lanac Monte Karlo pristup, po Kocig konverzijama (uveo Anton Kocig 1968. godine), veruje se da daju oštru aproksimaciju za broj Ojlerovih ciklusa u grafu, iako još uvek nema dokaza za ovu činjenicu (čak i za grafove ograničenih stepena).

Specijalni slučajevi

Asimptotsku formulu za broj Ojlerovih ciklusa u kompletnom grafu su odredili Makej i Robinson (1995):^[11]

ec(K_{n})=2^{(n+1)/2}\pi ^{1/2}e^{-n^{2}/2+11/12}n^{(n-2)(n+1)/2}{\bigl (}1+O(n^{-1/2+\epsilon }){\bigr )}.

Sličnu formulu je kasnije dobio M. I. Isaev (2009) za kompletne bipartitivne grafove:^[12]

ec(K_{n,n})=(n/2-1)!^{2n}2^{n^{2}-n+1/2}\pi ^{-n+1/2}n^{n-1}{\bigl (}1+O(n^{-1/2+\epsilon }){\bigr )}.

Primene

Ojlerovi putevi se koriste u bioinformatici za rekonstrukciju DNK sekvence od njenih fragmenata.^[13] Oni se takođe koriste u dizajnu CMOS kola, da pronađe optimalan logički redosled.^[14] Postoji nekoliko algoritama za obradu drveta , koji se oslanjaju na Ojlerov put drveta (gde se svaka grana vidi kao par lukova).^[15]^[16]

Vidi još

Ojlerov matroid, apstraktna generalizacija Ojlerovih grafova
Pet soba zagonetka
Lema o rukovanju, dokazao Ojler u originalnom članku, pokazuje da bilo koji neusmereni povezani graf ima paran broj čvorova neparnog stepena
Hamiltonov put – put koji posećuje svaki čvor tačno jednom
Problem pregleda staze, pronalaženje najkraćeg puta koji posećuje sve grane, ponavljajući ivice, ako Ojlerov put ne postoji.
Veblenova teorema, da grafovi sa čvorovima parnog stepena mogu biti podeljeni na cikluse disjunktnih grana, bez obzira na njihovu povezanost

Reference

^ N. L. Biggs; E. K. Lloyd; R. J. Wilson (1976). Graph Theory 1736–1936. Oxford: Clarendon Press. str. 8–9. ISBN 978-0-19-853901-8.
^ C. L. Mallows, N. J. A. Sloane (1975). „Two-graphs, switching classes and Euler graphs are equal in number”. SIAM Journal on Applied Mathematics. 28 (4): 876—880. JSTOR 2100368. doi:10.1137/0128070.
^ ^a ^b Some people reserve the terms path and cycle to mean non-self-intersecting path and cycle.
^ Jun-ichi Yamaguchi, Introduction of Graph Theory.
^ Schaum's outline of theory and problems of graph theory By V. K. Balakrishnan [1].
^ Schrijver, A. (1983), „Bounds on the number of Eulerian orientations”, Combinatorica, 3 (3–4): 375—380, MR 729790, S2CID 13708977, doi:10.1007/BF02579193
^ Fleury, M. (1883), „Deux problèmes de Géométrie de situation”, Journal de mathématiques élémentaires, 2nd ser. (na jeziku: French), 2: 257—261
^ Thorup 2000
^ Fleischner, Herbert (1991). „X.1 Algorithms for Eulerian Trails”. Eulerian Graphs and Related Topics: Part 1, Volume 2. Annals of Discrete Mathematics. 50. Elsevier. str. X.1—13. ISBN 978-0-444-89110-5.
^ Brightwell & Winkler, "Note on Counting Eulerian Circuits", 2004.
^ Brendan McKay and Robert W. Robinson, Asymptotic enumeration of eulerian circuits in the complete graph, Combinatorica, 10 (1995), no. 4, 367–377.
^ M.I. Isaev (2009). „Asymptotic number of Eulerian circuits in complete bipartite graphs”. Proc. 52-nd MFTI Conference. Moscow: 111—114.
^ Pevzner, Pavel A.; Tang, Haixu; Waterman, Michael S. (2001). „An Eulerian trail approach to DNA fragment assembly”. Proceedings of the National Academy of Sciences of the United States of America. 98 (17): 9748—9753. Bibcode:2001PNAS...98.9748P. PMC 55524  . PMID 11504945. doi:10.1073/pnas.171285098  .
^ Roy, Kuntal (2007). „Optimum Gate Ordering of CMOS Logic Gates Using Euler Path Approach: Some Insights and Explanations”. Journal of Computing and Information Technology. 15 (1): 85—92. doi:10.2498/cit.1000731.
^ Tarjan, Robert E.; Vishkin, Uzi (1985). „An efficient parallel biconnectivity algorithm”. SIAM Journal on Computing. 14 (4): 862—874. S2CID 7231609. doi:10.1137/0214061.
^ Berkman, Omer; Vishkin, Uzi (1994). „Finding level-ancestors in trees”. J. Comput. Syst. Sci. 2. 48 (2): 214—230. doi:10.1016/S0022-0000(05)80002-9.

Literatura

Fleischner, Herbert (1991). „X.1 Algorithms for Eulerian Trails”. Eulerian Graphs and Related Topics: Part 1, Volume 2. Annals of Discrete Mathematics. 50. Elsevier. str. X.1—13. ISBN 978-0-444-89110-5.
N. L. Biggs; E. K. Lloyd; R. J. Wilson (1976). Graph Theory 1736–1936. Oxford: Clarendon Press. str. 8–9. ISBN 978-0-19-853901-8.
Euler, L., "Solutio problematis ad geometriam situs pertinentis", Comment. Academiae Sci. I. Petropolitanae 8 (1736). pp. 128.–140.
Hierholzer, Carl; Wiener, Chr (1873). „Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren”. Mathematische Annalen. 6: 30—32. S2CID 119885172. doi:10.1007/BF01442866. .
Lucas, E., Récréations Mathématiques IV, Paris, 1921
Fleury, "Deux problemes de geometrie de situation", Journal de mathematiques elementaires (1883). pp. 257.–261.
Thorup, Mikkel (2000). „Near-optimal fully-dynamic graph connectivity”. Proceedings of the thirty-second annual ACM symposium on Theory of computing. str. 343–350. ISBN 1581131844. S2CID 128282. doi:10.1145/335305.335345.
W. T. Tutte and C. A. B. Smith (1941) "On Unicursal Paths in a Network of Degree 4", American Mathematical Monthly 48: 233–237.

Spoljašnje veze

Diskusija prvih pomena Flerijevog algoritma.
Ojlerov put u Enciklopediji matematike.

[1] N. L. Biggs; E. K. Lloyd; R. J. Wilson (1976). Graph Theory 1736–1936. Oxford: Clarendon Press. str. 8–9. ISBN 978-0-19-853901-8.

[2] C. L. Mallows, N. J. A. Sloane (1975). „Two-graphs, switching classes and Euler graphs are equal in number”. SIAM Journal on Applied Mathematics. 28 (4): 876—880. JSTOR 2100368. doi:10.1137/0128070.

[pathcycle-3] Some people reserve the terms path and cycle to mean non-self-intersecting path and cycle.

[4] Jun-ichi Yamaguchi, Introduction of Graph Theory.

[5] Schaum's outline of theory and problems of graph theory By V. K. Balakrishnan [1].

[6] Schrijver, A. (1983), „Bounds on the number of Eulerian orientations”, Combinatorica, 3 (3–4): 375—380, MR 729790, S2CID 13708977, doi:10.1007/BF02579193

[7] Fleury, M. (1883), „Deux problèmes de Géométrie de situation”, Journal de mathématiques élémentaires, 2nd ser. (na jeziku: French), 2: 257—261

[8] Thorup 2000

[9] Fleischner, Herbert (1991). „X.1 Algorithms for Eulerian Trails”. Eulerian Graphs and Related Topics: Part 1, Volume 2. Annals of Discrete Mathematics. 50. Elsevier. str. X.1—13. ISBN 978-0-444-89110-5.

[10] Brightwell & Winkler, "Note on Counting Eulerian Circuits", 2004.

[11] Brendan McKay and Robert W. Robinson, Asymptotic enumeration of eulerian circuits in the complete graph, Combinatorica, 10 (1995), no. 4, 367–377.

[12] M.I. Isaev (2009). „Asymptotic number of Eulerian circuits in complete bipartite graphs”. Proc. 52-nd MFTI Conference. Moscow: 111—114.

[13] Pevzner, Pavel A.; Tang, Haixu; Waterman, Michael S. (2001). „An Eulerian trail approach to DNA fragment assembly”. Proceedings of the National Academy of Sciences of the United States of America. 98 (17): 9748—9753. Bibcode:2001PNAS...98.9748P. PMC 55524  . PMID 11504945. doi:10.1073/pnas.171285098  .

[14] Roy, Kuntal (2007). „Optimum Gate Ordering of CMOS Logic Gates Using Euler Path Approach: Some Insights and Explanations”. Journal of Computing and Information Technology. 15 (1): 85—92. doi:10.2498/cit.1000731.

[15] Tarjan, Robert E.; Vishkin, Uzi (1985). „An efficient parallel biconnectivity algorithm”. SIAM Journal on Computing. 14 (4): 862—874. S2CID 7231609. doi:10.1137/0214061.

[16] Berkman, Omer; Vishkin, Uzi (1994). „Finding level-ancestors in trees”. J. Comput. Syst. Sci. 2. 48 (2): 214—230. doi:10.1016/S0022-0000(05)80002-9.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]