Cykl Eulera
Witam!
Dziś zajmiemy się zagadnieniem z teorii grafów. Dokładnie powiem o grafach eulerowskich.
Na początek kilka prostych definicji:
graf- graf to zbiór wierzchołków, które mogą być połączone krawędziami w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków
krawędź- linia łącząca wierzchołki
cykl- to ścieżka zamknięta, z takim samym ostatnim i pierwszym wierzchołkiem.
stopień- liczba krawędzi grafu incydentnych do wierzchołka.
Teraz możemy przejść do grafów eulerowskich.
Cykl eulerowski to taki cykl w grafie, który przechodzi przez każdą jego krawędź dokładnie raz.
Wszystko zaczęło się od Leonarda Eulera w roku 1736, który chciał rozwiązać zagadnienie mostów królewieckich.
Problem ten brzmi tak:Przez Królewiec przepływała rzeka Pregoła a ponad rzeką przerzucono siedem mostów, z których jeden łączył obie wyspy, a pozostałe mosty łączyły wyspy z brzegami rzeki.
Tak wygląda do graficznie:
Euler zadał pytanie: czy można przejść kolejno przez wszystkie mosty tak, żeby każdy przekroczyć tylko raz?
Inaczej możemy zapytać czy, jeżeli mamy określony graf, to czy możliwe jest skonstruowanie ścieżki, która pozwala na przejście każdej krawędzi grafu tylko raz?
Odpowiedź brzmi: Ilość wierzchołków nieparzystego stopnia musi wynosić 0 lub 2.
Warunkiem istnienia cyklu Eulera jest:
-spójność grafu,
-dla grafu skierowanego należy sprawdzić czy do każdego wierzchołka wchodzi tyle samo krawędzi co wychodzi
-dla grafu nieskierowanego z każdego wierzchołka musi wychodzić parzysta liczba krawędzi.
Jeszcze trzy wyjaśnienia:
spójność grafu- dla każdej pary wierzchołków istnieje ścieżka, która je łączy
Graf nieskierowany to po prostu graf z krawędziami również wielokrotnymi.
graf skierowany – inaczej digraf, w którym ruch po grafie możliwy jest tylko w kierunkach wskazywanych przez krawędzie.
Graf skierowany posiada drogę Eulera, gdy wszystkie wierzchołki z wyjątkiem dwóch mają takie same stopnie wychodzące i wchodzące, w jednym z tych dwóch wierzchołków stopień wychodzący jest o 1 większy niż wchodzący a w drugim odwrotnie
Rozważmy jeszcze sytuację grafu półeulerowskiego:
Graf półeulerowski zawiera w sobie ścieżkę, która pozwala przejść przez wszystkie jego krawędzie tylko raz (jeśli ścieżka jest zamknięta to mamy do czynienia z cyklem eulera).
Dodam kolejną definicję:
Spójny graf jest eulerowski wtedy i tylko wtedy, gdy stopień każdego wierzchołka jest parzysty.
Dla grafów skierowanych graf jest eulerowski gdy dla każdego wierzchołka zachodzi:
Konstrukcja szukania cyklu Eulera:
Niech graf będzie grafem eulerowskim. Jest wykonalna konstrukcja, która daje cykl Eulera.
1. usuwaj z grafu przechodzone krawędzie i wierzchołki izolowane powstałe w wyniku usuwania krawędzi.
2. Przechodź przez mosty wtedy i tylko wtedy, gdy nie ma innej możliwości.
Jest to tzw. algorytm Fleury’ego. Na poniższym rysunku cykl ma taką konstrukcję:
Kolejna definicja mówi nam, że: spójny graf jest półeulerowski wtedy i tylko wtedy, gdy ma dokładnie dwa wierzchołki stopnia nieparzystego.
Z grafem eulerowskim jest związane zagadnienie chińskiego listonosza. Polega ono na znalezieniu ścieżki zamkniętej, zawierającej każdą krawędź grafu co najmniej raz i mającej minimalny koszt (sumę wag krawędzi).
Jeśli wszystkie wierzchołki grafu są parzystego stopnia to istnieje droga zamknięta a więc rozwiązaniem jest cykl Eulera, gdyż suma wag krawędzi cyklu Eulera jest zawsze taka sama i nie zależy od wyboru wierzchołka początkowego.
Jeśli jednak rozwiązaniem nie jest graf eulerowski wtedy musimy poradzić sobie w inny sposób, ale o tym w najbliższym czasie na blogu.
Filed under: Matematyka,teoria grafów - @ 3 listopada 2017 21:16
Tagi: cykl Eulera, droga, euler, graf, graf nieskierowany, graf skierowany, graf zorientowany, krawędź, mosty królewieckie