W teorii wykres An Eulera ścieżka lub Eulera ścieżki , a nawet Eulera łańcuch o nieukierunkowane wykresu jest ścieżka , która przechodzi przez wszystkie krawędzie , raz na krawędzi. Nazwę nadano w nawiązaniu do Leonharda Eulera . Jeśli taka ścieżka powraca do punktu początkowego, mówimy o obwodzie eulera lub cyklu eulera , a nawet o wycieczce euleryjskiej . Graf, który dopuszcza obwód Eulera , jest nazywany Eulerowskim . Jeśli dopuszcza kurs eulera, mówi się, że jest pół-euleryjski .
Pojęcie ścieżki Eulera jest zilustrowane problemem projektu koperty. To kwestia narysowania koperty bez podnoszenia ołówka i bez kilkukrotnego rysowania tej samej linii. Rysunek możemy zamodelować za pomocą poniższego wykresu. Ścieżka Eulera odpowiada rysowaniu wykresu na arkuszu bez podnoszenia ołówka.
Przykład wykresu przyjmującego ścieżkę Eulera.
Rysunek odręczny bez podnoszenia ołówka
Problem z siedmioma mostami w Królewcu polega na tym, czy można przejść przez każdy most w mieście Królewca podczas jednego spaceru, po każdym moście. Jak pokazano na poniższym rysunku, problem jest modelowany za pomocą wykresu w następujący sposób: mosty tworzą grzbiety, a wyspy, a brzegi wierzchołkami. Ponieważ ten wykres nie dopuszcza ścieżki Eulera, problem nie ma rozwiązań.
|
Możemy również rozważyć wykres wielościanu , na przykład ośmiościanu . Wierzchołki i krawędzie wielościanu są odpowiednio wierzchołkami i krawędziami wykresu.
Stopień od wierzchołka jest liczba krawędzi wchodzących w tym wierzchołku krawędzi (incydent). Na poniższych wykresach wskazujemy stopnie dla każdego wierzchołka.
Wykres 7 mostów Królewca i inny wykres mówi o 5 komorach. Te wykresy nie uwzględniają ścieżek Eulera. Podane liczby to stopnie.
1. i 4. Wykresy mające ścieżkę Eulera, ale bez obwodu Eulera. 2. Wykres bez rozwiązania. 3. Wykres zawierający obwód Eulera.
Twierdzenie Eulera, zwane także twierdzeniem Eulera-Hierholzera, występuje w dwóch charakterystykach:
Euler zademonstrował niezbędne warunki w 1736 r. Kompletny dowód poniżej został opublikowany przez niemieckiego matematyka Carla Hierholzera w 1873 r. Eulerowi czasami przypisuje się równoważność, jak w książce Diestela o teorii grafów (patrz Th. 1.8.1 in). Dwa bezpośrednie kierunki przedstawiono w następujący sposób.
Załóżmy, że istnieje ścieżka Eulera i udaj się nią, usuwając używane krawędzie. Przy każdym przejściu przez szczyt (z wyjątkiem początku i końca), grzbiet, który dociera do tego szczytu i grzbiet, który z niego wychodzi, jest usuwany. Tak więc, z wyjątkiem wierzchołka początkowego lub końcowego, parzystość stopnia pozostaje niezmieniona. Na końcu ścieżki wszystkie krawędzie są usuwane, co pozwala wnioskować o parzystości wierzchołków.
Znaczenia pośrednie, tj. Odwrotność, można wykazać w następujący sposób.
Pokażmy to, gdy wszystkie wierzchołki są równe. Zacznijmy od dowolnego wierzchołka s 0 wykresu. Pożyczmy krawędzie, usuwając je z wykresu tak długo, jak to możliwe. Ponieważ stopnie są parzyste, koniecznie wróciliśmy do wierzchołka s 0 i znaleźliśmy obwód s 0 - s 1 - ... - s 0 . Jeśli nie ma już żadnych krawędzi, mamy obwód Eulera. W przeciwnym razie zaczynamy proces ponownie, aby pokazać inny obwód, od wierzchołka s i, od którego zaczyna się krawędź. Otrzymujemy wtedy kolejny obwód s i - ... - s i , który właśnie wkleiliśmy w poprzednim obwodzie w miejsce s i :
s 0 - s 1 - ... - s i - ... - s i - s i + 1 - ... s 0 .
Powtarzamy ten proces, aż wykorzystamy wszystkie krawędzie i otrzymamy obwód Eulera.
Możemy właściwie napisać program komputerowy do obliczania ścieżki lub obwodu Eulera, jeśli taki istnieje. Omówmy algorytm z pracy Hierholzera z 1873 r., Który jest zgodny z ideą jego dowodu (patrz znaczenie pośrednie powyżej). Powtarza wyodrębnianie obwodów, które sklejamy, aby zbudować obwód Eulera. Ten algorytm można zaimplementować w celu uzyskania algorytmu w czasie liniowym w liczbie krawędzi (patrz Przykład 2.5.2 i Algorytm 2.3.1 w). Aby to zrobić, następujące operacje muszą być wykonywane tylko w stałym czasie:
W tym celu wystarczy efektywnie zarządzać listami podwójnie połączonymi :
Pierre-Henry Fleury podał inny algorytm w 1883 roku, ale implementacja na komputerze byłaby mniej wydajna niż algorytm Hierholzera. Jego pomysłem jest zbudowanie obwodu poprzez każdorazowe pożyczanie priorytetowo krawędzi, której usunięcie nie powoduje odłączenia wykresu.
Powyższe wyniki są eksportowane do skierowanych wykresów. O takim wykresie mówi się, że jest Eulerianem, jeśli ma następującą właściwość:
Możemy uporządkować łuki wykresu w taki sposób, że dwie kolejne krawędzie w kolejności - gdzie ostatnia i pierwsza krawędź rzędu są uważane za kolejne - na wykresie następują po sobie.Tutaj znowu ta właściwość oznacza, że możemy „przechodzić” przez wykres, podążając za łukami od ich początkowego końca do końca i oczywiście używając każdego łuku dokładnie raz i wracając do punktu początkowego. Jeśli chodzi o wersję niezorientowaną, pokazujemy następujące twierdzenie:
Twierdzenie Eulera (wersja zorientowana) - Niech G będzie grafem zorientowanym. Następujące trzy zdania są równoważne:
Łączność wystarcza, aby rozszerzyć przypadek nieukierunkowany na przypadek skierowany, a graf Eulera jest siłą rzeczy silnie powiązany.
W niektórych książkach algorytmicznych (ale także w książce o teorii grafów Diestela, patrz Rozdział 10, str. 213), w ramach teorii złożoności , problem EULERII, czy graf jest Eulerianem, jest często porównywany z problemem HAMILTONIŃSKIM, aby znaleźć Kurs Hamiltona , czyli kurs przechodzący dokładnie raz przez każdy wierzchołek. Ustalenie, że wykres przyjmuje obwód Eulera, odbywa się w czasie wielomianowym (wystarczy sprawdzić parzystość stopni wierzchołków wykresu). Tak więc, problem Eulera czy wykres jest Eulera znajduje się w klasie P . Problem HAMILTONIŃSKI jest a priori bardziej skomplikowany do rozwiązania algorytmicznego: jest to problem NP-zupełny , mający ważne zastosowania.