3.8.3 Teorema del Corte Minimal
Un corte T es una selección cualquiera de nodos de una red tal que la fuente F está en T y el sumidero S no está en T. Vemos por lo tanto que S ∈ Tc.
Definición: Decimos que un corte es mínimo si la capacidad tiene un valor mínimo.
Ejemplo. La capacidad del corte del ejemplo 1 es w(F,e) + w(f,h) + w(c,d) = 3 + 6 +5 = 14
Teorema. Si tenemos una red R con flujo f y un corte T.
Entonces si la igualdad del teorema anterior se cumple se tiene un flujo máximo y un corte mínimo. En este caso se tiene: f(i,j) = w(i,j) si i ∈ T, j NO∈ T y también f(i,j) = 0 si i NO∈ T, j ∈ T.
A este teorema se le conoce como el teorema del flujo máximo y corte mínimo.
BIBLIOGRAFIA:
I.) Matematicas para computadora de Luis Alberto Lomeli Beherendt
---------------------------------------------------------------------------------------------------