3.8.4 Pareos
La teoría de redes y en particular el teorema del flujo máximo tienen muchas aplicaciones. Uno de los ejemplos más ilustrativos es el problema de hacer corresponder los elementos entre dos conjuntos.
Supongamos que tenemos una relación entre dos conjuntos, por ejemplo el caso de que 4 personas S1, S2, S3 y S4 solicitan trabajo y se tienen 4 trabajos disponibles T1, T2, T3, T4: El primero está capacitado para los trabajos T2 y T4, el segundo solicita a T1, T3 y T4 y el tercero a T2 y T4 y el cuarto para T2 y T4.
Podemos construir una red en base a esta relación agregando una fuente y un sumidero como se ve en la figura. Le asignamos así también a cada una de las aristas el valor de 1. VER EJEMPLO
La pregunta que nos hacemos es si se puede lograr un acomodo en donde todos tengan trabajo.
El problema se resuelve aplicando el algoritmo del flujo máximo y corte mínimo a la red así construida.
Un acoplamiento con el número máximo de aristas se obtiene cuando el flujo es máximo. También es posible ver que se tiene un acoplamiento completo, o sea que todos pueden conseguir trabajo, si el flujo equivale al número de elementos en el primer conjunto.
En el ejemplo anterior vemos que no es posible tener un acoplamiento completo.
BIBLIOGRAFIA:
I.) Matemáticas para computadora de Luis Alberto Lomeli Beherendt
---------------------------------------------------------------------------------------------------