Mit hilfe von minimalen Schnitten können bestimmte Eigenschaften zu einem gegebenen Netzwerk untersucht werden. Dazu zählt zum beispiel die Suche nach Bottlenecks, oder die Störungsanfälligkeit eines Netzwerks.
Schnitt
Definition
Gegeben ist ein Netzwerk G=(V,E,c) mit Quelle s und Senke t. Sei U⊆V mit s∈U und t∈/U. Dann heißt C:=σ+(U)Schnitt von G. Dazu ist cap(C):=∑e∈σ+(U) c(e) die Schnittkapazität von C.
Beispiel
Im obigen Netzwerk ist der Schnitt zur Menge U={s,a,b}⊂V in lachsfarbend hervorgehoben. Der Schnitt ist: C={(s,a),(s,c),(a,b),(b,c),(c,t)} mit der Schnittkapazität cap(C)=60.
Minimaler Schnitt
Definition
Ein Schnitt heißt minimal, die Schnittkapazität minimal ist.
Flusswert und Schnittkapazität
Satz
Sei G=(V,E,c) ein Netzwerk mit Quelle s und Senke t. Sei f ein zufässiger Fluss und C⊆E ein Schnitt. Dann gilt:
val(f)≤cap(c)
Beweis
Wir betrachten einen Schnitt C=σ+(U) für U⊂V mit s∈U und t∈/U für ein Netzwerk G=(V,E,c) mit Fluss f.
Nach der Definition des Flusswertes, entspricht dieser der Differenz aus der Summe des Flusses der ausgehenden Kanten aus der Quelle s und der Summe des Flusses der eingehenden Kanten in die Quelle s:
val(f)=exf(s)=e∈σ+(s)∑f(e)−e∈σ−(s)∑f(e)
Aus der Flusserhaltungbedingung folgt, dass die Summer der Überschüsse aller Knoten in U{s}0 ist:
Aus diesen Eigenschaften folgt, dass der Flusswert von f dem Überschüss über alle Knoten in U entspricht. Dieser übeschuss ist wiederum kleiner oder gleich der Schnittkapazität von C, da der Fluss einer Kante maximal gleich der Kapazität der Kante sein kann.
Gegeben ist ein Netzwerk G=(V,E,c) mit Quelle s und Senke t und Kapazitäten c(e)≥0, e∈E.
Dann entspricht der maximale Flusswert der minimalen Schnittkapazität.
Beweis
Wir betrachten einen Schnitt C=σ+(U) für U⊂V mit s∈U und t∈/U für ein Netzwerk G=(V,E,c) mit Fluss f.
Nach der Definition des Flusswertes, entspricht dieser der Differenz aus der Summe des Flusses der ausgehenden Kanten aus der Quelle s und der Summe des Flusses der eingehenden Kanten in die Quelle s:
val(f)=exf(s)=e∈σ+(s)∑f(e)−e∈σ−(s)∑f(e)
Aus der Flusserhaltungbedingung folgt, dass die Summer der Überschüsse aller Knoten in U{s}0 ist:
Aus diesen Eigenschaften folgt, dass der Flusswert von f dem Überschüss über alle Knoten in U entspricht. Dieser übeschuss ist wiederum kleiner oder gleich der Schnittkapazität von C, da der Fluss einer Kante maximal gleich der Kapazität der Kante sein kann.