Übung 7: Graphen
Tiefensuche
Beweisen Sie das Lemma der weißen Pfade:
Gegen ein Graph G = (V,E) und ein Lauf des Tiefensuchalgorithmus'.
Ein Knoten v ist ein Nachfahre von Knoten u im Tiefesuchbaum gdw.
zur Entdeckungszeit d(u) von u der Knoten v auf einem Pfad in G
erreicht werden kann, der nur aus weißen Knoten besteht.
Komponentengraph
Der Kompenentengraph GSCC = (VSCC,
ESCC) eines gerichteten Graphen G = (V,E) enthält einen
Knoten für jede starke Zusammenhangskomponente und eine Kante (u,v) in
ESCC, falls es in G eine gerichtete Kante von einem Knoten
aus der Zusammenhangskomponente, die zu u gehört zu einer Knoten aus
der Zusammenhangskomponenten von v gibt. Geben Sie einen Algorithmus
an, der den Komponentengraph berechnet.
This document was translated from LATEX by HEVEA.