Eulerweg/Eulerkreis bei gerichteten Graphen?
Hallo,
gibt es für gerichtete Graphen einen Eulerweg bzw. Eulerkreis?
Wenn ja, gelten genau die Voraussetzungen wie bei den ungerichteten Graphen?
Danke im voraus!
1 Antwort
Hi,
ja, auch für gerichtete Graphen gibt es Eulerkreise und Eulerwege.
Die Voraussetzungen sind ähnlich. Ein ungerichteter Graph ist ja dann eulersch, wenn alle Knoten geraden Grad haben, d.h. die Anzahl der anliegenden Kanten gerade ist.
Bei gerichteten Graphen muss für jeden Knoten der Eingangsgrad (also Anzahl der eingehenden Kanten) gleich dem Ausgangsgrad (Anzahl der ausgehenden Kanten) sein. Ist ja auch logisch, denn man braucht ja für jeden Eingang in den Knoten auch einen zugehörigen Ausgang, damit man einen Kreis laufen kann, in dem jede Kante nur einmal vorkommt.
Gruß,
florgy