Ојлеров пут

Из Википедије, слободне енциклопедије
Кенигсбергови мостови. Овај граф није Ојлеров, стога, решење не постоји.
Свака чвор овог графа има паран степен. Дакле, ово је Ојреров граф. Праћење грана у абецедном редоследу даје Ојлеров циклус.

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

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

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

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

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

Дефиниција[уреди]

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

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

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

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

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

Особине[уреди]

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

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

Флеријев алгоритам[уреди]

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

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

Хирхолцеров алгоритам[уреди]

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

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

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

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

Проблеми сложености[уреди]

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

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

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

Специјални случајеви[уреди]

Асимптотску формулу за број Ојлерових циклуса у комплетном графу су одредили Макеј и Robinson (1995.):[10]


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) за комплетне бипартитивне графове:[11]


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).

Примене[уреди]

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

Види још[уреди]

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

Литература[уреди]

  1. N. L. Biggs, E. K. Lloyd and R. J. Wilson, Graph Theory 1736–1936, Clarendon Press, Oxford, 1976, 8–9, ISBN 0-19-853901-0.
  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. doi:10.1137/0128070. JSTOR 2100368 
  3. 3,0 3,1 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, doi:10.1007/BF02579193, MR 729790 .
  7. Fleury, M. (1883), „Deux problèmes de Géométrie de situation” (на French), Journal de mathématiques élémentaires, 2nd ser. 2: 257–261 .
  8. Fleischner, Herbert (1991), „X.1 Algorithms for Eulerian Trails”, Eulerian Graphs and Related Topics: Part 1, Volume 2, Annals of Discrete Mathematics, 50, Elsevier, pp. X.1–13, ISBN 978-0-444-89110-5 
  9. Brightwell and Winkler, "Note on Counting Eulerian Circuits", 2004.
  10. Brendan McKay and Robert W. Robinson, Asymptotic enumeration of eulerian circuits in the complete graph, Combinatorica, 10 (1995), no. 4, 367–377.
  11. M.I. Isaev (2009). „Asymptotic number of Eulerian circuits in complete bipartite graphs” (на Russian). Proc. 52-nd MFTI Conference (Moscow): 111–114 
  12. 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. doi:10.1073/pnas.171285098. PMC 55524. PMID 11504945 
  13. 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 
  14. Tarjan, Robert E.; Vishkin, Uzi (1985). „An efficient parallel biconnectivity algorithm”. SIAM Journal on Computing 14 (4): 862–874. doi:10.1137/0214061 
  15. Berkman, Omer; Vishkin, Uzi (Apr 1994). „Finding level-ancestors in trees”. J. Comput. Syst. Sci.. 2 48: 214–230. doi:10.1016/S0022-0000(05)80002-9 

Референце[уреди]

  • Euler, L., "Solutio problematis ad geometriam situs pertinentis", Comment. Academiae Sci. I. Petropolitanae 8 (1736), 128–140.
  • Hierholzer, Carl (1873), "Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren", Mathematische Annalen 6 (1): 30–32, 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), 257–261.
  • Thorup, Mikkel (2000), "Near-optimal fully-dynamic graph connectivity", Proc. 32nd ACM Symposium on Theory of Computing, pp. 343–350, 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.

Спољашње везе[уреди]