Transitive Hülle

Definition:
Die Transitive Hülle $A^*$ eines Graphen beschreibt durch ihre Kanten alle paarweise erreichbaren Knoten.

Ansätze:

1. Die Breitensuche gestartet bei $u$ liefert alle von $u$ erreichbaren Knoten. Für die Transitive Hülle ist somit die Breitensuche auf alle Knoten anzuwenden, Zeit $O(n(n+m))$, oder der im Folgenden beschriebene Algorithmus von Warshall.
2. Für die Adjazenzmatrix eines Graphen gilt:
   $(A^t)_{ij} > 0 \Leftrightarrow$ es existiert ein Pfad der Länge $t$ von $v_i$ nach $v_j$
   Somit gilt: $(i,j) \in A^* \Leftrightarrow (\sum_{t=1}^n A^t)_{ij} > 0$
   Umgeformt: $(i,j) \in A^* \Leftrightarrow (I+A)^{n-1} > 0$
   Komplexität der Matrixmultiplikation: $O(n^3)$