Erreichbarkeit und Zusammenhang
Mit Hilfe von Kantenzügen können wir eine bedeutsame Relation auf den Ecken eines Graphen definieren:
Definition (erreichbar)
Sei G = (E, K) ein Graph, und seien a, b ∈ E. Dann heißt die Ecke b erreichbar von der Ecke a in G, falls es einen Kantenzug von a nach b in G gibt. Andernfalls heißt b unerreichbar von a in G. Ist b erreichbar von a in G, so schreiben wir
a ∼G b oder kurz a ∼ b.
Beispiele
(1) | Jede Ecke a ist von sich selbst aus erreichbar, denn der Kantenzug a (der Länge 0) ist ein Kantenzug von a nach a. |
(2) | Ist G vollständig, so ist jede Ecke von jeder anderen aus erreichbar. Denn sind a, b verschiedene Ecken des Graphen, so ist a, b ein Kantenzug (der Länge 1) von a nach b in G. |
(3) | Ist a eine isolierte Ecke von G (d. h. d(a) = 0), so ist a nur von sich selbst aus erreichbar. In diesem Fall gilt also non(a ∼ b) für alle b ≠ a. |
(4) | Im Graphen des letzten der obigen Beispiele ist jede Ecke von jeder Ecke aus erreichbar. |
Es gelten die drei charakteristischen Eigenschaften der Gleichheit (Übung):
Satz (Eigenschaften der Erreichbarkeitsrelation)
Sei G = (E, K) ein Graph. Dann gilt für alle a, b, c ∈ E:
(1) | a ∼ a,(Reflexivität) |
(2) | a ∼ b impliziert b ∼ a,(Symmetrie) |
(3) | a ∼ b und b ∼ c impliziert a ∼ c.(Transitivität) |
Ein wichtiger Fall liegt vor, wenn sich je zwei Ecken durch einen Kantenzug verbinden lassen:
Definition (zusammenhängend)
Sei G = (E, K) ein Graph. Dann heißt G zusammenhängend, falls jede Ecke von jeder Ecke erreichbar ist, d. h. falls a ∼ b für alle a, b ∈ E gilt.
Allgemein können wir für jede Ecke die Menge der von dieser Ecke aus erreichbaren Ecken betrachten:
Definition (Zusammenhangskomponente)
Sei G = (E, K) ein Graph, und sei a ∈ E. Dann heißt die Menge
[ a ] = a/∼ = { b ∈ E | a ∼ b }
die Zusammenhangskomponente der Ecke a in G.
Die Zusammenhangskomponente einer Ecke ist eine Obermenge der Menge der Nachbarn. Es gilt
{ a } ∪ N(a) ⊆ [ a ], d(a) + 1 ≤ |[ a ]| für alle a ∈ E.
Aufgrund der Eigenschaften der Erreichbarkeit gilt für alle a, b ∈ E:
a ∼ b genau dann, wenn [ a ] = [ b ].
Weiter ist ein Graph genau dann zusammenhängend, wenn [ a ] = E für eine (und damit jede) Ecke a gilt. Allgemein teilen die Zusammenhangskomponenten die Eckenmenge in paarweise disjunkte nichtleere Mengen auf.
Beispiel
Wir betrachten den folgenden Graphen:
Der Graph hat, wie wir mit etwas Mühe erkennen können, die beiden Zusammenhangskomponenten
E1 = { 1, 2, 3, 5, 6, 11 } und E2 = { 4, 7, 8, 9, 10, 12 }.
Sind die Zusammenhangskomponenten bekannt, so können wir ein Ecken-Kanten-Diagramm des Graphen zeichnen, bei dem diese Komponenten offensichtlich sind:
In dieser Darstellung erscheinen die Zusammenhangskomponenten als abgetrennte „Länder“, und die Zerlegung eines Graphen in seine durch die Zusammenhangskomponenten definierten Untergraphen liegt nahe. Alternativ können wir auch die Kanten (samt den zugehörigen Ecken) einfärben, um die Zusammenhangskomponenten sichtbar zu machen:
Wie bei den bipartiten oder allgemein k-partiten Graphen liegt in den Zusammenhangskomponenten eine Zerlegung der Eckenmenge E in Teile E1, …, Ek vor. Im starken Kontrast zu den k-Partitionen sind nun aber die Teile in sich vernetzt, während es keine Kanten zwischen den Teilen gibt.