Brücken

Der Zusammenhangsbegriff suggeriert folgende Definition von ausgezeichneten Kanten:

Definition (Brücke)

Sei G = (E, K) ein Graph, und sei ab  ∈  K. Dann heißt die Kante ab eine Brücke von G, falls die Ecke b im Teilgraphen G′ = (E, K − { ab }) nicht von a aus erreichbar ist.

Eine Kante ist genau dann eine Brücke, wenn das Streichen dieser Kante die Zahl der Zusammenhangskomponenten erhöht. Insbesondere ist eine Kante eines zusammenhängenden Graphen genau dann eine Brücke, wenn der durch das Streichen der Kante entstehende Graph nicht mehr zusammenhängend ist.

Beispiele

(1)	Sei G = (E, K) mit E = { 1, …, 6 } und K = { 12, 13, 14, 23, 45, 46, 56 }. Die Kante 14 ist die einzige Brücke von G.

(2)	Ist d(a) = 1, so ist die eindeutige Kante ab  ∈  K eine Brücke. Nach dem Streichen dieser Kante ist die Einermenge { a } eine Zusammenhangskomponente in G′.

(3)	Ist G = (E, K) ein Kreis, so besitzt G keine Brücken. Geht G′ aus G durch Streichen einer Kante hervor, so ist jede Kante von G′ eine Brücke in G′.

(4)	Ist a₀, …, a_n, a₀ ein Kreis in G, so ist keine der Kanten des Kreises eine Brücke in G.

(5)	Der vollständige Graph K_n hat für n = 2 genau eine Brücke und für n ≥ 3 keine Brücken.

(6)	Der vollständig bipartite Graph K_n, m hat für n, m ≥ 2 keine Brücken. Ist n = 1 oder m = 1, so ist jede Kante von K_n, m eine Brücke.

(7)	Wir betrachten den folgenden Graphen: Mit Ausnahme der Brücke 6-11 sind die Brücken nicht gut erkennbar. Dies ändert sich bei folgender Darstellung: Die Brücken des Graphen sind genau die Kanten 27, 47 und 6-11.

Wir werden später einen Algorithmus kennenlernen, der in effizienter Weise entscheidet, ob in einem beliebigen Graphen eine Ecke b von einer Ecke a aus erreichbar ist. Jeder derartige Algorithmus ist auch geeignet, um zu entscheiden, ob eine Kante ab eine Brücke ist. Denn dies ist genau dann der Fall, wenn b immer noch von a aus erreichbar ist, wenn wir die Kante ab streichen.

Eine Charakterisierung von „bipartit“

Als Anwendung des Begriffs einer Brücke beweisen wir eine bemerkenswerte Charakterisierung der bipartiten Graphen mit Hilfe von Kreisen:

Satz (Kreischarakterisierung bipartiter Graphen)

Sei G = (E, K) ein Graph. Dann sind äquivalent:

(a)	G ist bipartit.

(b)	Jeder Kreis in G hat eine gerade Länge.

Insbesondere ist jeder kreisfreie Graph bipartit.

Beweis

(a) impliziert (b):

Sei G bipartit durch E₁ und E₂. Weiter sei a₁, a₂, …, a_n, a₁ ein Kreis der Länge n in G. Wir dürfen a₁  ∈  E₁ annehmen (sonst tauschen wir E₁ und E₂ aus). Da jede Kante von G eine Ecke in E₁ mit einer Ecke in E₂ verbindet, gilt

a₁  ∈  E₁, a₂  ∈  E₂, a₃  ∈  E₁, a₄  ∈  E₂, …,

d. h. a_k  ∈  E₁ für ungerade k und a_k  ∈  E₂ für gerade k (Induktion nach k ≤ n). Wegen a₁a_n  ∈  K und a₁  ∈  E₁ ist a_n  ∈  E₂. Folglich ist n gerade.

(b) impliziert (a):

Wir zeigen die Implikation durch Induktion nach der Größe m = |K|.

Induktionsanfang m = 0:

Ist m = 0, so ist G bipartit (durch jede Zerlegung der Ecken).

Induktionsschritt von m nach m + 1:

Sei G ein Graph mit genau m + 1 Kanten derart, dass jeder Kreis in G eine gerade Länge besitzt. Sei a*b* eine beliebige Kante von G, und sei G′ der Teilgraph von G, der durch Streichen von a*b* aus G entsteht. Da jeder Kreis in G′ ein Kreis in G ist, existiert nach I. V. eine Bipartition E₁, E₂ von G′.

1. Fall: a*b* ist eine Brücke in G.

Ohne Einschränkung sei a*  ∈  E₁. Ist b*  ∈  E₂, so ist G bipartit durch E₁, E₂. Ist b*  ∈  E₁, so tauschen wir in der Zusammenhangskomponente von b* in G′ die Zugehörigkeit der Ecken zu E₁ und E₂ aus („Wechsel der Farbe“). Dadurch entsteht eine Bipartition E₁*, E₂* von G′, die eine Bipartition von G ist.

2. Fall: a*b* ist keine Brücke in G.

Dann gibt es einen Weg a₁, … , a_n von a* = a₁ nach b* = a_n in G′. Da a₁, …, a_n, a₁ ein Kreis in G der Länge n ist, ist n gerade. Wie oben liegen also a₁ = a* und a_n = b* in verschiedenen Teilen der Partition. Dies zeigt, dass G bipartit durch E₁ und E₂ ist.

Wir illustrieren das Argument der zweiten Implikation durch einige Diagramme. Hierzu betrachten wir den folgenden Graphen G = (E, K):

Der Graph hat Kreise der Länge 4 und 6. Die Kante 45 ist die einzige Brücke von G. Entfernen wir die Brücke a*b* = 45, so ist der entstehende Teilgraph G′ nach Induktionsvoraussetzung bipartit. Wir visualisieren dies durch eine rot-grün-Färbung der Ecken, wobei die Ecke 4 ohne Einschränkung rot sei. Dann sind folgende Färbungen möglich:

Im ersten Fall können wir die Färbung unverändert übernehmen, wenn wir die Brücke a*b* wieder hinzufügen. Im zweiten Fall führen wir einen Farbwechsel im rechten Teil des Graphen (der Zusammenhangskomponente von b* = 5) durch, um den ersten Fall zu erzeugen. Die so modifizierte Färbung von G′ ist erneut für G geeignet.

Entfernen wir eine andere Kante als die Brücke, etwa a*b* = 7-10, so können wir eine Färbung des Teilgraphen G′ unverändert übernehmen, da durch die Voraussetzung „alle Kreise in G haben gerade Länge“ sichergestellt wird, dass die beiden Ecken der Kante verschieden gefärbt sind. Nehmen wir wieder an, dass die 4 rot gefärbt ist, so ergibt sich notwendig die folgende Färbung von G′: