Redes De Petri

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

En esta sección mostraremos que al concluir el algoritmo 4.El flujo en la red es máximo.

Mientras tanto, definiremos y analizaremos los cortes en las redes.

Sea G una red y consideremos el flujo F al concluir el algoritmo 84. Algunos vértices están etiquetados y otros no. Sea P (P) el conjunto de vértices etiquetados (no etiquetados). (Recuerde que P denota el complemento de P.) Entonces la fuente a está en P y el sumidero z esta en P. El conjunto S de aristas (v, w), con v E P y w E Pes un corte. Y la suma de las capacidades de las aristas en S es la capacidad del corte. Veremos que este corte tiene una capacidad mínima y como un corte mínimo corresponde a un flujo máximo

(teorema 9), el flujo F es máximo. Comenzamos con la definición formal de corte.

En esta sección, G es una red con fuente a y sumidero z. La capacidad de la arista (i, j) es Cij.

Definición

Un corte (P. P) en G' consta de conjunto P de vértices y el complemento P de P, con a ϵ P y z ϵ P.

Ejemplo 1

Consideramos la red G de la figura 1. Si hacemos P={a, b, d}, entonces P =(c, e, f, z) y (P, P) es un corte en G. Como muestra la figura, a veces indicamos un corte trazando una línea punteada para separar los vértices.

FIGURA 1 Un corteen una red. La línea punteada divide los vértices en los conjuntos

P= (a, b, d] YP= [e, e, f, z) produciendo el corte (P. P).

Ejemplo 2

La figura 10 muestra el etiquetado al final del algoritmo 4 para una red particular.

Si P (P) denota el conjunto de vértices etiquetados (no etiquetados), obtenemos el corte que se muestra en la figura 2.

FIGURA 2 Una red al finalizar el algoritmo4. El corre (P, P), P = {a, b. d} se obtiene al definir P como el conjunto de vértices etiquetados.

Ahora definiremos la capacidad de un corte.

Definición

La capacidad del corte (P, P) es el número

C(P, P)=∑ ∑ᵢ͵

ᵢϵp ͵ϵp

Ejemplo 1

La capacidad del corte de la FIGURA 8.3.1 es

Cbc + Cde=8

La capacidad del corte de la figura 8.3.2

Cbc + Cdc + Cde =6

Teorema

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,

(La notación ∑ significa la suma sobre todos los vértices i.)

Demostración. Observe que

pues cada lado de la ecuación es simplemente la suma de Fij sobre todas las i,j E P.

Ahora,

Un corte mínimo es un corte con capacidad mínima.

Teorema del flujo máximo y el corte mínimo.

Sea F un flujo en Gy sea (P, P) un corte en G. Si la igualdad se cumple en (8.3.1), entonces el flujo es máximo y el corte es mínimo. Además, la igualdad se cumple en (8.3.1) si y sólo si:

Demostración. El primer enunciado es inmediato.

La demostración del teorema 8.3.7 muestra que la igualdad se cumple precisamente, cuando de modo que la última afirmación también es verdadera.8.3.10

Ejemplo

En la figura 8.3.2, el valor del flujo y la capacidad del corte son ambos iguales a 6; por tanto, el flujo es máximo y el corte es mínimo. Podemos utilizar el teorema 9 para mostrar que el algoritmo 4 produce un flujo máximo.

Teorema

Al concluir, el algoritmo 4 produce un flujo máximo. Además, si P (respectivamente, P) es el conjunto de vértices etiquetados (respectivamente, no etiquetados) al concluir el algoritmo 4, el corte (P, P) es mínimo.

Demostración. Sea P el conjunto de vértices etiquetados (no etiquetados) de G al concluir el algoritmo 4. Consideremos una arista (i, J), donde i E P,} E P. Como i está etiquetado, debemos tener.

Fᵢ͵=Cᵢ͵:

En caso contrario, habríamos etiquetado} en las líneas 23 y 24. Ahora, consideremos una arista (j, i), donde

j ϵ P, i ϵ P. Como i está etiquetado, debemos tener

Fᵢ͵ =0;

En caso contrario, habríamos etiquetado} en las líneas 30 y 31. Por el teorema 9, al concluir el algoritmo 4, el flujoes máximo y el corte (P, P) es mínimo.

8.3.10

ACOPLAMIENTO

DEFINICIÓN

En esta sección consideraremos el problema de hacer corresponder los elementos de un conjunto con los elementos de otro conjunto. Veremos que este problema se puede reducir a determinar un flujo máximo en una red. Comenzaremos con un ejemplo.

Ejemplo 1

Supongamos que cuatro personas A, B, e y D realizan una solicitud para cinco trabajos J1, J2, J3, J4 Y J5 y suponga que el solicitante A está calificado para los trabajos J2y J5; el solicitante B está calificado para los trabajos J2 y J5; el solicitante C está calificado para los trabajos J1, J3, J4 Y J5; y el solicitante D está calificado para los trabajos J2 y J5. ¿Es posible hallar un trabajo para cada solicitante?

La situación se puede modelar mediante la gráfica de la figura 8.4.1. Los vértices representan a los solicitantes y los trabajos. Una arista une un solicitante con un trabajo para el cual el solicitante está calificado. Podemos mostrar que no es Posible asociar un trabajo a cada solicitante, si nos fijarnos en los solicitantes A, B y D, quienes son calificados para los trabajos J2 y J5 Si A y B reciben un trabajo, no quedaría un trabajo para D. Por tanto, no existe una asignación para A, B, e y D.

FIGURA 1 Solicitantes(A, B, C, D) y trabajos(J1, J2, J3, J4, J5) Una arista une un solicitante con un trabajo para el cual está calificado. Las líneas continuas muestran un acoplamiento máximo (es decir, el mayor número de solicitantes tiene trabajo).

EJEMPLO 8.4. 1

En el ejemplo 1, un acoplamiento consiste en hallar trabajos para las personas calificadas. Un acoplamiento máximo encuentra trabajo para el mayor número de personas. En la gráfica de la figura 1 aparece con líneas continuas un acoplamiento máximo. Un acoplamiento completo encuentra trabajo para todos. Hemos mostrado que la gráfica de la figura 1 no tiene un acoplamiento completo. A continuación damos las definiciones formales.

DEFINICION

Sea G una gráfica dirigida, bipartita,

...