Ојлеров пут

У теорији графова, Ојлеров пут је пут у оквиру графа, који обилази сваку грану тачно једном. На сличан начин, Ојлеров циклус је пут који почиње и завршава се у истом чвору. Леонард Ојлер је први дискутовао о њима при решавању познатих седам Кенигсбергових мостова, 1736. године. Проблем може бити формулисан математички:

С обзиром на граф на слици, да ли је могуће да се изгради пут (или циклус, то је пут који почиње и завршава се у једном истом чвору), који посети сваку грану тачно једном?

Ојлер је показао да је неопходан услов, за постојање Ојлеровог циклуса, да су сви чворови у графу парног степена, и рекао је, без доказа, да повезан граф код којег су сви чворови парног степена јесте Ојлеров граф. Први комплетан доказ ове последње изјаве објавио је, постхумно 1873. години, Карл Хирхолцер.^[1]

Појам Oјлеров граф има два општа значења у теорији графова. Прво - то је граф који садржи Ојлеров пут, а друго - граф, чији су сви чворови парног степена. Ове дефиниције се поклапају за повезане графове.^[2]

За постојање Ојлеровог пута неопходно је да су нула или два чвора непарног степена; то значи да Кенигсбергов граф није Ојлеров. Ако не постоје чворови непарног степена, сви Ојлерови путеви су циклуси. Ако постоје тачно два чвора непарног степена, сви Ојлерови путеви почињу у једном од чворова и завршавају се у другом. Граф који има Ојлеров пут, али не и Ојлеров циклус се назива полу-Ојлеров.

Дефиниција

Ојлеров пут,^[3] у неусмереном графу, је пут, који користи сваку грану тачно једном. Ако овај пут постоји, онда се граф зове полу-Ојлеров.^[4]

Ојлеров циклус,^[3] у неусмереном графу, је циклус , који користи сваку грану тачно једном. Ако такав циклус постоји, онда се граф зове Ојлеров.^[5] Термин "Ојлеров граф" се понекад користи у слабијем значењу да означи граф, где је сваки чвор парног степена. За крајње повезане графове ове две дефиниције су еквивалентне, иако, неповезан граф је Ојлер у слабијем значењу, ако и само ако свака компонента повезаности има Ојлеров циклус.

За усмерене графове, "пут" треба заменити на усмерен пут и "циклус" са усмерен циклус.

Дефиниција и особине Ојлерових путева, циклуса и графова важе и за мултиграфове.

Ојлерова оријентација неусмереног графа је уступање правца сваке гране у графу Г тако да је за сваки чвор в, улазни степен од в једнак излазном степену од в. Таква оријентација постоји за било који неусмерени граф, у којем је сваки чвор парног степена, и може се наћи изградњом Ојлеровог пута у сваку компоненту повезаности од Г и циљањем ивице на основу пута.^[6] Свака Ојлерова оријентација повезаног графа је јака оријентација, оријентација која чини добијени усмерени граф јако повезан.

Особине

Неусмерени граф има Ојлеров циклус, ако и само ако сваки чвор има парни степен, и сви чворови са не-нула степеном припадају једној компоненти повезиваности.
Неусмерени граф може да се растави на циклусе дисјунктних чворова, ако и само ако су сви њихови чворови парног степена. Дакле, граф има Ојлеров циклус, ако и само ако он може да се растави на циклусе дисјунктних чворова и његови чворови не-нула степена припадају једној компоненти повезаности.
Неусмерени граф има Ојлеров пут ако и само ако тачно нула или два чвора су непарног степена, и ако сви чворови нултног степена припадају једној компоненти повезаности.
Усмерени граф има Ојлеров циклус, ако и само ако сваки чвор има једнаке улазне и излазне степене и сви чворови не-нултог степена припадају једној чврстој компоненти повезаности. Еквивалентно, усмерен граф има Ојлеров циклус, ако и само ако он може да буде разложен на циклусе дисјунктних чворова и сви његови чворови не-нултог степена припадају једној чврстој компоненти повезаности.
Усмерени граф има Ојлеров пут, ако, и само ако највише један чвор има (излазни степен) − (улазни степен) = 1, највише један чвор има (улазни степен) − (излазни степен) = 1, сваки други чвор има једнаке улазне и излазне степене, и сви чворови не-нултог степена припадају једној компоненти повезаности неусмереног графа.

Конструкција Ојлерових путева и циклуса

Флеријев алгоритам

Флеријев алгоритам је елегантан али неефикасан алгоритам, који датира из 1883.^[7] Уочити граф који има све чворове у истој компоненту и тачно два чвора непарног степена. Алгоритам почиње у једном од чворова непарног степена, или, ако га граф нема, почиње у произвољно изабраном чвору. На сваком кораку он бира следећу ивицу на путу, чијим уклањањем граф остаје повезан, а ако не постоји таква грана, у овом случају, он узима преостале гране у односу на тренутну. Он затим прелази на друге чворове и уклања изабрану грану. На крају алгоритма нема грана, и низ грана које су редом изабране формира Ојлеров циклус, ако у графу нема чворова непарног степена, или Ојлеров пут, ако постоје тачно два чвора непарног степена.

Док избегавање графа у Флеријевом алгоритму има линеарну зависност од броја грана, односно О(|Е|), такође треба узети у обзир сложеност откривања мостова. Ако желимо да поново покренете Тарјанов алгоритам за претрагу моста за линеарно време, након уклањања сваке гране, Флеријев алгоритам ће имати временску сложеност О(|Е|²).^[8] динамички алгоритам за претрагу моста омогућава да буде побољшана $O(|E|\log ^{3}|E|\log \log |E|)$ , али је и даље знатно спорији него алтернативни алгоритми.

Хирхолцеров алгоритам

Хирхолцеров чланак из 1873. који пружа другачији начин за проналажење Ојлеровог циклуса, је ефикаснији од Флеријевог алгоритма:

Изабрати било који почетни чвор в, и пратити пут грана од тог чвора, па све до повратка у в. Није могуће да се заглави на било ком чвору осим у в, јер парни степен свих чворова гарантује да када је следећа стаза г на путу тамо мора да буде слободна грана, остављајући г. Пут формиран на тај начин је зачарани круг, али не може да покрије све чворове и гране оригиналног графа.
Докле год постоји чвор у, који припада текућем путу, али има суседних грана који нису део пута, покренути још једанпут од у, користити следеће неискоришћене гране, док се не вратимо на у, и придружити пут, формиран на овај начин, на претходни пут.

Користећи структуру података, као што је двоструко повезана листа, за одржавање скупа неискоришћених грана инцидентних са сваким чвором, за одржавање листе чворова на тренутном путу које имају неискоришћене гране, и за одржавање самог пута, појединачне операције алгоритма (проналажење неискоришћених грана за излаз сваког чвора, и повезивање два пута који деле грану) може да буде извршена за константно време сваки пут, дакле, за општи алгоритам је потребно линеарно време, $O(|E|)$ .^[9]

Бројање Ојлерових циклуса

Проблеми сложености

Број Ојлерових циклуса у усмереним графовима може се израчунати помоћу тзв. БЕСТ теореме, назване у част де Брујин, Ван Ардене-Еренфест, Самит и Туте. Формула гласи да је број Ојлерових циклуса у усмереном графу производ степена факторијела и детерминанте, преко теореме матрице стабла, дајући алгоритам (полиномијалне временске сложености).

БЕСТ теорема, први пут формулисана у таквом облику у "Напомена објављена у доказу" од стране Ардене-Еренфеста и у чланку де Брујина (1951). Оригинални доказ је бијективан и генерализовао де Брујинове низове. Он је варијација на ранијем резултату Смита и Тутеа (1941).

Бројање Ојлерових циклуса неусмереног графа је много теже. Овај проблем је #П-комплетан.^[10] У позитивном смеру, Марков ланац Монте Карло приступ, по Коциг конверзијама (увео Антон Коциг 1968. године), верује се да дају оштру апроксимацију за број Ојлерових циклуса у графу, иако још увек нема доказа за ову чињеницу (чак и за графове ограничених степена).

Специјални случајеви

Асимптотску формулу за број Ојлерових циклуса у комплетном графу су одредили Макеј и 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 )}.

Сличну формулу је касније добио М. И. Исаев (2009) за комплетне бипартитивне графове:^[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 )}.

Примене

Ојлерови путеви се користе у биоинформатици за реконструкцију ДНК секвенце од њених фрагмената.^[13] Они се такође користе у дизајну CMOS кола, да пронађе оптималан логички редослед.^[14] Постоји неколико алгоритама за обраду дрвета , који се ослањају на Ојлеров пут дрвета (где се свака грана види као пар лукова).^[15]^[16]

Види још

Ојлеров матроид, апстрактна генерализација Ојлерових графова
Пет соба загонетка
Лема о руковању, доказао Ојлер у оригиналном чланку, показује да било који неусмерени повезани граф има паран број чворова непарног степена
Хамилтонов пут – пут који посећује сваки чвор тачно једном
Проблем прегледа стазе, проналажење најкраћег пута који посећује све гране, понављајући ивице, ако Ојлеров пут не постоји.
Вебленова теорема, да графови са чворовима парног степена могу бити подељени на циклусе дисјунктних грана, без обзира на њихову повезаност

Референце

^ N. L. Biggs; E. K. Lloyd; R. J. Wilson (1976). Graph Theory 1736–1936. Oxford: Clarendon Press. стр. 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.
^ ^а ^б 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. (на језику: 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. стр. 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.

Литература

Fleischner, Herbert (1991). „X.1 Algorithms for Eulerian Trails”. Eulerian Graphs and Related Topics: Part 1, Volume 2. Annals of Discrete Mathematics. 50. Elsevier. стр. 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. стр. 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. стр. 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.

Спољашње везе

Дискусија првих помена Флеријевог алгоритма.
Ојлеров пут у Енциклопедији математике.

[1] N. L. Biggs; E. K. Lloyd; R. J. Wilson (1976). Graph Theory 1736–1936. Oxford: Clarendon Press. стр. 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. (на језику: 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. стр. 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]