Prueba de existencia de corte mínimo de flujo máximo

Question

Dejar $G = (V, E)$ ser un gráfico dirigido con capacidades de borde $c: E \rightarrow \mathbb{R}_{\geq 0}$, $s,t \in V$. Asume que hay una ventaja$(u, v) \in E$ de modo que tenga plena capacidad en cada máx. $(s,t)$-fluir. Entonces existe al menos un mínimo$(s,t)$-cortar $(X, V\backslash X)$ en G tal que $u \in X$ y $v \in V \backslash X$.

Llevo horas intentando probar esta cuestión, usando contraposición y prueba por contradicción. Creo que me estoy perdiendo algo. ¿Me puede ayudar?

Answer 1

Pista: deja $c_0$ ser la capacidad mínima de un $(s,t)$-cortar y dejar $c_1$ ser la capacidad mínima de un $(s,t)$-cortar con $u\in X$ y $v\in V\setminus X$. Si$c_1>c_0$ entonces puede disminuir la capacidad de $(u,v)$ por $\min(c_1-c_0,c(u,v))>0$ sin cambiar el corte mínimo.