TU Wien:Mathematik 1 UE (diverse)/Übungen SS10/Beispiel 29

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

  • Kantenfolge: Von einem Startpunkt ausgehend existiert ein Weg (über einen vorgegebenen Punkt) zum Startpunkt zurück. 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.