103 lines
2.8 KiB
Markdown
103 lines
2.8 KiB
Markdown
---
|
|
title: Transitive Hülle
|
|
date: 2018-11-07
|
|
---
|
|
|
|
Gegeben eine endliche Menge $V$ und eine Relation $R$ auf $V$, d.h. $R
|
|
\subseteq V \times V$.
|
|
|
|
Zwei Elemente $u,v \in V$ stehen in Relation, falls $(u, v) \in R$.
|
|
|
|
|
|
**Frage**: Wie findet man die kleinste transitive Hülle von $R^+$ mit $R
|
|
\subseteq R^+$?
|
|
|
|
$R^+$ heißt transitive Hülle von $R$.
|
|
|
|
Als Graphenproblem:
|
|
|
|
Wir modellieren "in relation stehen" durch Kanten
|
|
|
|
|
|
# Definition (Transitive Hülle)
|
|
|
|
Sei $G=(V,E)$ ein gerichteter Graph. Der Graph $G^+ = (V,E^+)$ mit $E^+ = \{
|
|
(v,b) | u,v \in V, (u \rightsquigarrow v) \in G \}$ heißt **transitive Hülle**
|
|
von $G$.
|
|
|
|
|
|
**Beispiel**: 
|
|
|
|
 ist die transitive Hülle von
|
|
obigem Graph.
|
|
|
|
|
|
# Algorithmus (Berechnen der Transitiven Hülle; Warshall)
|
|
|
|
Für einen gerichteten Graphen $G=(V,E)$ mit $V=\{1,...,n\}$ betrachte die
|
|
Adjazenzmatrix von $G$ definiert als $A[i,j] = \begin{cases}
|
|
1 & (i,j) \in E \\
|
|
0 & (i,j) \notin E
|
|
\end{cases}$
|
|
|
|
**Bemerkung**: $A$ ist im allgemeinen nicht mehr symmetrisch (anders als bei
|
|
ungerichteten Graphen).
|
|
|
|
**Idee**: Ausgehend von $A$ schrittweise die Adjazenzmatrix der transitiven
|
|
Hülle zu berechnen.
|
|
|
|
Für $k \in \{0, ..., n\}$ definieren wir Matrizen $T_k$ rekursiv als
|
|
$T_k[i,j] = \begin{cases}
|
|
1 & \text{falls es einen $i$-$j$-Pfad mit Zwischenknoten aus } \{1, ...,
|
|
k\} \text{ gibt} \\
|
|
0 & \text{sonst}
|
|
\end{cases}$.
|
|
|
|
Dann gilt $T_0 = A$ (Adjazenzmatrix) und $T_n$ ist die Adjazenzmatrix der
|
|
transitiven Hülle
|
|
|
|
Wir wollen $T_k$ rekursiv aus $T_{k-1}$ berechnen (für $k \geq 1$). Es gilt
|
|
$T_k[i,j] = max \{ T_{k-1}[i,j], T_{k-1}[i,k] \cdot T_{k-1}[k,j] \}$, d.h.
|
|
$T_k[i,j] = 1$ genau dann, wenn $T_{k-1}[i,j] = 1$ oder $T_{k-1}[i,k] = 1$ und
|
|
$T_{k-1}[k,j] = 1$.
|
|
|
|
Die $i$-$j$-Pfade mit Zwischenknoten aus $\{1,...,k\}$ zerfallen in 2 Fälle:
|
|
|
|
i) $i$-$j$-Pfade mit Zwischenknoten aus $\{1,...,k-1\}$
|
|
i) $i$-$j$-Pfade, die den Knoten $k$ als Zwischenknoten enthalten
|
|
|
|
|
|
Pfade im Fall
|
|
|
|
i) gibt es, falls $T_{k-1}[i,j] = 1$
|
|
i) gibt es, falls $T_{k-1}[i,k] = 1$ und $T_{k-1}[k,j] = 1$
|
|
|
|
|
|
## Algorithmus im Pseudocode
|
|
|
|
**Eingabe**: Adjazenzmatrix $A$ von $G=(V,E)$ (gerichteter Graph)
|
|
|
|
**Ausgabe**: Adjazenzmatrix der transitiven Hülle
|
|
|
|
i) $W = A$
|
|
i) `for` $k$ `in` $\{1,...,n\}$ `do`
|
|
|
|
`for` $i$ `in` $\{1,...,n\}$ `do`
|
|
|
|
`for` $j$ `in` $\{1,...,n\}$ `do`
|
|
|
|
$W[i,j] = max \{ W[i,j], W[i,k] \cdot W[k,j] \}$
|
|
|
|
i) Ausgabe $W$
|
|
|
|
|
|
**Laufzeit**: $O(n^3)$
|
|
|
|
**Korrektheit**: Basiert auf Rekusionsformel von oben und der Bemerkung
|
|
$T_{k-1}[i,k] = T_k[i,k]$ und $T_{k-1}[k,j] = T_k[k,j]$.
|
|
|
|
Dies gilt, da Pfade mit Startknoten $i$ und Endknoten $k$ und Zwischenknoten
|
|
aus $\{1, ..., k-1\}$ sind (in Pfaden gibt es keine Kotenwiederholungen).
|
|
|
|
Algorithmus ist Beispiel für dynamische Programmierung, dazu später mehr.
|