Eulerovská cesta - Eulerian path

Multigraf obou Konigsberg Bridges a pět puzzle místnosti více než dvou lichých vrcholy (oranžově), a tak nejsou Eulerian a tudíž hádanky nemají žádné řešení.

Každý vrchol tohoto grafu má sudý stupeň . Jedná se tedy o eulerovský graf. Po hranách v abecedním pořadí vznikne eulerovský obvod/cyklus.

V teorii grafů je Eulerianova stezka (nebo Eulerianova cesta ) stezka v konečném grafu, která navštíví každý okraj přesně jednou (což umožňuje revizi vrcholů). Podobně eulerovský okruh nebo eulerovský cyklus je eulerovská stezka, která začíná a končí na stejném vrcholu . Poprvé je probral Leonhard Euler při řešení slavného problému Sedm mostů Königsberg v roce 1736. Problém lze matematicky vyjádřit takto:

Je vzhledem k grafu na obrázku možné sestrojit cestu (nebo cyklus ; tj. Cestu začínající a končící na stejném vrcholu), která navštíví každou hranu přesně jednou?

Euler dokázal, že nezbytnou podmínkou existence eulerovských obvodů je, že všechny vrcholy v grafu mají sudý stupeň , a bez důkazu uvedl, že spojené grafy se všemi vrcholy sudého stupně mají eulerovský obvod. První úplný důkaz tohoto posledního tvrzení zveřejnil posmrtně v roce 1873 Carl Hierholzer . Toto je známé jako Eulerova věta:

Propojený graf má Eulerův cyklus právě tehdy, pokud má každý vrchol sudý stupeň.

Termín eulerovský graf má v teorii grafů dva společné významy. Jeden význam je graf s Eulerianovým okruhem a druhý je graf s každým vrcholem sudého stupně. Tyto definice se shodují pro spojené grafy.

Pro existenci eulerských stezek je nutné, aby nula nebo dva vrcholy měly lichý stupeň; to znamená, že Königsbergův graf není Eulerian. Pokud neexistují žádné vrcholy lichého stupně, jsou všechny Eulerianovy stezky obvody. Pokud existují přesně dva vrcholy lichého stupně, všechny eulerovské stezky začínají na jednom z nich a končí na druhém. Graf, který má eulerovskou stopu, ale nemá eulerovský okruh, se nazývá poloeuleriánský .

Definice

Eulerian stezka , nebo Euler chůze v undirected grafu je chůze, která využívá každou hranu právě jednou. Pokud taková procházka existuje, nazývá se graf traversable nebo semi-eulerian .

Eulerian cyklus , Eulerian obvod nebo Euler prohlídka v undirected grafu je cyklus , který používá všechny okraje právě jednou. Pokud takový cyklus existuje, nazývá se graf Eulerian nebo unicursal . Termín „eulerovský graf“ je také někdy používán v slabším smyslu k označení grafu, kde každý vrchol má sudý stupeň. Pro konečně spojené grafy jsou tyto dvě definice ekvivalentní, zatímco případně nespojený graf je eulerovský v slabším slova smyslu právě tehdy, pokud má každá připojená komponenta eulerovský cyklus.

U směrovaných grafů musí být „cesta“ nahrazena směrovanou cestou a „cyklus“ s nasměrovaným cyklem .

Definice a vlastnosti eulerských stezek, cyklů a grafů platí také pro multigrafy .

Eulerian orientace z undirected grafu G je přiřazení směru ke každému okraji G tak, že se v každém vrcholu V se indegree z V rovná outdegree z V . Taková orientace existuje pro jakýkoli neorientovaný graf, ve kterém má každý vrchol sudý stupeň, a lze jej nalézt vytvořením Eulerovy cesty v každé připojené složce G a následným orientováním okrajů podle trasy. Každá eulerovská orientace připojeného grafu je silná orientace , orientace, která činí výsledný směrovaný graf silně propojeným .

Vlastnosti

Neorientovaný graf má eulerovský cyklus právě tehdy, pokud má každý vrchol sudý stupeň a všechny jeho vrcholy s nenulovým stupněm patří k jedné spojené složce .
Neorientovaný graf lze rozložit na cykly nesouvislé hrany právě tehdy, pokud všechny jeho vrcholy mají sudý stupeň. Graf má tedy eulerovský cyklus právě tehdy, pokud jej lze rozložit na cykly nesouvislé s hranami a jeho nenulové stupně vrcholy patří k jedné propojené komponentě.
Neorientovaný graf má eulerovskou stopu právě tehdy, když přesně nula nebo dva vrcholy mají lichý stupeň a všechny jeho vrcholy s nenulovým stupněm patří k jedné připojené komponentě
Směrovaný graf má eulerovský cyklus právě tehdy, pokud má každý vrchol stejný stupeň a stupeň a všechny jeho vrcholy s nenulovým stupněm patří k jedné silně spojené složce . Ekvivalentně má směrovaný graf eulerovský cyklus právě tehdy, pokud jej lze rozložit na směrované cykly nesouvislé s hranou a všechny jeho vrcholy s nenulovým stupněm patří k jedné silně propojené komponentě.
Směrovaný graf má eulerovskou stopu právě tehdy, pokud má maximálně jeden vrchol ( mimo stupeň )-( ve stupni ) = 1, nejvýše jeden vrchol má (stupeň)-(stupeň mimo) = 1, každý jiný vrchol má stejný stupeň stupně a stupeň out a všechny jeho vrcholy s nenulovým stupněm patří k jedné spojené složce podkladového neorientovaného grafu.

Stavba eulerských stezek a okruhů

Použití Eulerianových stezek k řešení hádanek zahrnujících kreslení tvaru souvislým tahem:
1. Protože logická hra Haus vom Nikolaus má dva liché vrcholy (oranžový), musí stezka začínat na jednom a končit na druhém.
2. Annie Pope's se čtyřmi lichými vrcholy nemá řešení.
3. Pokud neexistují liché vrcholy, stezka může začít kdekoli a tvoří eulerovský cyklus.
4. Volné konce jsou považovány za vrcholy stupně 1.

Fleuryho algoritmus

Fleuryho algoritmus je elegantní, ale neefektivní algoritmus z roku 1883. Vezměme si graf, o kterém je známo, že má všechny hrany ve stejné složce a nejvýše dva vrcholy lichého stupně. Algoritmus začíná na vrcholu lichého stupně, nebo pokud graf žádný nemá, začíná libovolně zvoleným vrcholem. V každém kroku zvolí další hranu v cestě, jejíž odstranění by graf neodpojilo, pokud taková hrana neexistuje, v takovém případě vybere zbývající hranu vlevo v aktuálním vrcholu. Poté se přesune na druhý koncový bod této hrany a hranu odstraní. Na konci algoritmu nezůstávají žádné hrany a posloupnost, ze které byly okraje vybrány, tvoří eulerovský cyklus, pokud graf nemá žádné vrcholy lichého stupně, nebo eulerovskou stopu, pokud existují právě dva vrcholy lichého stupně.

Zatímco pohyb grafu ve Fleuryho algoritmu je lineární v počtu hran, tj . Musíme také zohlednit složitost detekce mostů . Pokud máme po odstranění každé hrany znovu spustit Tarjanův lineární algoritmus pro vyhledávání mostů času, Fleuryho algoritmus bude mít časovou složitost . Algoritmus dynamického hledání mostů Thorup (2000) umožňuje toto vylepšit , ale stále je výrazně pomalejší než alternativní algoritmy. ${\ displaystyle O (| E |)}$ ${\ displaystyle O (| E |^{2})}$ ${\ Displaystyle O (| E | \ cdot \ log ^{3} | E | \ cdot \ log \ log | E |)}$

Hierholzerův algoritmus

Hierholzerův dokument z roku 1873 poskytuje jinou metodu pro hledání Eulerových cyklů, která je účinnější než Fleuryho algoritmus:

Vyberte libovolný počáteční vrchol v a sledujte stopu hran z tohoto vrcholu, dokud se nevrátíte do v . Není možné se zaseknout na jiném vrcholu než v , protože sudý stupeň všech vrcholů zajišťuje, že když stezka vstoupí do jiného vrcholu w , musí existovat nepoužitý okraj opouštějící w . Takto vytvořená prohlídka je uzavřená prohlídka, ale nemusí pokrývat všechny vrcholy a hrany počátečního grafu.
Dokud existuje vrchol u, který patří k aktuální prohlídce, ale který má sousední hrany, které nejsou součástí prohlídky, začněte další trasu od u , sledujte nepoužívané hrany, dokud se nevrátíte do u , a připojte se k takto vytvořené prohlídce k předchozí prohlídka.
Protože předpokládáme, že je původní graf propojený , opakováním předchozího kroku se vyčerpají všechny hrany grafu.

Použitím datové struktury, jako je dvojitě propojený seznam, k udržení sady nepoužitých hran dopadajících na každý vrchol, k udržení seznamu vrcholů na aktuální trase, které mají nepoužité hrany, a k zachování samotné prohlídky, jednotlivých operací algoritmus (zjištění nepoužité hrany ukončení každého vrcholu, najít nové počáteční vrchol na cestě, a spojující dvě prohlídky, které sdílejí vrchol) může být proveden v konstantním čase každé, takže celková algoritmus má lineární čas , . ${\ displaystyle O (| E |)}$

Tento algoritmus lze také implementovat s deque . Protože je možné se zaseknout pouze tehdy, když deque představuje uzavřenou trasu, měli byste deque otáčet tak, že odstraníte hrany z ocasu a přidáte je k hlavě, dokud se neodlepí, a poté pokračujte, dokud nebudou zohledněny všechny hrany. To také vyžaduje lineární čas, protože počet provedených otočení není nikdy větší než (intuitivně se všechny „špatné“ hrany přesunou do hlavy, zatímco nové okraje se přidají do ocasu) ${\ displaystyle | E |}$

Ortografické projekce a Schlegelovy diagramy s hamiltonovskými cykly vrcholů pěti platonických těles - pouze osmistěn má eulerovskou dráhu nebo cyklus, prodloužením dráhy tečkovanou

Počítání eulerovských obvodů

Problémy se složitostí

Počet eulerovských obvodů v digrafech lze vypočítat pomocí takzvané NEJLEPŠÍ věty pojmenované podle de B ruijna , van Aardenne- E hrenfest , S mith a T utte . Vzorec uvádí, že počet eulerovských obvodů v digrafu je součinem určitých faktoriálů stupně a počtu zakořeněných arborescencí . Ten lze vypočítat jako determinant pomocí maticové stromové věty , což dává polynomiální časový algoritmus.

NEJLEPŠÍ věta je v této podobě poprvé uvedena v „poznámce přidané na důkaz“ k papíru Aardenne-Ehrenfest a de Bruijn (1951). Původní důkaz byl bijektivní a generalizoval de Bruijnovy sekvence . Je to variace na dřívější výsledek Smitha a Tutteho (1941).

Počítání počtu eulerovských obvodů na neorientovaných grafech je mnohem obtížnější. Tento problém je známý jako #P-úplný . V pozitivním směru se předpokládá, že přístup Markovského řetězce Monte Carlo prostřednictvím Kotzigových transformací (zavedený Antonem Kotzigem v roce 1968) poskytuje ostrou aproximaci počtu eulerských obvodů v grafu, ačkoli zatím neexistuje žádný důkaz tohoto fakt (i pro grafy ohraničeného stupně).

Speciální případy

Asymptotická vzorec pro počet Eulerovské obvodů v kompletním grafu byla stanovena McKay a Robinson (1995):

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

Podobný vzorec později získal MI Isaev (2009) pro kompletní bipartitní grafy :

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

Aplikace

Eulerianovy stezky se používají v bioinformatice k rekonstrukci sekvence DNA z jejích fragmentů. Používají se také v návrhu obvodu CMOS k nalezení optimálního uspořádání logické brány . Existuje několik algoritmů pro zpracování stromů, které se spoléhají na Eulerovu prohlídku stromu (kde je každá hrana považována za dvojici oblouků). Sekvence de Bruijn mohou být konstruovány jako eulerské stopy de Bruijnových grafů .

V nekonečných grafech

Nekonečný graf se všemi vrcholovými stupni rovnajícími se čtyřem, ale bez eulerovské přímky

V nekonečném grafu odpovídá konceptu Eulerian Trail nebo Eulerian Cycle Eulerian Line, dvojitě nekonečná stopa, která pokrývá všechny okraje grafu. K existenci takové stopy nestačí, aby byl graf propojen a aby všechny stupně vrcholů byly sudé; například zobrazený nekonečný Cayleyův graf , se všemi vrcholovými stupni rovnými čtyřem, nemá žádnou Eulerianovu čáru. Nekonečné grafy, které obsahují eulerovské čáry, charakterizovaly Erdõs, Grünwald & Weiszfeld (1936) . Aby měl nekonečný graf nebo multigraf $G$ Eulerianovu čáru, je nutné a dostatečné, aby byly splněny všechny následující podmínky:

$G$ je připojeno.
$G$ má spočítatelné sady vrcholů a hran.
$G$ nemá žádné vrcholy (konečného) lichého stupně.
Odstranění jakéhokoli konečného podgrafu $S$ z $G$ ponechá ve zbývajícím grafu nejvýše dvě nekonečné spojené součásti a pokud má $S$ na každém ze svých vrcholů sudý stupeň, pak odebrání listů $S$ přesně jedné nekonečně spojené součásti.

Viz také

Eulerian matroid , abstraktní generalizace eulerovských grafů
Puzzle s pěti místnostmi
Lemma potřesení rukou, které Euler prokázal ve svém původním článku, ukazuje, že jakýkoli neorientovaný spojený graf má sudý počet vrcholů lichého stupně
Hamiltonovská cesta - cesta, která navštíví každý vrchol přesně jednou.
Problém s kontrolou trasy , hledejte nejkratší cestu, která navštíví všechny hrany, případně opakující se hrany, pokud neexistuje eulerská cesta.
Veblenova věta , že grafy s rovnoměrným vrcholem lze rozdělit do cyklů nesouvislých hran bez ohledu na jejich konektivitu

Poznámky

Reference

Erdõs, Pál ; Grünwald, Tibor ; Weiszfeld, Endre (1936), „Végtelen gráfok Euler vonalairól“ [O Eulerových liniích nekonečných grafů] (PDF) , Mat. Opravit. Lapok (v maďarštině), 43 : 129–140. Přeloženo jako Erdős, P .; Grünwald, T .; Vázsonyi, E. (1938), „Über Euler-Linien unendlicher Graphen“ [Eulerian lines in infinite graphs] (PDF) , J. Math. Fyz. (v němčině), 17 (1–4): 59–75, doi : 10,1002/sapm193817159.
Euler, L., „ Solutio problematis ad geometriam situs pertinentis “, Komentář. 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 , S2CID 119885172.
Lucas, E., Récréations Mathématiques IV , Paříž, 1921.
Fleury, „Deux problemes de geometrie de situácia“, Journal de mathematiques elementaires (1883), 257–261.
T. van Aardenne-Ehrenfest a NG de Bruijn (1951) „Obvody a stromy v orientovaných lineárních grafech“, Simon Stevin 28: 203–217.
Thorup, Mikkel (2000), „Téměř optimální plně dynamická grafická konektivita“, Proc. 32. sympozium ACM o teorii výpočetní techniky , s. 343–350, doi : 10,1145/335305,335345 , S2CID 128282
WT Tutte a CAB Smith (1941) „Na unicursálních cestách v síti stupně 4“, American Mathematical Monthly 48: 233–237.

Languages

In other projects