Konstruktion von minimalen Spannbäumen

Es gibt zwei Prinzipien für die Konstruktion von minimalen Spannbäumen(Tarjan):

• ,,blaue`` Regel
• ,,rote`` Regel
  

Beweis: durch Widerspruch

1.

Sei T ein minimaler Spannbaum von (G,w), sei $e \in E_C$ die minimale Kante. Annahme: $e \notin T$. Da T Spannbaum $\Rightarrow T \cap E_C \neq \emptyset$.
Sei $T \cap E_C = \{e_1, e_2, \ldots, e_k\}, k\geq 1$. Dann enthält $T \cup \{e\}$ einen eindeutig bestimmten Kreis (den sogenannten durch e bzgl. T bestimmten Fundamentalkreis). Dieser Kreis muß mindestens eine Kante $\in E_c \cap T$ enthalten, da die beiden Endpunkte von e auf verschiedenen Seiten des Schnitts C liegen.

Sei $e' \in E_c \cap T$. Dann gilt nach Vorraussetzung w(e') >w(e). Also ist $T':=T-\{e'\}\cup\{e\}$ ein Spannbaum von G, der echt kleineres Gewicht als T hat, Widerspruch zu T ist minimaler Spannbaum.

2.

Sei $e \in E_c$ minimal. Annahme: e kommt in keinem minimalen Spannbaum vor. Sei T ein beliebiger minimaler Spannbaum von (G,w).

$e \notin T \cap E_c \neq \emptyset$. Sei $e' \in E_c \cap T$ eine Kante auf dem durch e bezüglich T erzeugten Fundamentalkreis. Dann ist $T'=T-\{e'\}\cup\{e\}$ wieder ein Spannbaum von G, und es ist w$(T')\leq$w(T). Also T' minimaler Spannbaum und $e \in T'$.
$\Diamond$

Beweis:

1.

Nehmen wir an, daß es einen minimalen Spannbaum T gibt, der $e=\{v_1,v_2\}$ enthält. Wenn wir e aus T entfernen, so zerfällt T in zwei nicht zusammenhängende Teilbäume T₁ und T₂ mit $v_i\in T_i$, i=1,2. Da aber e auf einem Kreis in G liegt, muß es einen Weg von v₁ nach v₂ geben, der e nicht benützt. Mithin gibt es eine Kante $\hat{e}\neq e$ auf diesem Weg, die einen Knoten in T₁ mit T₂ verbindet. Verbinden wir T₁ und T₂ entlang $\hat{e}$, so erhalten wir einen von T verschiedenen Spannbaum $\hat{T}$. Wegen $w(\hat{e})<w(e)$ folgt $w(\hat{T})<w(T)$. Ein Widerspruch.

2.

Wir nehmen an, e_i liege in jedem minimalen Spannbaum (MSB) von G, und zeigen die Behauptung durch Widerspruch.
Sei T ein beliebiger MSB von G. Entfernen wir e_i aus T, so zerfällt T in zwei nicht zusammenhängende Teilbäume T₁ und T₂. Da e_i auf einem Kreis $c_1=e_1,\ldots,e_k$ in G liegt, können wir wie unter 1. e_i durch eine Kante e_j des Kreises c₁ ersetzen, die T₁ und T₂ verbindet. Dadurch erhalten wir einen von T verschiedenen Spannbaum $\tilde T$, der e_i nicht enthält. Da nach Voraussetzung $w(e_j)\le w(e_i)$ gilt, folgt $w(\tilde T)\le w(T)$ (und sogar $w(\tilde T)= w(T)$, da T nach Annahme ein MSB ist). Also ist $\tilde T$ ein MSB von G, der e_i nicht enthält, im Widerspruch zur Annahme, e_i liege in jedem MSB von G.
$\Diamond$

Literatur: R.E. Tarjan: ``Data Structures and Network Algorithms'', SIAM CBMS-NSF Reihe Bd. 44.