Erreichbarkeit und Zusammenhang
Die wichtigste Relation in einem Graphen ist die Erreichbarkeitsbeziehung:
Definition (erreichbar)
Ist G = (E, K) ein Graph, so heißt eine Ecke b erreichbar von einer Ecke a, falls es einen Kantenzug a0, …, an in G gibt mit a0 = a und an = b.
Die Erreichbarkeit ist, wie man leicht zeigt, eine Äquivalenzrelation auf E. Wir können also definieren:
Definition (Zusammenhangskomponenten, zusammenhängend)
Die Äquivalenzklassen der Erreichbarkeitsrelation in einem Graphen G heißen die Zusammenhangskomponenten von G. Ein Graph G heißt zusammenhängend, falls jede Ecke von jeder anderen aus erreichbar ist.
Ein Graph G = (E, K) ist also genau dann zusammenhängend, wenn die Eckenmenge E die einzige Zusammenhangskomponente von G ist.
Im Umfeld der Erreichbarkeitsrelation definieren wir weiter:
Definition (Brücke)
Eine Kante k eines Graphen G heißt eine Brücke, wenn das Streichen von k aus G die Anzahl der Zusammenhangskomponenten erhöht.
Leicht zu sehen ist: Eine Kante ab ist genau dann eine Brücke, wenn der Kantenzug a, b der einzige Weg in G von a nach b ist.
In der Sprache der Relationen ist die Erreichbarkeitsrelation nichts anderes als die transitive Hülle der Relation R = { (a, b) | a b ∈ K } ∪ { (a, a) | a ∈ E }. Damit ist der im Kapitel über Matrizen vorgestellte Algorithmus von Warshall geeignet, die Erreichbarkeitsrelation effektiv zu berechnen, und er liefert insbesondere auch eine Antwort auf die Frage, ob ein gegebener Graph zusammenhängend ist oder nicht. Wir verweisen den interessierten Leser also auf das dritte Kapitel, für das folgende ist die Kenntnis der dortigen Ergebnisse aber nicht notwendig.
Definition (Abstand)
Sei G = (E, K) ein zusammenhängender Graph. Für a, b ∈ E setzen wir
d(a, b) = „die Länge eines kürzesten Kantenzuges von a nach b in G“,
und nennen d(a, b) den Abstand von a und b in G.
Der Buchstabe „d“ steht hier für „distance“. Die Funktion d : G2 → ℕ hat die Eigenschaften einer Metrik, d. h. für alle a, b, c ∈ E gilt d(a, a) = 0, d(a, b) = d(b, a), sowie die Dreiecksungleichung d(a, c) ≤ d(a, b) + d(b, c).
Ist G nicht zusammenhängend, so kann man d(a, b) = ∞ vereinbaren, falls die Ecken a und b in verschiedenen Zusammenhangskomponenten des Graphen liegen. Unter den üblichen Rechenregeln für ∞ gelten dann immer noch die metrischen Eigenschaften für die Funktion d. Die Zusammenhangskomponente einer Ecke a ist dann gegeben durch { b ∈ E | d(a, b) < ∞ }.