Rruga e Eulerit

Në teorinë e grafeve, një graf Eulerian është një shteg në një graf të fundëm që viziton çdo kulm saktësisht një herë (duke lejuar rishikimin e kulmeve). Në mënyrë të ngjashme,një graf Eulerian fillon dhe mbaron në të njëjtin kulm. Ato u diskutuan për herë të parë nga Leonhard Euler gjatë zgjidhjes së problemit të famshëm “Shtatë Urat e Königsberg” në vitin 1736.

Problemi mund të shprehet matematikisht :

Duke pasur parasysh grafin në imazh, a është e mundur të ndërtohet një rrugë; (d.m.th., një shteg që fillon dhe mbaron në të njëjtin kulm) që viziton çdo kulm saktësisht një herë?

Euleri vërtetoi se një kusht i domosdoshëm për ekzistencën e grafeve Euleriane është që të gjitha kulmet në graf të kenë një shkallë çift, dhe deklaroi pa prova se grafet e lidhura me të gjitha kulmet e shkallës çift kanë një qark Eulerian. Prova e parë e plotë e këtij pretendimi të fundit u botua pas vdekjes në 1873 nga Carl Hierholzer.

Kjo njihet si teorema e Euler-it:

Një graf i lidhur ka një qark Euler nëse çdo kulm ka shkallë çift.

Termi graf Eulerian ka dy kuptime të përbashkëta në teorinë e grafeve:

Një graf me një qark Eulerian
Një graf me çdo kulm të shkallës së njëjtë.

Këto përkufizime përkojnë për grafet e lidhura.

Për ekzistencën e shtigjeve Euleriane është e nevojshme që zero ose dy kulme të kenë një shkallë tek, kjo do të thotë se grafi i Königsberg nuk është Eulerian. Nëse nuk ka kulme të shkallës tek, të gjitha gjurmët Euleriane janë qarqe. Nëse ka saktësisht dy kulme të shkallës tek, të gjitha shtigjet Euleriane fillojnë në njërën prej tyre dhe përfundojnë në tjetrën. Një graf që ka një qark(Qarku është një shteg i mbyllur p.sh. 1->2->6->1) Eulerian por jo një shteg(në të cilin as kulmet dhe as skajet nuk përsëriten) Eulerian quhet gjysmë-Eulerian. Dallimi kryesorë mes rrugës së Euler-it dhe asaj të Hamilton-it është se ajo e Hamiltonit shkon neper çdo kulm ndërsa ajo e Euler-it, ne çdo brinjë.

Definicion

Një gjurmë Eulerian ose ecja e Eulerit në një graf të padrejtuar është një ecje që përdor çdo skaj saktësisht një herë. Nëse ekziston një ecje e tillë, grafiku quhet i përshkueshëm ose gjysmë-eulerian.

Një cikël Eulerian në një graf të padrejtuar është një cikël që përdor çdo kulm saktësisht një herë. Nëse ekziston një cikël i tillë, grafi quhet Eulerian.Termi "graf Eulerian" përdoret gjithashtu ndonjëherë në një kuptim më të dobët për të treguar një graf ku çdo kulm ka shkallë të barabartë. Për grafet e lidhura të fundme, të dy përkufizimet janë ekuivalente, ndërsa një graf ndoshta i palidhur është Eulerian në kuptimin më të dobët nëse çdo komponent i lidhur ka një cikël Eulerian.

Për grafet e drejtuara, "rruga" duhet të zëvendësohet me shtegun e drejtuar dhe "cikli" me cikël të drejtuar.

Përkufizimi dhe vetitë e grafeve Euleriane janë të vlefshme edhe për multigrafët.

Një orientim Eulerian i një grafi të padrejtuar G është një caktim i një drejtimi në secilën skaj të G-së në mënyrë që, në çdo kulm v, shkalla e v-së është e barabartë me shkallën e jashtme të v-së. Një orientim i tillë ekziston për çdo graf të padrejtuar në të cilin çdo kulm ka shkallë të barabartë, dhe mund të gjendet duke ndërtuar një rrugë Euler në çdo komponent të lidhur të G-së dhe më pas duke orientuar skajet sipas rrugës. Çdo orientim Eulerian i një grafi të lidhur është një orientim i fortë, një orientim që e bën grafin e drejtuar që rezulton të lidhet fort.

Vetitë

Një graf i padrejtuar ka një cikël Eulerian nëse çdo kulm ka shkallë çift, dhe të gjitha kulmet e tij me shkallë jo-zero i përkasin një komponenti të vetëm të lidhur.
Një graf i padrejtuar mund të zbërthehet në cikle të shkëputura nga skaji nëse të gjitha kulmet e tij kanë shkallë çift. Pra, një graf ka një cikël Eulerian nëse mund të zbërthehet në cikle të shkëputura nga skajet dhe kulmet e tij me shkallë jo-zero që i përkasin një komponenti të vetëm të lidhur.
Një graf i padrejtuar ka një shteg Euleriane nëse saktësisht zero ose dy kulme kanë shkallë tek, dhe të gjitha kulmet e tij me shkallë jo-zero i përkasin një komponenti të vetëm të lidhur
Një graf i drejtuar ka një cikël Eulerian nëse çdo kulm ka shkallë të barabartë dhe shkallë të jashtme, dhe të gjitha kulmet e tij me shkallë jo-zero i përkasin një komponenti të vetëm të lidhur fort. Në mënyrë ekuivalente, një graf i drejtuar ka një cikël Eulerian nëse ai mund të zbërthehet në cikle të drejtuara nga skajet dhe të gjitha kulmet e tij me shkallë jozero i përkasin një komponenti të vetëm të lidhur fort.
Një graf i drejtuar ka një shteg Eulerian nëse dhe vetëm nëse maksimumi një kulm ka (shkallë të jashtme) − (shkallë të brendshme) = 1, maksimumi një kulm ka (shkallë të brendshme) − (shkallë të jashtme) = 1, çdo kulm tjetër ka shkallë të barabartë në shkallë të brendshme dhe jashtme, dhe të gjitha kulmet e tij me shkallë jozero i përkasin një komponenti të vetëm të lidhur të grafit themelor të padrejtuar.

Numërimi i Qarqeve Euleriane

Çështjet e kompleksitetit

Numri i qarqeve Euleriane në digrafe mund të llogaritet duke përdorur të ashtuquajturën teoremën “BEST”, të quajtur sipas De Bruijn, van Aardenne-Ehrenfest, Smith dhe Tutte. Formula thotë se numri i qarqeve Euleriane në një digraf është produkt i faktorëve të shkallës së caktuar dhe numrit të rrenjëzuar të arboreshencës. Kjo e fundit mund të llogaritet si një përcaktues, nga teorema e pemës së matricës, duke dhënë një algoritëm polinomial kohor.

Teorema BEST është deklaruar fillimisht në këtë formë në një "shënim të shtuar në provë" në punimin Aardenne-Ehrenfest dhe de Bruijn (1951). Prova origjinale ishte bijektive dhe përgjithësoi sekuencat e de Bruijn-it. Është një variacion i një rezultati të mëparshëm nga Smith dhe Tutte (1941).

Numërimi i numrit të qarqeve Euleriane në grafe të padrejtuara është shumë më i vështirë. Ky problem dihet se është #P-complete. Në një drejtim pozitiv, një qasje e zinxhirit Markov Monte Carlo, nëpërmjet transformimeve Kotzig (prezantuar nga Anton Kotzig në 1968) besohet se jep një përafrim të mprehtë për numrin e qarqeve euleriane në një graf, megjithëse ende nuk ka asnjë provë për këtë.

Zbatimet

Shtigjet Euleriane përdoren në bioinformatikë për të rindërtuar sekuencën e ADN-së nga fragmentet e saj.Ato përdoren gjithashtu në dizajnimin e qarkut CMOS për të gjetur një renditje optimale të portës logjike. Ka disa algoritme për përpunimin e pemëve që mbështeten në një rrugë të Euler-it të pemës (ku çdo skaj trajtohet si një palë harqesh).Sekuencat e de Bruijn-it mund të ndërtohen si gjurmë Euleriane të grafëve të de Bruijn-it.

Në një graf të pafundëm

Në një graf të pafundëm, koncepti përkatës për një shteg Eulerian ose një cikël eulerian është një vijë euleriane, një shteg dyfish e pafundme që mbulon të gjitha skajet e grafikut. Nuk mjafton për ekzistencën e një shtegu të tillë që grafi të jetë i lidhur dhe të gjitha shkallët e kulmeve të jenë çift. P.sh. grafi i pafundëm i Cayley i paraqitur, me të gjitha shkallët e kulmeve të barabarta me katër, nuk ka asnjë vijë euleriane. Grafet e pafundëm që përmbajnë linja euleriane u karakterizuan nga Erdõs, Grünwald & Weiszfeld (1936). Që një graf i pafundëm ose shumëgraf G të ketë një vijë euleriane, është e nevojshme dhe e mjaftueshme që të plotësohen të gjitha kushtet e mëposhtme:

G është i lidhur.
G ka grupe të numërueshme kulmesh dhe skajesh.
G nuk ka kulme të shkallës tek (të fundme).
Heqja e çdo nëngrafi të fundëm S nga G lë më së shumti dy komponentë të lidhur pafundësisht në grafin e mbetur, dhe nëse S ka shkallë çift në secilën nga kulmet e tij, atëherë heqja e S lë saktësisht një komponent të pafundëm të lidhur.

Referime

Euler, L., "Solutio problematis ad geometriam situs pertinentis", Comment. Academiae Sci. I. Petropolitanae 8 (1736), 128-140.
Hierholzer, C., "Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechnung zu umfahren", Mathematische Annalen 6 (1873), 30-32.
Lucas, E., Récréations Mathématiques IV, Paris, 1921.
Fleury, "Deux problemes de geometrie de situation", Journal de mathematiques elementaires (1883), 257-261.
^[1]

Linqe

^ e Eulerit, Rruga (2021-10-19). "Eulerian path". Wikipedia (në anglisht).

[1] Eulerit, Rruga (2021-10-19). "Eulerian path". Wikipedia (në anglisht).

[1]