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) = {x₁, x₂, x₃, x₄, x₅, x₆, x₇} und den 10 Bogen (x₂, x₃), (x₃, x₂), (x₃, x₄), (x₄, x₅), (x₂, x₆), (x₆, x₃), (x₆, x₇), (x₇, x₆), (x₇, x₃), (x₄, x₇).

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 x₁ 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 x_i und Bogen k_j 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 k_i = (x_i−1, x_i) für i = 1, 2,…, p heißt gerichtete Kantenfolge von x₀ nach x_p 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 x₀ = x_p, und offen, wenn x₀ ≠ x_p 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 = x₀k₁x₁ … x_p−1k_px₀, in dem die Ecken x₀, x₁,…,x_p−1 paarweise verschieden sind, heißt gerichteter Kreis. In dem oben skizzierten Digraphen D ist z. B. x₃x₂x₆x₃x₄x₇x₃ ein geschlossener gerichteter Kantenzug der Länge 6, aber kein gerichteter Kreis. Dagegen sind x₃x₂x₃ bzw. x₃x₄x₇x₆x₃ 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 x ∈ E(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.