Direkt zum Inhalt

Lexikon der Mathematik: gerichteter Graph

Digraph, Begriff aus der Graphentheorie.

Ein gerichteter Graph (Digraph) D besteht aus einer endlichen, nicht leeren Menge E(D) von Ecken und einer Menge B(D) geordneter Paare (x, y) von verschiedenen Ecken x und y. Man nennt E(D) Eckenmenge, |E(D)| Eckenzahl, B(D) Bogenmenge und |B(D)| Bogenzahl des Digraphen D.

Ein Element k = (x, y) ∈ B(D) heißt Bogen oder gerichtete Kante, und man sagt auch, k ist ein Bogen von x nach y oder x ist Anfangsecke und y Endecke von k. Der Außengrad \({d}_{D}^{+}(x)\) bzw. Innengrad \({d}_{D}^{-}(x)\) einer Ecke x in D ist die Anzahl der Bogen mit x als Anfangsecke bzw. mit x als Endecke. Die Zahlen \begin{eqnarray}{\delta }^{+}(D)=\min \{{d}_{D}^{+}(x)|x\in E(D)\}\end{eqnarray} bzw. \begin{eqnarray}{\delta }^{-}(D)=\min \{{d}_{D}^{-}(x)|x\in E(D)\}\end{eqnarray} nennt man minimalen Außengrad bzw. minimalen Innengrad, und \begin{eqnarray}{{\rm{\Delta }}}^{+}(D)=\max \{{d}_{D}^{+}(x)|x\in E(D)\}\end{eqnarray} bzw. \begin{eqnarray}{{\rm{\Delta }}}^{-}(D)=\max \{{d}_{D}^{-}(x)|x\in E(D)\}\end{eqnarray} maximalen Außengrad bzw. maximalen Innengrad des Digraphen D. Weiter heißt \begin{eqnarray}\delta (D)=\min \{{\delta }^{+}(D),{\delta }^{-}(D)\}\end{eqnarray}

Minimalgrad von D. Im Fall \begin{eqnarray}{d}^{+}(x,D)={d}^{-}(x,D)=0\end{eqnarray} spricht man von einer isolierten Ecke x.

Falls ein Digraph D nicht zu groß ist, so veranschaulicht man ihn sich am besten durch eine Skizze, indem man die Ecken als Punkte der Ebene zeichnet, und jeden Bogen k = (x, y) durch einen von x nach y gerichteten Pfeil darstellt. Die Abbildung zeigt einen Digraphen D mit der Eckenmenge E(D) = {x1, x2, x3, x4, x5, x6, x7} und den 10 Bogen (x2, x3), (x3, x2), (x3, x4), (x4, x5), (x2, x6), (x6, x3), (x6, x7), (x7, x6), (x7, x3), (x4, x7).

Abbildung 1 zum Lexikonartikel gerichteter Graph
© Springer-Verlag GmbH Deutschland 2017
 Bild vergrößern

Gerichteter Graph (Digraph)

Der skizzierte Digraph hat folgende Eigenschaften. Er besitzt sieben Ecken, also gilt |E(D)| = 7. Es gilt weiterhin \begin{eqnarray}\begin{array}{l}{{\rm{\Delta }}}^{+}(D)={d}_{D}^{+}({x}_{3})=2,\\ {d}_{D}^{-}({x}_{4})={d}_{D}^{-}({x}_{2})=1,\\ {{\rm{\Delta }}}^{-}(D)={d}_{D}^{-}({x}_{3})=3,\\ {d}_{D}^{+}({x}_{5})=0,\end{array}\end{eqnarray} und x1 ist eine isolierte Ecke.

Aus jedem Digraphen D kann man auf eindeutige Weise einen Multigraphen (Pseudograph) mit der gleichen Eckenmenge konstruieren, indem man jedem Bogen von x nach y eineindeutig eine Kante zuordnet, die mit x und y inzidiert. Ein solcher Multigraph heißt untergeordneter Multigraph des Digraphen D.

Umgekehrt kann man aus jedem Graphen G einen Digraphen D konstruieren, indem man jeder Kante eine Richtung gibt. Man nennt D dann eine Orientierung von G. Diese Konstruktion ist natürlich keineswegs eindeutig.

Analog zur Theorie der Graphen existiert auch für Digraphen ein Handschlaglemma: \begin{eqnarray}\displaystyle \sum _{x\in E(D)}{d}_{D}^{+}(x)=\displaystyle \sum _{x\in E(D)}{d}_{D}^{-}(x)=|B(D)|.\end{eqnarray}

Eine endliche Folge von Ecken xi und Bogen kj in einem Digraphen D der Form \begin{eqnarray}W={x}_{0}{k}_{1}{x}_{1}{k}_{2}{x}_{2}\ldots {x}_{p-1}{k}_{p}{x}_{p}\end{eqnarray} mit ki = (xi−1, xi) für i = 1, 2,…, p heißt gerichtete Kantenfolge von x0 nach xp der Länge p. Für W schreibt man auch kurz \begin{eqnarray}W={x}_{0}{x}_{1}\ldots {x}_{p}.\end{eqnarray}

Die gerichtete Kantenfolge W ist geschlossen, wenn x0 = xp, und offen, wenn x0xp gilt.

Sind in einer gerichteten Kantenfolge alle Bogen paarweise verschieden, so spricht man von einem gerichteten Kantenzug, und sind sogar alle Ecken paarweise verschieden, so liegt ein gerichteter Weg vor. Ein geschlossener gerichteter Kantenzug C = x0k1x1xp−1kpx0, in dem die Ecken x0, x1,…,xp−1 paarweise verschieden sind, heißt gerichteter Kreis. In dem oben skizzierten Digraphen D ist z. B. x3x2x6x3x4x7x3 ein geschlossener gerichteter Kantenzug der Länge 6, aber kein gerichteter Kreis. Dagegen sind x3x2x3 bzw. x3x4x7x6x3 gerichtete Kreise der Länge 2 bzw. 4.

Besitzt ein Digraph keinen gerichteten Kreis, so spricht man auch von einem kreisfreien Digraphen. Ein Digraph D heißt stark zusammenhängend, wenn für je zwei verschiedene Ecken x und y ein gerichteter Weg von x nach y existiert. Man nennt einen Digraphen zusammenhängend, wenn sein untergeordneter Multigraph zusammenhängend ist. Es ist recht leicht zu sehen, daß ein zusammenhängender Digraph D genau dann stark zusammenhängend ist, wenn jeder Bogen auf einem gerichteten Kreis liegt.

Ein Digraph D heißt pseudo-symmetrisch, wenn \begin{eqnarray}{d}_{D}^{+}(x)={d}_{D}^{-}(x),\end{eqnarray} und regulär, wenn \begin{eqnarray}{d}_{D}^{+}(x)={d}_{D}^{-}(x)=r\end{eqnarray} für alle xE(D) gilt.

[1] Bollobás, B.: Modern Graph Theory. Springer New York, 1998.
[2] Chartand, G.; Lesniak, L.: Graphs and Digraphs. Chapman and Hall London, 1996.
[3] Volkmann, L.: Fundamente der Graphentheorie. Springer Wien New York, 1996.

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