---
title: Gerichtete Graphen
date: 2018-11-07
---

**Beispiel**: ![Digraph](20181107_1-dg.png)

$G = (V,E)$

* $V$ endliche Menge
* $E \subseteq V \times V$

Kanten in $G$ bestehen aus $(u,v)$ mit $u,v \in V, u \neq v$. $u$ heißt
Startknoten, $v$ heißt Endknoten der Kante $(u,v)$. Vorstellung: Laufen im
Graph nur in der richtigen Richtung. Kanten sind "Einbahnstraßen".

Für gerichtete Graphen definieren wir: $G=(V,E), u\in V$

* $outdeg(u) = |\{v \in V | (u,v) \in E\}|$
* $indeg(u) = |\{v \in V | (v,u) \in E\}|$


Beispiel von oben:

* $outdeg(1) = 1$, $indeg(1) = 2$
* $outdeg(4) = 1$, $indeg(4) = 0$


# Pfade, Wege, Kreise (gerichtet)

Definiert man analog zum ungerichteten Fall mit der Einschränkung, das Knoten
eines Pfades/Weges/Kreises in der richtigen Richtung verbunden sind.


**Beispiel**: Pfad

*Gegeben*: $G=(V,E)$ gerichteter Graph.

Ein Pfad $p$ ist ein Tupel $(v_0,...,v_{l-1})$ mit $v_i \in V$ und $(v_i,
v_{i+1}) \in E, \forall i \in \{0,...,l-2\}, v_i \neq v_j, \forall i \neq j$.
$p$ heißt $v_0v_{l-1}$-Pfad. Existenz eines Pfades von $u$ nach $v$ ($u,v \in
V$) bezeichnen wir mit $u \rightsquigarrow v$.


**Beispiel**: (wie oben)

* $(1,2,3,1,2)$ ist Weg
* $(4,1,2)$ ist Pfad
* $(2,3,1)$ ist Kreis


# Definition (Zusammenhang)

Sei $G=(V,E)$ gerichteter Graph und $u,v \in V$ Knoten. $u$ und $v$ heißen
stark zusammenhängend, falls es einen gerichteten $uv$-Pfad und einen
gerichteten $vu$-Pfad gibt, d.h. falls $u \rightsquigarrow v$ und $v
\rightsquigarrow u$

$$
\tag*{$\Box$}
$$


**Beispiel**: (von oben)

* 1 und 3 sind stark zusammenhängend
* 1 und 4 sind nicht stark zusammenhängend (kein Pfad von 1 nach 4)


**Bemerkung**: stark zusammenhängend ist Äquivalenzrelation. Die Untergraphen,
die den Äquivalenzklassen entsprechen, heißen **(starke)
Zusammenhangskomponenten**.


Ein gerichteter Graph $G$ heißt stark zusammenhängend, falls $G$ nur eine
Zusammenhangskomponente hat.