algorytm.org

Cykl Eulera

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Cykl Eulera
Ocena użytkowników:***** / 42
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 09 sierpnia 2005 21:35

Cykl Eulera, to taki cykl w grafie, który zawiera każdą krawędź grafu dokładnie raz. Warunkiem istnienia cyklu są:
  • 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.
Szukanie cyklu:
Zaczynamy od dowolnego wierzchołka (w naszym przypadku będzie to ten z najmniejszym indeksem), dodajemy ten wierzchołek na stos i idziemy do następnego, osiągalnego z niego wierzchołka z najmniejszym indeksem, a łącząca go z nim drogę usuwamy (rys.1), dodajemy ten wierzchołek na stos i idziemy do następnego, osiągalnego wierzchołka z najmniejszym indeksem, a łączącą go z nim drogę usuwamy (rys.2), itd...
Jeżeli nie możemy już nigdzie pójść pobieramy element ze stosu (będzie on kolejnym w cyklu) i teraz z ostatniego wierzchołka na stosie idziemy dalej (rys. 4). Czynność powtarzamy tak długo jak długo mamy jakieś wierzchołki na stosie.

Przykład:

Cykl Eulera - przykład
Przebieg algorytmu:
Cykl Eulera - krok 1 Cykl Eulera - krok 2
Stos: a,b
Cykl:
Stos: a,b,c
Cykl:
Cykl Eulera - krok 3 Cykl Eulera - krok 4
Stos: a,b,c,a
Cykl:
Stos: a,b,d
Cykl: a,c
Cykl Eulera - krok 5  
Stos: a,b,d,e,b
Cykl: a,c
 
Teraz już nigdzie nie możemy pójść więc zdejmujemy kolejno wierzchołki ze stosu i dodajemy je do cyklu. Końcowy wynik tych operacji to cykl: a,c,b,e,d,b,a.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Emil HotkowskiC/C++C++ - dla grafow nieskierowanych
.cpp
.cpp
***** / 7
Emil HotkowskiC/C++C++ - na listach krawedzi
.cpp
.cpp
***** / 2
Tomasz LubińskiDelphi/PascalBorland Delphi 5
.pas
.pas
***** / 6
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 16 sierpnia 2012 20:22
Komentarze
photo
-20 # xyz 2010-11-26 16:26
spójność grafu nie jest konieczna, ponieważ graf może posiadać wierzchołki izolowane przez co nie będzie spójny, ale cykl eulera może istnieć
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+5 # kutafon 2011-01-07 23:48
Jakiś dowód poprawności algorytmu by się przydał, bo za bardzo nie widać, dlaczego miałoby to działać
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-3 # mmm 2011-12-09 12:03
Poza tym warunek dla cyklu nie jest poprawny. Dopuszczalne są dokładnie dwa wierzchołki o nieparzystych stopniach.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+3 # x 2012-01-22 01:49
mmm, wtedy nie będzie w grafie istniał cykl, tylko ścieżka.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+2 # mz18 2012-01-19 17:53
@mmm: czy tobie nie chodzi przypadkiem o ścieżkę Eulera?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+7 # emil3566 2012-01-25 16:21
@mmm
Graf jest Eulerowski jeżeli wszystkie wierzchołki maja parzysty stopień wierzchołka, i to jest cykl bo przejdziesz wszystkie krawędzie wracając na koniec do początkowej.

(uwaga)
Graf jest półeulerowski jeżeli dwa wierzchołki są nieparzystego stopnia. Jest to tzw. ścieżka eulerowska , czyli droga która zawiera w sobie wszystkie krawędzie jednak zaczyna się i kończy w rożnych wierzchołkach :)

Pozdrawiam :)
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz