Wpisany przez Tomasz Lubiński,
31 lipca 2005 23:55
Warunkiem koniecznym na istnienie cyklu Eulera, w grafie jest:
Jak wygenerować taki graf? Otóż należy sprawdzać kolejno dla wierzchołków od 1 do n-1, gdzie n - liczba wierzchołków, czy spełnione są podane powyżej warunki. Jeżeli są spełnione to przechodzimy do sprawdzania następnego wierzchołka, jeżeli nie to wybieramy wierzchołek o indeksie większym od aktualnie sprawdzanego i odpowiednio:
- dla grafu skierowanego - do każdego wierzchołka musi wchodzić tyle samo krawędzi co wychodzi
- dla grafu nieskierowanego - z każdego wierzchołka musi wychodzić parzysta liczba krawędzi
Jak wygenerować taki graf? Otóż należy sprawdzać kolejno dla wierzchołków od 1 do n-1, gdzie n - liczba wierzchołków, czy spełnione są podane powyżej warunki. Jeżeli są spełnione to przechodzimy do sprawdzania następnego wierzchołka, jeżeli nie to wybieramy wierzchołek o indeksie większym od aktualnie sprawdzanego i odpowiednio:
- dla grafu nieskierowanego: jeżeli wierzchołek ten jest incydentny z właśnie sprawdzanym to usuwamy krawędź, a jeśli nie jest to ją tworzymy
- dla grafu skierowanego: analogicznie dodajemy bądź usuwamy dowolnie krawędź wchodzącą lub wychodzącą.
Implementacje
Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Tomasz Lubiński | Delphi/Pascal | Borland Delphi 5 | .pas | .pas | ***** / 2 |
Tomasz Lubiński | Java | .java | .java | ***** / 5 |
Poprawiony: 27 maja 2010 18:46