Satz von Menger

Sei $G$ ein Graph und $A,B\subseteq V(G)$.
Die minimale Größe eines $A$–$B$-Trenners ist gleich der maximalen Anzahl von paarweise Knoten-disjunkten $A$–$B$-Pfaden.

Beweis

Beweis. Sei $k:=k(G,X,Y)$ die minimale Zahl von Knoten, die $A$ und $B$ trennen. Wir zeigen folgende stärkere Aussage:

Wenn $\mathcal{P}$ weniger als $k$ disjunkte $A$-$B$-Pfade enthält, dann gibt es eine Menge $\mathcal{Q}$ von $|\mathcal{P}|+1$ disjunkten $A$-$B$-Pfaden, die $\mathcal{P}$ erweitert.

$\mathcal{Q}$ erweitert $\mathcal{P}$: $A\cap V(\mathcal{P})\subset A\cap V(\mathcal{Q})$ und $B\cap V(\mathcal{P})\subset B\cap V(\mathcal{Q})$

Wir fixieren im Folgenden $G$ und $A$, werden aber $B$ ändern.
Der Beweis ist per Induktion über $|V(\mathcal{P})|:=|\bigcup _{P\in \{\mathcal{P}\}}V(P)|$.

Induktionsbasis $|V(\mathcal{P})|=0$.
Sei $R$ ein $A$-$B$-Pfad. Wir setzen $\mathcal{Q}:=\{R\}$.

Induktionsschritt $|V(\mathcal{P})|>0$.
Sei $R$ ein $A$-$B$-Pfad, der die $(<k)$ Knoten aus $B$ in $V(\mathcal{P})$ vermeidet.

• Fall 1. Falls $R$ keinen Pfad aus $\mathcal{P}$ trifft, setzen wir $\mathcal{Q}:=\mathcal{P}\cup \{R\}$.
• Fall 2. Ang., $R$ trifft einen Pfad aus $\mathcal{P}$.
  Sei $x$ der letzte Knoten aus $R$, der auf einem $P\in \mathcal{P}$ liegt.
  Wir setzen $B^{\prime }:=B\cup V(xP\cup xR)$ und ${\mathcal{P}}^{\prime }:=(\mathcal{P}\setminus \{P\})\cup \{Px\}$.
  Nun gilt $|V({\mathcal{P}}^{\prime })|<|V(\mathcal{P})|$. Nach IV gibt es daher eine Menge ${\mathcal{Q}}^{\prime }$ von $|{\mathcal{P}}^{\prime }|+1$ disjunkten $A$-$B^{\prime }$-Pfaden, die ${\mathcal{P}}^{\prime }$ erweitern.
  ${\mathcal{Q}}^{\prime }$ muss daher:

  • einen Pfad $Q$ enthalten, der in $x$ endet, und

  • einen eindeutigen Pfad $Q^{\prime }$, dessen letzter Knoten $y$ keiner der letzten Endknoten von Pfaden in ${\mathcal{P}}^{\prime }$ ist.

  • Unterfall 2a: $y\notin V(xP)$. Dann erhalten wir $\mathcal{Q}$ aus ${\mathcal{Q}}^{\prime }$, indem wir $xP$ an $Q$ anhängen. Ferner, falls $y\in V(xR)$, hängen wir $yR$ an $Q^{\prime }$ an und fügen diesen Pfad zu $\mathcal{Q}$ hinzu. Falls $y\notin V(xR)$, fügen wir $Q^{\prime }$ zu $\mathcal{Q}$ hinzu.

  • Unterfall 2b: $y\in V(xP)$. Dann erhalten wir $\mathcal{Q}$ aus ${\mathcal{Q}}^{\prime }$, indem wir $xR$ zu $Q$ und $yP$ zu $Q^{\prime }$ hinzufügen.

In beiden Fällen erweitert $\mathcal{Q}$ die Menge $\mathcal{P}$, was zu zeigen war.

Beispiel

!DS_vollständiger_foliensatz, p.185

Links

• DS_vollständiger_foliensatz.pdf
• Separationen und Trenner