Direkt zum Inhalt

Lexikon der Mathematik: Eulerscher Digraph

ein Digraph D, der einen geschlossenen gerichteten Kantenzug W besitzt, welcher alle Bogen des Digraphen enthält, für den also B(W) = B(D) gilt.

Dieser geschlossene gerichtete Kantenzug W wird gerichtete Eulersche Tour genannt. Ein (nicht notwendig geschlossener) gerichteter Kantenzug W von D mit B(W) = B(D) heißt gerichteter Eulerscher Kantenzug.

Analog zu den Sätzen von Euler-Hierholzer und Veblen für Eulersche Graphen kann man die Eulerschen Digraphen wie folgt charakterisieren.

Ein zusammenhängender Digraph D ist genau dann Eulersch, wenn \({d}_{D}^{+}(x)\space =\space {d}_{D}^{-}\)für alle Ecken x aus D gilt, oder wenn sich D in bogendisjunkte gerichtete Kreise zerlegen läßt.

Auch der Algorithmus von Hierholzer ist anwendbar, um eine gerichtete Eulersche Tour in einem Eulerschen Digraphen zu bestimmen.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos