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.

  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

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.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.