Esta página contiene varios ejercicios corregidos sobre problemas de flujo máximo. Esos problemas utilizan principalmente el Ford-Fulkerson algoritmo y la solución de corte mínimo.
Ejercicio 1
Usando el método Ford-Fulkerson, calcule un flujo máximo en la siguiente red:
Ejercicio 2
La siguiente figura muestra una red de flujo en la que se muestra un flujo st. La capacidad de cada borde aparece como una etiqueta junto al borde, y los números en los cuadros dan la cantidad de flujo enviado en cada borde. (Los bordes sin números en recuadros no tienen ningún flujo que se envíe). ¿Cuál es el valor de este flujo? ¿Es este un flujo st máximo en este gráfico? Si no es así, encuentre un flujo st máximo. Encuentra un corte en pt mínimo. (Especifique qué vértices pertenecen a los conjuntos del corte).
El valor de este flujo es 17. No, este no es un flujo máximo. Podemos encontrar un caudal máximo observando la red residual. En este caso, a partir del flujo dado, podemos obtener un flujo máximo con una única ruta de aumento, szyxwt. Entonces el flujo máximo tiene valor 19.
Podemos encontrar un corte mínimo utilizando la red residual para el caudal máximo final. Comenzando en s, encuentre todos los vértices que son accesibles desde s en la red residual. Esto forma un conjunto en el corte mínimo. Los otros vértices forman la otra parte del conjunto del corte. Entonces, un corte mínimo en este caso son los dos conjuntos {s; z} y {x; w; y; t}.
Puede comprobar que la capacidad de este corte (es decir, la capacidad total de los bordes de {s; z} a {x; w; y; t}, que consta de los bordes dirigidos (s; w); (s; x) ; (z; y); y (z; t) es 19, como lo garantiza el teorema de flujo máximo / corte mínimo.
Ejercicio 3
Describa un algoritmo eficiente que encuentre un nuevo flujo máximo si la capacidad de un borde en particular aumenta en una unidad. Describe un algoritmo eficiente que encuentre un nuevo flujo máximo si la capacidad de un borde en particular disminuye en una unidad.
Suponga que la arista de u a v aumenta su capacidad en uno. A partir del flujo máximo anterior F, simplemente haga una nueva iteración del algoritmo de Ford-Fulkerson con el gráfico modificado: El gráfico de flujo residual aumenta la capacidad del borde (u; v) con uno. Haga una búsqueda gráfica para ver si hay alguna ruta en el gráfico de flujo residual a lo largo de la cual el flujo pueda aumentar. Si hay uno, debe haber un flujo de tamaño uno (porque todos los flujos son números enteros). Si no hay flujo en el gráfico de flujo residual, F sigue siendo el flujo máximo.
Suponga que la arista de u a v disminuye su capacidad en uno. Si el flujo máximo anterior F no usó la capacidad total de (u; v), dicho cambio no cuenta en absoluto. De lo contrario, actualizamos el flujo de la siguiente manera:
Dado que el flujo que ingresa a u es una unidad más que el flujo que sale de él y el flujo que ingresa a v es una unidad menos que el flujo que sale de él, no hay forma de que debamos transferir un flujo unitario de u a v. Por lo tanto, busque en el gráfico de flujo residual una ruta de u a v a lo largo de la cual el flujo pueda aumentar en uno. Si existe tal ruta, actualizamos F con el flujo.
Si no existe tal camino, debemos reducir el flujo de sa u y de v a t con una unidad. Hacemos esto encontrando una ruta de u a s en el gráfico de flujo residual a lo largo de la cual el flujo puede aumentar en uno y una ruta de t a v a lo largo de la cual el flujo puede aumentar en uno. (Debe haber tales caminos, porque teníamos un flujo de sa t a través de (u; v)). Luego, actualice F con estos dos flujos.
Ejercicio 4
Teniendo en cuenta el siguiente flujo, ¿cómo aumentar el flujo?
El corte mínimo está hecho, por lo que conocemos los cuellos de botella en el gráfico. La suma de las capacidades en la fuente es 22 y 24 en el sumidero, llegamos a la conclusión de que no podemos tener más de 22. Por lo tanto, necesitamos encontrar una ruta desde para aumentar el flujo en 2, y una ruta desde hasta para aumentar el fluir por 1. El ejercicio anterior le da a un algoritmo una idea para alcanzar este objetivo. Podemos aumentar las capacidades con bordes de corte mínimos.
Ejercicio 5
En el gráfico bipartito opuesto, los vértices T1… T6 representan trabajadores y los vértices E1… E6 representan trabajos. Una ventaja conecta a un trabajador con un empleo si el trabajador tiene las calificaciones necesarias para ocupar este empleo. ¿Cómo asignar puestos de trabajo a los trabajadores para minimizar el número de desempleados?
Asignar un trabajo a una persona equivale a "seleccionar" un borde. Los Ti están conectados a una fuente ficticia con una capacidad de 1 (lo mismo para los Ei a un sumidero ficticio). Los bordes del gráfico bipartito tienen una capacidad de 1. Luego busca un flujo máximo.
Ejercicio 6
Suponga que está organizando una conferencia en la que los investigadores presentan los artículos que han escrito. Los investigadores que quieran presentar un artículo envían un trabajo a los organizadores de la conferencia. Los organizadores de la conferencia tienen acceso a un comité de revisores que están dispuestos a leer cada uno de los artículos.
Cada envío de un artículo es revisado por hasta revisores. Además, cada envío tiene un tema en particular y cada revisor tiene una especialización para un conjunto de temas, por lo que los artículos sobre un tema determinado solo son revisados por los revisores que son expertos en ese tema.
Los organizadores de la conferencia deben decidir qué revisores revisarán cada artículo (o, de manera equivalente, qué artículos serán revisados por qué revisores). Explique cómo podrían usar una red de flujo para resolver este problema.
Hay un conjunto A de artículos y un conjunto B de revisores. Agregue un borde dirigido (α, β) al gráfico si algún artículo α en A podría ser revisado por algún revisor β en B, es decir, el artículo es sobre un tema en el que el revisor es experto. Establezca la capacidad de esa arista en 1. Agregue un vértice s (fuente) y un vértice t (terminal). Para cada α en A, agregue un borde (s, α) de capacidad mA. Para cada β en B, agregue un borde (β, t) de capacidad mB. Ejecute Ford-Fulkerson para obtener el flujo máximo y calcular el corte correspondiente (A, B). Esto da el conjunto de aristas que corresponden a la asignación de artículos a revisores.
Ejercicio 7
Sea un conjunto de máquinas y tareas. Una máquina LI se puede utilizar como máximoI tiempo. Una tarea Cj se puede utilizar como máximo bj tiempo. La tabla de oferta y demanda representa máquinas y tareas, y la capacidad de realizar una tarea en una máquina determinada (en blanco).
Cree máquinas / tareas de gráficos bipartitos y luego haga una fuente ficticia (sumidero ficticio) con capacidades de arco aI (y Bj). Luego resuelva el problema de flujo.
ES 
FR 
EN