Zusammenhängende Graphen-Eigenschaft wichtig?

Wissenschaft Informatik
#1

Moin zusammen.

Wofür ist es wichtig, einen zusammenhängenden Graphen zu haben. Mir ist klar, was zusammenhängend bedeutet, nämlich eine Verbindung zwischen einem Eckenpaar u,v. Also dass man von einer Ecke u eine Ecke v erreichen kann. Gerichtete Graphen können auch sehr wohl zusammenhängen sein, man muss also nicht von v zurück nach u kommen können, oder?

Zurück zur eigentlichen Frage, wozu man das wissen sollte… Mir fällt da spontan ein, dass ein nicht zusammenhängender Graph kein Baum mehr sein kann. Aber sonstige Konsequenzen eines zusammenhängenden Graphen?

Viele Grüße
Disap

#2

Hallo,

Wofür ist es wichtig, einen zusammenhängenden Graphen zu
haben.

Stell dir vor, du willst ein Programm schreiben, das irgend etwas modelliert, und diese Komponenten werden intern als Graph dargestellt. Wenn einige Komponenten nicht mit dem Rest des Modells zusammenhängen, dann ist das vermutlich ein Fehler irgendwo im Modell, und sicher eine Meldung wert.

Oder stell dir vor, du hast das Netz der Deutschen Bahn im Computer als Graph - wenn der Graph nicht zusammenhängend ist, weißt du, dass du viel Geld fürs Bauen neuer Gleise ausgeben musst :wink:.

Oder eine allgemeinere Argumentation: wenn du einen zusammenhängenden Graphen traversierst, kannst du dich einfach von Knoten zu Knoten hangeln. Wenn er nicht zusammenhängt, musst du zusätzlich alle Knoten anschauen und sie gegebenenfalls besuchen, wenn du das noch nicht getan hast.

Um auf die gerichteten Graphen einzugehen: wenn ich mich richtig erinnere heißt ein Graph „stark zusammenhängend“, wenn man von jedem Knoten zu jedem anderen gelangen kann, indem man immer nur den Kanten in ihrerer Richtung folgt, und „schwach zusammenhängend“, wenn man auch die Gegenrichtung benutzen muss.

Grüße,
Moritz