algorytm.org

Generowanie grafu z cyklem 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?

Generowanie grafu z cyklem Eulera
Ocena użytkowników:***** / 6
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 31 lipca 2005 23:55

Warunkiem koniecznym na istnienie cyklu Eulera, w grafie jest:
  • 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
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiDelphi/PascalBorland Delphi 5
.pas
.pas
***** / 2
Tomasz LubińskiJava
.java
.java
***** / 5
 
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: 27 maja 2010 18:46
Komentarze
photo
+5 # Patryk 2010-05-18 15:09
A co Z warunkiem, że graf musi być spójny? Bez tego wyjdzie Ci jakaś bzdura,a nie graf z cyklem Eulera.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz