TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 173
Zur Navigation springen
Zur Suche springen
Angabe[Bearbeiten | Quelltext bearbeiten]
Man bestimme die starken Zusammenhangskomponenten und die Reduktion des Graphen .
Theoretische Grundlagen (von mnemetz)[Bearbeiten | Quelltext bearbeiten]
Ein ungerichteter Graph G heißt zusammenhängend, wenn jeder Knoten y von jedem Knoten x aus erreichbar ist.
In einem gerichteten Graph fasst man jene Knoten zu einer starken Zusammenhangskomponente zusammen, die selbst von jedem dieser Knoten erreichbar sind. Sollte ein Knoten nur in einer Richtung erreichbar sein, so wird er selbst zu einer starken Zusammenhangskomponente.
Bei der Reduktion eines Graphen werden die starken Zusammenhangskomponenten zu einem Punkt zusammengefasst und dann verbunden.
Lösungsvorschag (von der Lerngruppe vom 26.12.2005)[Bearbeiten | Quelltext bearbeiten]
Starken Zusammenhangskomponenten[Bearbeiten | Quelltext bearbeiten]
Starke Zusammenhangskomponenten sind:
- 3-2-1-4
- 2-1-4 (ist umstritten wg. obigem)
- 5
- 6
- 7