77 lines
1.9 KiB
Markdown
77 lines
1.9 KiB
Markdown
|
---
|
||
|
|
title: Gerichtete Graphen
|
||
|
|
date: 2018-11-07
|
||
|
|
---
|
||
|
|
|
||
|
|
**Beispiel**: 
|
||
|
|
|
||
|
|
$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.
|