TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 175

Angabe

Man bestimme die starken Zusammenhangskomponenten und die Reduktion $G_{5R}$ des Graphen $G_{5}$.

Theoretische Grundlagen (von Baccus)

• Ein ungerichteter Graph G heißt zusammenhängend, wenn jeder Knoten $a$ von jedem Knoten $b$ aus erreichbar ist: $\forall a,b\in V(G)\quad \exists$ Kantenfolge, die $a$ und $b$ verbindet.

• In einem gerichteten Graphen
  • heißen jene Knoten stark zusammenhängend, die mit anderen Knoten in beiden Richtungen verknüpft sind: $\forall a,b\in V(G)\quad a\rightarrow b\;\wedge \;b\rightarrow a$.
  • Knoten heißen schwach zusammenhängend, wenn sie im Schatten des Urgraphen gegenseitig erreichbar sind.

Ein gerichteter Graph zerfällt daher u.U. in mehrere Zusammenhangskomponenten, die in sich stark zusammenhängend sind, aber nicht untereinander.

Bei der Reduktion eines Graphen werden die starken Zusammenhangskomponenten zu einem Punkt (Knotensammlung) zusammengefaßt.

Stark zusammenhängend

sind daher (nach Anschauung) die Knoten (1,2,8) und (3,4,5,6,7).

Reduziert

sieht der Graph also so aus:

$\{1,2,8\}\longleftarrow \{3,4,5,6,7\}$.

[Theoretische Grundlagen (von mnemetz) [unklar]

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ösungsvorschlag von menemetz (inkorrekt)]

Starke Zusammenhangskomponenten

Starke Zusammenhangskomponenten sind:

• (Einser-Zyklus)
  • 1-8
  • 1-2
  • 1-2-8
• (Vierer-Zyklus)
  • 4-6-7-3
  • 4-6-3
• (Fünfer-Zyklus)
  • 5-4-6
  • 5-3-4-6

Graphentheoretische Reduktion

                   1 2 8
  5 3 4 6 *--------->*<-----------* 4 6 7 3

Links

f.thread:37573&highlight=reduktion f.thread:49405