0 Daumen
183 Aufrufe

Aufgabe:

Sei G=(V,A) G=(V, A) ein Digraph mit Kapazitäten u : AR+ u: A \rightarrow \mathbb{R}_{+} und Balancen b : VR b: V \rightarrow \mathbb{R} mit vVb(v)=0 \sum \limits_{v \in V} b(v)=0 . Zeigen Sie, dass es genau dann einen b b -Fluss gibt, wenn
δ+(X)u(a)vXb(v) fu¨r alle XV. \sum \limits_{\delta^{+}(X)} u(a) \geq \sum \limits_{v \in X} b(v) \quad \text { für alle } X \subseteq V .
Hinweis: Benutzen Sie die Konstruktion eines Hilfsnetzwerkes (G,u,s,t) \left(G^{\prime}, u^{\prime}, s, t\right) von Lemma 8.2 und das Max-Flow-Min-Cut-Theorem bezüglich der Existenz eines s-t-Flusses in G G^{\prime} , der die Flüsse aus s und nach t t sättigt.

Avatar von

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen