Max-Flow-Min-Cut-Existenznachweis

Question

Lassen $G = (V, E)$ ein gerichteter Graph mit Kantenkapazitäten sein $c: E \rightarrow \mathbb{R}_{\geq 0}$, $s,t \in V$. Angenommen, es gibt eine Kante$(u, v) \in E$ so dass es in jeder max $(s,t)$-fließen. Dann gibt es mindestens ein Minimum$(s,t)$-Schnitt $(X, V\backslash X)$ in G so dass $u \in X$ und $v \in V \backslash X$.

Ich habe stundenlang versucht, diese Frage mit Kontraposition und einem Beweis durch Widerspruch zu beweisen. Ich glaube, ich vermisse etwas. Kannst du mir helfen?

Answer 1

Hinweis: Lassen Sie $c_0$ die Mindestkapazität eines sein $(s,t)$-cut und lassen $c_1$ die Mindestkapazität eines sein $(s,t)$-Schnitt mit $u\in X$ und $v\in V\setminus X$. Wenn$c_1>c_0$ dann können Sie die Kapazität von verringern $(u,v)$ durch $\min(c_1-c_0,c(u,v))>0$ ohne den minimalen Schnitt zu ändern.