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.

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.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte

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