Preuve d'existence min-cut max-flow

Question

Laisser $G = (V, E)$ être un graphe orienté avec des capacités d'arête $c: E \rightarrow \mathbb{R}_{\geq 0}$, $s,t \in V$. Supposons qu'il y ait un avantage$(u, v) \in E$ de sorte qu'il ait la pleine capacité dans chaque max $(s,t)$-couler. Alors il existe au moins un minimum$(s,t)$-Couper $(X, V\backslash X)$ en G tel que $u \in X$ et $v \in V \backslash X$.

J'essaye de prouver cette question depuis des heures, en utilisant la contraposition et une preuve par contradiction. Je pense qu'il me manque quelque chose. Peux-tu m'aider?

Answer 1

Indice: laissez $c_0$ être la capacité minimale d'un $(s,t)$-cut, et laisser $c_1$ être la capacité minimale d'un $(s,t)$-cut avec $u\in X$ et $v\in V\setminus X$. Si$c_1>c_0$ alors vous pouvez diminuer la capacité de $(u,v)$ par $\min(c_1-c_0,c(u,v))>0$ sans changer la coupe minimale.