Esta página contiene varios ejercicios corregidos sobre problemas de flujo máximo. Estos problemas utilizan principalmente el algoritmo Ford-Fulkerson y la solución de corte mínimo.
Ejercicio 1
Usando el método Ford-Fulkerson, calcule un rendimiento máximo en la siguiente red:
Ejercicio 2
La siguiente figura muestra una red de arroyos en la que se muestra un st stream. La capacidad de cada borde aparece como una etiqueta al lado del borde, y los números en los cuadros indican la cantidad de flujo enviado en cada borde. (Los bordes sin números encuadrados no tienen flujo enviado sobre ellos). ¿Cuál es el valor de este flujo? ¿Es este un punto de flujo máximo en este gráfico? Si no, encuentre una tasa de bits máxima st. Encuentra un corte mínimo. (Especifique qué vértices pertenecen a los conjuntos en la sección).
El valor de esta tarifa es de 17. No, no es una tarifa máxima. Se puede encontrar un rendimiento máximo observando la red residual. En este caso, a partir del flujo dado, podemos obtener el flujo máximo con una sola ruta de aumento, szyxwt. Por lo tanto, el caudal máximo tiene el valor 19.
Se puede encontrar un corte mínimo usando la red residual para el flujo máximo final. A partir de s, encuentre todos los vértices alcanzables desde s en la red residual. Esto forma un conjunto en el corte mínimo. Los otros vértices forman la otra parte definida del corte. Así, un corte mínimo en este caso son los dos conjuntos {s; z} y {x; w; y; t}.
Puede verificar que la capacidad de este corte (es decir, la capacidad total de los bordes de {s;z} a {x;w;y;t}, que consiste en 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
Describir un algoritmo eficiente que encuentra un nuevo flujo máximo si la capacidad de un borde particular aumenta en una unidad. Describa un algoritmo eficiente que encuentre un nuevo flujo máximo si la capacidad de un borde en particular disminuye en una unidad.
Suponga que el borde de u a v aumenta su capacidad en uno. A partir del flujo máximo F anterior, basta con hacer una nueva iteración del algoritmo de Ford-Fulkerson con el grafico modificado: El gráfico de flujo residual aumenta la capacidad del borde (u; v) en uno. Realice una búsqueda gráfica para ver si hay una ruta en el gráfico de flujo residual a lo largo de la cual el flujo puede aumentar. Si lo hay, 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 es siempre el flujo máximo.
Suponga que el borde de u a v disminuye su capacidad en uno. Si la tasa máxima anterior F no utilizó la capacidad total de (u;v), tal cambio no importa en absoluto. De lo contrario, actualizamos el feed de la siguiente manera:
Dado que el flujo que entra en u es mayor en una unidad que el flujo que sale y el flujo que entra en v es menor que el flujo que sale en una unidad, es imposible transferir una unidad de flujo de u a v. Por lo tanto, busque en el gráfico de flujo residual un camino de u a v a lo largo del cual el flujo pueda aumentar en uno. Si existe tal ruta, actualizamos F con la secuencia.
Si no existe tal camino, debemos reducir el flujo de s a u y de v a t en una unidad. Para hacer esto, encontramos un camino de u a s en el gráfico de flujo residual a lo largo del cual el flujo puede aumentar en uno y un camino de t a v a lo largo del cual el flujo puede aumentar en uno. (Debe haber esos caminos, porque teníamos un flujo de s a 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?
Se realiza el corte mínimo, 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, deducimos que no podemos tener más de 22. Por lo tanto, debemos encontrar un camino de a para aumentar el caudal en 2, y un camino de a para aumentar el flujo por 1. El ejercicio anterior le da una idea a un algoritmo para lograr 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 puestos de trabajo. Un beneficio conecta a un trabajador con un trabajo si el trabajador tiene las calificaciones necesarias para ese trabajo. ¿Cómo asignar puestos de trabajo a los trabajadores para minimizar el número de desempleados?
Asignar un trabajo a una persona es como "seleccionar" un borde. 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 donde los investigadores presentan artículos que han escrito. Los investigadores que deseen presentar un trabajo envían una comunicación a los organizadores de la conferencia. Los organizadores de la conferencia tienen acceso a un comité de revisores que están dispuestos a leer los artículos cada uno.
Cada envío de artículo es revisado por tantos revisores como sea posible. Además, cada envío tiene un tema 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 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 arroyos 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 un artículo α en A puede ser revisado por un revisor β en B, es decir, el artículo trata sobre un tema en el que el revisor es un experto. Establezca la capacidad de este borde en 1. Agregue un vértice s (fuente) y un vértice t (terminal). Para cada α en A, agregue un borde (s, α) de capacitancia mA. Para cada β de B, agregue un borde (β , t) de capacidad mB. Ejecute Ford-Fulkerson para obtener el caudal máximo y calcule el corte correspondiente (A,B). Esto da el conjunto de aristas que corresponden a la asignación de artículos a los revisores.
Ejercicio 7
Considere un conjunto de máquinas y tareas. Una máquina de Li se puede utilizar en la mayoría de los casos. Una tarea Cj se puede utilizar como máximo bj tiempo. El gráfico de oferta y demanda representa máquinas y tareas, y la capacidad de realizar una tarea en una máquina determinada (vacía).
Cree un gráfico bipartito, luego haga una fuente ficticia (sumidero ficticio) con capacidades de arco ai (y bj). Luego resuelve el problema de flujo.
ES 
FR 
EN