TU Wien:Mathematik 1 UE (diverse)/Übungen WS07/Beispiel 172

• (a) In nachstehendem Graphen gebe man (verschiedene) Beispiele für eine gerichtete Kantenfolge, einen Kantenzug und einen Weg vom Knoten 6 zum Knoten 1 an.
• (b) Desgleichen finde man eine geschlossene Kantenfolge, einen geschlossenen Kantenzug sowie einen Kreis jeweils durch den Knoten 5.
• (c) Man zeige, dass G schwach, aber nicht stark zusammenhängend ist und bestimme die starken Zusammenhangskomponenten.

Theoretische Grundlagen (von mnemetz)

• Kantenfolge: Von einem Startpunkt ausgehend existiert ein Weg (über einen vorgegebenen Punkt) zum Startpunkt zurück (muss nicht zum Startpunkt zurückführen). In einem gerichteten Graphen muss zusätzlich die Richtung übereinstimmen.
• Kantenzug: Dies ist eine Kantenfolge, in der keine Kante mehrfach auftritt.
• Weg: Ist eine offene Kantenfolge, in der kein Knoten mehrfach auftritt.

Kantenfolge und Kantenzug können die Attribute offen oder geschlossen haben.

Anmerkung

Die Definition für Kantenfolge gehört IMHO allgemeiner formuliert:

• Kantenfolge: Eine Folge von Kanten eines ungerichteten Graphen heißt Kantenfolge, wenn man die Kanten "ohne Absetzen" durchlaufen kann.
• Kreis: Ein Kreis ist eine geschlossene Kantenfolge, in der alle Knoten und Kanten verschieden sind (bis auf den Anfangs- bzw. Endknoten).

-- Superwayne 11:27, 17. Nov. 2014 (CET)

Lösungsvorschlag von mnemetz

ACHTUNG! Hier gibt es einige Unstimmigkeiten! Bitte die Anmerkungen am Ende beachten.

(a)

(a) In nachstehendem Graphen gebe man (verschiedene) Beispiele für eine gerichtete Kantenfolge, einen Kantenzug und einen Weg vom Knoten 6 zum Knoten 1 an.

• gerichtete Kantenfolge (s. Grafik u.)
  • $6\Rightarrow 3\Rightarrow 5\Rightarrow 6$
  • $6\Rightarrow 3\Rightarrow 4\Rightarrow 6$

• Kantenzug
  • s. ger. Kantenfolge

• Weg 6->1 (s. Grafik u.)
  • $6\Rightarrow 3\Rightarrow 2\Rightarrow 1$
  • $6\Rightarrow 3\Rightarrow 2\Rightarrow 8\Rightarrow 1$
  • $6\Rightarrow 5\Rightarrow 3\Rightarrow 2\Rightarrow 1$
  • $6\Rightarrow 5\Rightarrow 3\Rightarrow 2\Rightarrow 8\Rightarrow 1$

(b)

Desgleichen finde man eine geschlossene Kantenfolge, einen geschlossenen Kantenzug sowie einen Kreis jeweils durch den Knoten 5.

• Geschlossene Kantenfolge (s. Grafik u.)
  • $4\Rightarrow 6\Rightarrow 5\Rightarrow 4$
  • $3\Rightarrow 4\Rightarrow 6\Rightarrow 5\Rightarrow 3$

• geschlossener Kantenzug
  • s. geschl. Kantenfolge

• Kreis
  • s. geschl. Kantenfolge

(c)

Man zeige, dass G schwach, aber nicht stark zusammenhängend ist und bestimme die starken Zusammenhangskomponenten.

Graph ist nur schwach zusammenhängend, da keinesfalls von jedem Punkt aus der andere erreicht werden kann (Beispiele $8\Rightarrow 7$, $6\Rightarrow 7$, $3\Rightarrow 2$).

• Starke Zusammenhangskomponenten (s. Grafik u.)
  • $6\Rightarrow 5$
  • $1\Rightarrow 2$
  • $1\Rightarrow 8$
  • $2\Rightarrow 8\Rightarrow 1$
  • $3\Rightarrow 4\Rightarrow 6$

Anmerkungen

ACHTUNG: Laut Prof. Länger ist diese Lösung der starken Zusammenhangskomponenten nicht korrekt, da keine Knoten zu 2 starken Zusammenhangskomponenten gehören dürfen, sondern zu genau einer. Laut Prof. Länger sind die st. Zusammenhangskomponenten: {7}, {1,2,8}, {3,4,5,6}. (Man muss von jedem Knoten zu jedem anderen (auch wieder zum Startknoten zurück) kommen können)

von Fabs

Lt. Definition 2.21 heißt ein gerichteter Graph G "stark zusammenhängend", wenn für je zwei VERSCHIEDENE Knoten v,w aus V(G) eine (gerichtete) Kantenfolge von v nach w existiert. Daher dürfte {7} keine starke Zusammenhangskomponente sein, da ja hier die Knoten keine Schleifen zu sich selbst haben.

von WildAngie: Knoten {7} ist laut Definition 8.2.5 aus "Einführung in die Mathematik für Informatiker" eine Zusammenhangskomponente: "Den Graphen X mit |V(X)|=1 (ein isolierter Knoten) betrachten wir ebenfalls als zusammenhängend."

von MA

Achtung bei (a) Gerichtete Kantenfolge: $6\Rightarrow 3\Rightarrow 5\Rightarrow 6$ kann nicht stimmen, da es von 3 nach 5 keine Kantenfolge gibt, sondern nur von 5 nach 3. Mögliche gerichtete Kantenfolgen sind daher $6\Rightarrow 3\Rightarrow 4\Rightarrow 6$ und $6\Rightarrow 5\Rightarrow 4\Rightarrow 6$.

Links

• Diskussion Informatik-Forum WS07 Beispiel 172