Proyecto #5 Problemas de Corte Minimo

Definición de corte minimo

En lo que respecta a las redes, un corte es un conjunto de corte en el cual quedan dos partes disjuntas del conjunto de vértices, V1 y V2 que, situados en la red, dejan la fuente en una de ellas y al sumidero en la otra.

Definición de capacidad de un corte

Se llama capacidad de un corte a la suma:

S Capacidad (v,w) ; v Є V1 , w ЄV2
V1 es la parte que contiene a la fuente
V2 es la parte que contiene al sumidero

Sea F un flujo en G y sea (P, P) un corte en G. Entonces la capacidad de (p, p) es mayor o igual que el valor de F; es decir:

Si ЄP S JЄP Cij ³ S i F ai

La notación Si : Significa la suma sobre todos los vértices i
Demostración: observe Sj ЄP S iЄP Cji = Sj ЄP S iЄP F ij

Pues cada lado de la ecuación es simplemente la suma de Fij sobre todas las de i, j Є P

Ahora

S i F ai= Sj ЄP Sj Fji -Sj ЄP Sj

=Sj ЄP SiЄP Fji +Sj ЄP SiЄP Fji- =Sj ЄP SiЄP Fji

=Sj ЄP SiЄP Fji -Sj ЄP SiЄP Fji- £Sj ЄP SiЄP Fji£ Sj ЄP SiЄP Cji

El corte minimal nos da la minima capacidad del corte efectuado en el grafo.

Para el cálculo de la capacidad del corte minimal no se tienen en cuenta las capacidades de las aristas del corte cuya dirección sea contraria al sentido de flujo.

TEOREMA DEL FLUJO MÁXIMO Y EL CORTE MÍNIMO

Sea F un flujo en G y sea (P, P) un corte en G si la igualdad se cumple entonces el flujo es máximo y el corte es mínimo si y solo si:

1) FI J = CI J para i ЄP, J Є P

2) Fij =0 para i Є P, J Є P

El valor del flujo maximal de una red es igual a la capacidad del corte minimal que se puede aplicar a la red.

Se puede obtener, por tanto el corte minimal de una red, conociendo el flujo maximal de la red obtenido mediante la aplicación del algoritmo anteriormente definido.