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)[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