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

Aus VoWi
Zur Navigation springen Zur Suche springen
  • (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)[Bearbeiten | Quelltext bearbeiten]

  • 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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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

(a)[Bearbeiten | Quelltext bearbeiten]

(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.)

  • Kantenzug
    • s. ger. Kantenfolge
  • Weg 6->1 (s. Grafik u.)

(b)[Bearbeiten | Quelltext bearbeiten]

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

  • Geschlossene Kantenfolge (s. Grafik u.)


  • geschlossener Kantenzug
    • s. geschl. Kantenfolge
  • Kreis
    • s. geschl. Kantenfolge

(c)[Bearbeiten | Quelltext bearbeiten]

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 , , ).

  • Starke Zusammenhangskomponenten (s. Grafik u.)

Anmerkungen[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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

Links[Bearbeiten | Quelltext bearbeiten]

  • Diskussion Informatik-Forum WS07 Beispiel 172