Ścieżka Eulera

Multigrafy zarówno mostów w Królewcu , jak i zagadek z pięcioma pokojami mają więcej niż dwa nieparzyste wierzchołki (na pomarańczowo), a zatem nie są eulerowskie, a zatem zagadki nie mają rozwiązań.

Każdy wierzchołek tego grafu ma stopień parzysty . Jest to zatem graf Eulera. Podążanie za krawędziami w kolejności alfabetycznej daje obwód/cykl Eulera.

W teorii grafów ścieżka Eulera (lub ścieżka Eulera ) to ścieżka w skończonym grafie, która odwiedza każdą krawędź dokładnie raz (pozwalając na ponowne odwiedzanie wierzchołków). Podobnie obwód Eulera lub cykl Eulera to ślad Eulera, który zaczyna się i kończy w tym samym wierzchołku . Zostały one po raz pierwszy omówione przez Leonharda Eulera podczas rozwiązywania słynnego problemu Siedmiu Mostów w Królewcu w 1736 roku. Problem można przedstawić matematycznie w następujący sposób:

Czy biorąc pod uwagę wykres na obrazku, można skonstruować ścieżkę (lub cykl , tj. ścieżkę zaczynającą się i kończącą w tym samym wierzchołku), która przechodzi przez każdą krawędź dokładnie raz?

Euler udowodnił, że warunkiem koniecznym istnienia obwodów Eulera jest to, że wszystkie wierzchołki w grafie mają parzysty stopień , i stwierdził bez dowodu, że połączone grafy ze wszystkimi wierzchołkami parzystego stopnia mają obwód Eulera. Pierwszy pełny dowód tego ostatniego twierdzenia został opublikowany pośmiertnie w 1873 roku przez Carla Hierholzera . Jest to znane jako twierdzenie Eulera:

Spójny graf ma cykl Eulera wtedy i tylko wtedy, gdy każdy wierzchołek ma parzysty stopień.

Termin wykres Eulera ma dwa powszechne znaczenia w teorii grafów. Jedno znaczenie to graf z obwodem Eulera, a drugie to graf z każdym wierzchołkiem parzystego stopnia. Definicje te pokrywają się dla połączonych grafów.

Dla istnienia śladów Eulera konieczne jest, aby zero lub dwa wierzchołki miały stopień nieparzysty; oznacza to, że graf Królewca nie jest eulerowski. Jeśli nie ma wierzchołków nieparzystego stopnia, wszystkie ścieżki Eulera są obwodami. Jeśli istnieją dokładnie dwa wierzchołki nieparzystego stopnia, wszystkie ścieżki Eulera zaczynają się w jednym z nich, a kończą w drugim. Graf, który ma ślad Eulera, ale nie ma obwodu Eulera, nazywa się pół-eulerowskim .

Definicja

Szlak Eulera lub spacer Eulera w grafie nieskierowanym to spacer, który wykorzystuje każdą krawędź dokładnie raz. Jeśli taki spacer istnieje, graf nazywa się przejezdnym lub semi-eulerowskim .

Cykl Eulera , zwany także obwodem Eulera lub trasą Eulera , w grafie nieskierowanym to cykl , w którym każda krawędź jest używana dokładnie raz. Jeśli taki cykl istnieje, graf nazywa się eulerowskim lub jednokursowym . Termin „wykres Eulera” jest czasami używany w słabszym znaczeniu do określenia wykresu, w którym każdy wierzchołek ma parzysty stopień. W przypadku skończonych połączonych grafów te dwie definicje są równoważne, podczas gdy prawdopodobnie niepołączony graf jest eulerowski w słabszym sensie wtedy i tylko wtedy, gdy każdy połączony składnik ma cykl Eulera.

W przypadku grafów skierowanych „ścieżkę” należy zastąpić ścieżką skierowaną , a „cykl” – cyklem skierowanym .

Definicja i właściwości ścieżek, cykli i grafów Eulera obowiązują również dla multigrafów .

Orientacja Eulera grafu nieskierowanego G to takie przypisanie kierunku każdej krawędzi grafu G , że w każdym wierzchołku v stopień wejściowy v jest równy stopniowi zewnętrznemu v . Taka orientacja istnieje dla dowolnego nieskierowanego wykresu, w którym każdy wierzchołek ma parzysty stopień, i można ją znaleźć konstruując trasę Eulera w każdym połączonym składniku G, a następnie ustawiając krawędzie zgodnie z trasą. Każda orientacja eulerowska grafu spójnego jest orientacją silną , orientacją, która sprawia, że wynikowy graf skierowany jest silnie spójny .

Nieruchomości

Graf nieskierowany ma cykl Eulera wtedy i tylko wtedy, gdy każdy wierzchołek ma parzysty stopień, a wszystkie jego wierzchołki o stopniu niezerowym należą do jednej spójnej składowej .
cykle rozłączne krawędziowo wtedy i tylko wtedy, gdy wszystkie jego wierzchołki mają parzysty stopień. Tak więc graf ma cykl Eulera wtedy i tylko wtedy, gdy można go rozłożyć na cykle rozłączne krawędziowo, a jego wierzchołki niezerowe należą do pojedynczego połączonego składnika.
Graf nieskierowany ma ślad Eulera wtedy i tylko wtedy, gdy dokładnie zero lub dwa wierzchołki mają stopień nieparzysty, a wszystkie jego wierzchołki o stopniu niezerowym należą do jednego połączonego składnika
Graf skierowany ma cykl Eulera wtedy i tylko wtedy, gdy każdy wierzchołek ma równy stopień i stopień zewnętrzny , a wszystkie jego wierzchołki o stopniu niezerowym należą do jednego silnie połączonego składnika . Równoważnie, graf skierowany ma cykl Eulera wtedy i tylko wtedy, gdy można go rozłożyć na skierowane cykle rozłączne krawędziowo , a wszystkie jego wierzchołki o stopniu niezerowym należą do jednego silnie połączonego składnika.
Graf skierowany ma ślad Eulera wtedy i tylko wtedy, gdy co najwyżej jeden wierzchołek ma ( stopień ) - ( stopień ) = 1, co najwyżej jeden wierzchołek ma ( stopień ) - ( stopień ) = 1, co inny wierzchołek ma równy stopień wejściowy i wyjściowy, a wszystkie jego wierzchołki o stopniu niezerowym należą do pojedynczego połączonego składnika podstawowego wykresu nieskierowanego. ^{[ potrzebne źródło ]}

Konstruowanie ścieżek i obwodów Eulera

Używanie śladów Eulera do rozwiązywania zagadek polegających na rysowaniu kształtu ciągłym pociągnięciem:

Ponieważ układanka Haus vom Nikolaus ma dwa nieparzyste wierzchołki (pomarańczowe), szlak musi zaczynać się w jednym i kończyć w drugim.
Annie Pope z czterema nieparzystymi wierzchołkami nie ma rozwiązania.
Jeśli nie ma nieparzystych wierzchołków, ślad może zaczynać się w dowolnym miejscu i tworzy cykl Eulera.
Luźne końce są uważane za wierzchołki stopnia 1.

Algorytm Fleury'ego

Algorytm Fleury'ego to elegancki, ale nieefektywny algorytm, którego początki sięgają 1883 roku. Rozważmy graf, o którym wiadomo, że ma wszystkie krawędzie w tej samej składowej i co najwyżej dwa wierzchołki nieparzystego stopnia. Algorytm zaczyna się od wierzchołka o nieparzystym stopniu lub, jeśli wykres nie ma żadnego, zaczyna się od dowolnie wybranego wierzchołka. W każdym kroku wybiera następną krawędź na ścieżce jako taką, której usunięcie nie rozłączyłoby wykresu, chyba że nie ma takiej krawędzi, w którym to przypadku wybiera pozostałą krawędź w bieżącym wierzchołku. Następnie przechodzi do drugiego punktu końcowego tej krawędzi i usuwa krawędź. Na końcu algorytmu nie ma żadnych krawędzi, a sekwencja, z której wybrano krawędzie, tworzy cykl Eulera, jeśli graf nie ma wierzchołków nieparzystego stopnia, lub ślad Eulera, jeśli są dokładnie dwa wierzchołki nieparzystego stopnia.

Podczas gdy $,$ wykresu w pod względem liczby krawędzi, tj. pod uwagę złożoność wykrywania . Jeśli mamy ponownie uruchomić Tarjana po usunięciu każdej krawędzi, algorytm Fleury'ego będzie miał złożoność czasową ${\ Displaystyle O (| E|^ {2} )}$ . Dynamiczny algorytm wyszukiwania mostów Thorupa (2000) pozwala to ulepszyć do ${\ Displaystyle O (| E | \ cdot \ log ^{3}|E|\cdot \log \log |E|)}$ , ale nadal jest to znacznie wolniejsze niż alternatywne algorytmy.

Algorytm Hierholzera

Hierholzera z 1873 r. Przedstawia inną metodę znajdowania cykli Eulera, która jest bardziej wydajna niż algorytm Fleury'ego:

Wybierz dowolny początkowy wierzchołek v i podążaj śladem krawędzi od tego wierzchołka aż do powrotu do v . Nie można utknąć w żadnym innym wierzchołku niż v , ponieważ równy stopień wszystkich wierzchołków zapewnia, że gdy ślad wchodzi w inny wierzchołek w , musi pozostać niewykorzystana krawędź opuszczająca w . Wycieczka utworzona w ten sposób jest wycieczką zamkniętą, ale może nie obejmować wszystkich wierzchołków i krawędzi początkowego grafu.
Dopóki istnieje wierzchołek u , który należy do aktualnej trasy, ale ma sąsiednie krawędzie nie będące częścią trasy, rozpocznij kolejny szlak od u , podążając nieużywanymi krawędziami aż do powrotu do u , i dołącz tak utworzoną trasę do poprzedniej wycieczka.
Ponieważ zakładamy, że oryginalny graf jest spójny , powtórzenie poprzedniego kroku spowoduje wyczerpanie wszystkich krawędzi grafu.

Używając struktury danych, takiej jak podwójnie połączona lista , do utrzymywania zestawu nieużywanych krawędzi incydentnych z każdym wierzchołkiem, do utrzymywania listy wierzchołków w bieżącej trasie, które mają nieużywane krawędzie, oraz do utrzymywania samej trasy, poszczególne operacje algorytm (znajdowanie niewykorzystanych krawędzi wychodzących z każdego wierzchołka, znajdowanie nowego wierzchołka początkowego trasy i łączenie dwóch tras, które mają wspólny wierzchołek) może być wykonywane w stałym czasie, więc cały algorytm zajmuje czas liniowy , $O(|E|)$ .

Algorytm ten można również zaimplementować za pomocą deque . Ponieważ utknięcie jest możliwe tylko wtedy, gdy deque reprezentuje zamkniętą trasę, należy obrócić deque, usuwając krawędzie z ogona i dodając je do głowy, aż się odblokują, a następnie kontynuować, aż wszystkie krawędzie zostaną uwzględnione. Zajmuje to również czas liniowy, ponieważ liczba wykonanych obrotów nigdy nie jest większa niż ${\ Displaystyle | E |}$ (intuicyjnie wszelkie „złe” krawędzie są przenoszone na głowę, podczas gdy świeże krawędzie są dodawane do ogona)

Projekcje ortograficzne i diagramy Schlegla z cyklami Hamiltona wierzchołków pięciu brył platońskich - tylko ośmiościan ma ścieżkę lub cykl Eulera, przedłużając swoją ścieżkę o kropkowaną

Liczenie obwodów Eulera

Kwestie złożoności

Liczbę obwodów Eulera w Smitha digrafach można obliczyć za de Bruijna pomocą tak zwanego twierdzenia BEST , nazwanego na cześć , van Aardenne - Ehrenfesta , i T utte . Wzór stwierdza, że liczba obwodów Eulera w digrafie jest iloczynem silni pewnego stopnia i liczby ukorzenionych drzew . Ten ostatni można obliczyć jako wyznacznik , za pomocą twierdzenia o drzewie macierzowym , dając algorytm czasu wielomianowego.

Twierdzenie BEST zostało po raz pierwszy przedstawione w tej formie w „notatce dodanej w dowodzie” do artykułu Aardenne-Ehrenfest i de Bruijn (1951). Oryginalny dowód był bijekcją i uogólniał sekwencje de Bruijna . Jest to wariacja na temat wcześniejszego wyniku Smitha i Tutte (1941).

Policzenie liczby obwodów Eulera na grafach nieskierowanych jest znacznie trudniejsze. Ten problem jest znany jako #P-complete . Uważa się, że w pozytywnym kierunku Monte Carlo z łańcuchem Markowa , poprzez transformacje Kotziga (wprowadzone przez Antona Kotziga w 1968 r.), Daje ostre przybliżenie liczby obwodów Eulera na grafie, chociaż jak dotąd nie ma na to dowodu fakt (nawet dla wykresów o ograniczonym stopniu).

Przypadki specjalne

Asymptotyczny wzór na liczbę obwodów Eulera w pełnych grafach został określony przez McKay i Robinson (1995):

{\ Displaystyle \ nazwa operatora {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 )}.}

Podobny wzór uzyskał później MI Isaev (2009) dla pełnych grafów dwudzielnych :

{\ Displaystyle \ nazwa operatora {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 )}.}

Aplikacje

Ślady Eulera są wykorzystywane w bioinformatyce do rekonstrukcji sekwencji DNA z jego fragmentów. Są one również wykorzystywane w CMOS w celu znalezienia optymalnej kolejności bramek logicznych . Istnieje kilka algorytmów przetwarzania drzew , które opierają się na trasie Eulera po drzewie (gdzie każda krawędź jest traktowana jako para łuków). Sekwencje de Bruijna można skonstruować jako ścieżki eulerowskie grafów de Bruijna .

W nieskończonych grafach

Graf nieskończony ze wszystkimi stopniami wierzchołków równymi cztery, ale bez linii Eulera

W grafie nieskończonym koncepcją odpowiadającą śladowi Eulera lub cyklowi Eulera jest linia Eulera, podwójnie nieskończony ślad, który obejmuje wszystkie krawędzie grafu. Do istnienia takiego śladu nie wystarczy, aby graf był spójny i aby wszystkie stopnie wierzchołków były równe; na przykład pokazany nieskończony wykres Cayleya , ze wszystkimi stopniami wierzchołków równymi czterem, nie ma linii Eulera. Grafy nieskończone zawierające linie Eulera zostały scharakteryzowane przez Erdõsa, Grünwalda i Weiszfelda (1936) . Aby graf nieskończony lub multigraf $G$ miał linię Eulera, konieczne i wystarczające jest spełnienie wszystkich następujących warunków:

$G$ jest podłączony.
$G$ ma policzalne zbiory wierzchołków i krawędzi.
$G$ nie ma wierzchołków (skończonego) nieparzystego stopnia.
Usunięcie dowolnego skończonego podgrafu $S$ z $G$ pozostawia co najwyżej dwa nieskończenie połączone składniki w pozostałym grafie, a jeśli $S$ ma parzysty stopień w każdym ze swoich wierzchołków, to usunięcie $S$ pozostawia dokładnie jeden nieskończenie połączony składnik.

Nieskierowane grafy Eulera

Euler określił warunek konieczny, aby graf skończony był eulerowski, ponieważ wszystkie wierzchołki muszą mieć parzysty stopień. Hierholzer udowodnił, że jest to warunek wystarczający w artykule opublikowanym w 1873 r. Prowadzi to do następującego koniecznego i wystarczającego stwierdzenia, jakie musi być eulerowskie graf skończony: Nieskierowany spójny graf skończony jest eulerowski wtedy i tylko wtedy, gdy każdy wierzchołek G ma nawet stopień.

Następujący wynik został udowodniony przez Veblena w 1912 roku: Nieskierowany spójny graf jest eulerowski wtedy i tylko wtedy, gdy jest rozłączną sumą niektórych cykli.

Skierowany graf ze wszystkimi parzystymi stopniami, który nie jest eulerowski, służący jako kontrprzykład dla stwierdzenia, że warunkiem wystarczającym, aby graf skierowany był eulerowski, jest to, że ma wszystkie parzyste stopnie

Hierholzer opracował algorytm czasu liniowego do konstruowania trasy Eulera w grafie nieskierowanym.

Skierowane grafy Eulera

Można mieć graf skierowany, który ma wszystkie stopnie parzyste, ale nie jest eulerowski. Oznacza to, że nawet stopnie nie są wystarczającym warunkiem, aby dwuznak był eulerowski. König udowodnił, że dwuznak musi również mieć taką samą liczbę łuków wchodzących i wychodzących z każdego wierzchołka, aby był eulerowski. Innymi słowy, skierowany graf musi być symetryczny. Skierowany i silnie spójny graf jest eulerowski wtedy i tylko wtedy, gdy każdy wierzchołek G jest symetryczny.

Algorytm czasu liniowego Hierholzera do konstruowania trasy Eulera ma również zastosowanie do grafów skierowanych.

Mieszane grafy Eulera

Ten mieszany graf jest eulerowski. Wykres jest parzysty, ale niesymetryczny, co dowodzi, że równość i symetria nie są warunkami koniecznymi i wystarczającymi, aby graf mieszany był eulerowski.

Jeśli graf mieszany ma tylko stopnie parzyste, nie ma gwarancji, że będzie grafem Eulera. Oznacza to, że równość jest warunkiem koniecznym, ale niewystarczającym, aby graf mieszany był eulerowski. Jeśli graf mieszany jest parzysty i symetryczny, to na pewno jest symetryczny. Oznacza to, że równość i symetria są warunkiem koniecznym, aby graf mieszany był eulerowski. Nie jest to jednak warunek konieczny i wystarczający, ponieważ można skonstruować graf parzysty i niesymetryczny, czyli wciąż eulerowski.

Ford i Fulkerson udowodnili w 1962 roku w swojej książce Flows in Networks warunek konieczny i wystarczający, aby graf był eulerowski, a mianowicie, że każdy wierzchołek musi być parzysty i spełniać warunek równowagi. Dla każdego podzbioru wierzchołków S różnica między liczbą łuków wychodzących z S i wchodzących do S musi być mniejsza lub równa liczbie krawędzi incydentnych z S. Jest to warunek zbioru zrównoważonego. Graf mieszany i silnie spójny jest eulerowski wtedy i tylko wtedy, gdy G jest parzysty i zrównoważony.

Proces sprawdzania, czy graf mieszany jest eulerowski, jest trudniejszy niż sprawdzanie, czy graf nieskierowany lub skierowany jest eulerowski, ponieważ zrównoważony warunek zbioru dotyczy każdego możliwego podzbioru wierzchołków.

Parzysty graf mieszany, który narusza zrównoważony warunek zbioru, a zatem nie jest eulerowski.

Graf parzysty mieszany, który spełnia warunek zbioru zrównoważonego, a zatem jest grafem mieszanym Eulera.

Zobacz też

Matroid Eulera , abstrakcyjne uogólnienie grafów Eulera
Puzzle z pięcioma pokojami
Lemat o uścisku dłoni , udowodniony przez Eulera w jego oryginalnym artykule, pokazujący, że każdy nieskierowany spójny graf ma parzystą liczbę wierzchołków nieparzystego stopnia
Ścieżka Hamiltona – ścieżka, która odwiedza każdy wierzchołek dokładnie raz.
Problem z inspekcją trasy , szukaj najkrótszej ścieżki, która odwiedza wszystkie krawędzie, ewentualnie powtarzające się krawędzie, jeśli ścieżka Eulera nie istnieje.
Twierdzenie Veblena , które stwierdza, że grafy o parzystym stopniu wierzchołków można podzielić na cykle rozłączne krawędzi niezależnie od ich łączności

Notatki

Erdős, Pál ; Grunwald, Tibor ; Weiszfeld, Endre (1936), „Végtelen gráfok Euler vonalairól” [O liniach Eulera nieskończonych grafów] (PDF) , Mat. Naprawić. Lapok (po węgiersku), 43 : 129–140 . Przetłumaczone jako Erdős, P .; Grunwald, T. ; Vázsonyi, E. (1938), „Über Euler-Linien unendlicher Graphen” [O liniach Eulera na nieskończonych grafach] (PDF) , J. Math. fizyka (w języku niemieckim), 17 (1–4): 59–75, doi : 10.1002/sapm193817159 .
Euler L., „ Solutio problematis ad geometriam situs pertinentis ”, Komentarz. 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 .
E. Lucas, Récréations Mathématiques IV , Paryż, 1921.
Fleury, „Deux problemes de geometrie de position”, Journal de mathematiques elementaires (1883), 257–261.
T. van Aardenne-Ehrenfest i NG de Bruijn (1951) „Obwody i drzewa w zorientowanych grafach liniowych”, Simon Stevin 28: 203–217.
Thorup, Mikkel (2000), „Niemal optymalna, w pełni dynamiczna łączność grafów”, Proc. 32. Sympozjum ACM na temat teorii informatyki , s. 343–350, doi : 10.1145/335305.335345 , S2CID 128282
WT Tutte i CAB Smith (1941) „O ścieżkach jednokierunkowych w sieci stopnia 4”, American Mathematical Monthly 48: 233–237.

Linki zewnętrzne