Wpisany przez Tomasz Lubiński
niedziela, 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ą.
| Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
| Tomasz Lubiński | Delphi/Pascal | Borland Delphi 5 |  | |
  / 1 |
| Tomasz Lubiński | Java |  | |
/ 1 |
Poprawiony: czwartek, 27 maja 2010 18:46
Komentarze