El objetivo de este artículo es explicar un método que permite calcular la cantidad máxima de materia que se puede hacer transitar entre un punto A y un punto B, tomando una red de rutas o conductos cuyas caracteristicas son conocidas.

He aquí un problema concreto que debería aclarar y precisar el sentido de la frase anterior. Los bomberos acaban de recibir un llamado de emergencia pues una casa de su barrio está en llamas. Pregunta : ¿cómo deben utilizar sus recursos para llevar un máximo de agua del lago vecino a la casa que arde ? Para permitirnos razonar, se necesita un gráfico que represente las diferentes instalaciones hidráulicas que entran en juego. Estas son :

Por ejemplo, se ve en este gráfico que dos conductos de agua parten del lago : uno llega directamente al cuartel de bomberos, mientras que el segundo surte una planta de depuración (representada por la burbuja arriba a la izquierda).
El cuartel de bomberos está directamente unido con un grifo de incendios (que se supondrá que está situado cerca de la casa en llamas), así como a un camión de bomberos que puede hacer el camino hasta la casa, etc.
Las flechas simbolizan entonces los conductos entre los diversos actores en juego. Se subraya que cada flecha tiene al medio un pequeño rectángulo cuya longitud varía. Esta longitud representa el caudal del conducto simbolizado. Se ve, por ejemplo, que el conducto que une el lago con la planta depuradora tiene un calibre mucho más grueso que el que une la planta de depuración con el grifo de incendios.

Dicho esto, el asunto que nos preocupa se vuelve claro : se busca determinar qué cantidad de agua hacer pasar a través de cada uno de los conductos de manera que, en último término, llegue el máximo de agua a la casa (o, lo que significa lo mismo, el máximo de agua salga del lago).

Un método de resolución

La construcción de base : una idea natural

Como acabamos de explicar, nuestro objetivo es hacer pasar el máximo de agua posible del lago a la casa. Para esto, es natural comenzar por buscar un camino que una el lago con la casa y hacer pasar el máximo de agua a lo largo de ese camino. Concretamente, uno puede elegir el camino pasando primero por el cuartel y luego el grifo (pero por supuesto no es la única opción posible). Mientras más largo sea el camino, menor el caudal recibido por las dos últimas canalizaciones por igual. Se decide entonces, para comenzar, hacer circular una cantidad de agua igual a ese caudal común retenido a lo largo del camino.
Después de esta decisión, la situación queda así :

Como usted habrá comprendido, las zonas azuladas sobre las flechas representan el agua que transita por medio de los respectivos conductos.

Se puede ahora reproducir el mismo razonamiento anterior a excepción de que ya no se tomen más en cuenta los conductos que unen el cuartel con el grifo de incendios y el grifo con la casa, debido a que ambos están saturados (esto significa que no se puede hacer pasar más agua suplementaria por esos conductos). Se puede, sin embargo, encontrar de nuevo un camino entre el lago y la casa que evite esos dos conductos saturados. Por ejemplo, el que pasa sucesivamente por el cuartel y luego por el camión. Se decide por lo tanto enviar a lo largo de ese camino la máxima cantidad de agua posible, es decir, la cantidad exacta de agua necesaria para saturar la canalización que une el lago con el cuartel (que esta vez es el factor limitante). Se llega así a la siguiente situación :

Se comprueba que hay aún un camino, que no toma ningún conducto saturado, que une el lago con la casa : es el que pasa sucesivamente por la planta de depuración, el cuartel, y después el camión. El conducto limitante, esta vez, es el que une la planta de depuración con el cuartel y se envía entonces a lo largo del camino encontrado la cantidad exacta de agua necesaria para saturar ese conducto .

El desatascamiento de los conductos

Si se observa por un instante el gráfico al cual se ha llegado (representado a la derecha), se comprueba que ya no hay ningún camino entre el lago y la casa que lleve conductos no saturados. Parece que ya no es posible repetir la construcción que acabamos de hacer tres veces. ¿Quiere decir que hemos hecho una utilización óptima de la red ? ¡Desafortunadamente, no ! En efecto, examinemos con más atención el gráfico de la derecha y hagamos los tres siguientes comentarios :

• El grifo de incendios recibe toda su agua del cuartel, mientras que el conducto que lo une con la planta de depuración no es utilizado.
• Todavía es posible llevar agua al grifo pasando por la planta de depuración, sin saturar los conductos que intervienen en este recorrido (eso no se hizo hasta ahora ya que el grifo no puede reenviar más agua que la que recibe actualmente).
• Desatascar el conducto saturado entre el cuartel y el grifo permitiría de facto al cuartel hacer transitar agua suplementaria hasta la casa utilizando el camión.

Así, se encontró una solución para transportar agua suplementaria del lago a la casa :

• primero, se pide al cuartel que proceda a una nueva repartición de su distribución utilizando primero agua para el camión pero, como contrapartida, mandando menos al grifo de incendios, y
• segundo, se compensa las pérdidas del grifo haciendo transitar agua vía la planta de depuración.

Esto equivale a decir que se hace pasar agua según el camino representado en el gráfico de la izquierda. Se subraya que ese camino ’’hace volver’’ el conducto que se desea desatascar... y por otra parte es justamente este ’’hacer volver’’ el que simboliza el desatascamiento. Si se desea (aunque no sea eso lo que ocurre en la práctica), se puede decir que se hace pasar agua a contracorriente por ese conducto y que eso compensa una parte del caudal que corría ya por el conducto en el sentido correcto.

Recapitulativo : el algoritmo de Ford-Fulkerson

En pocas palabras, el método que se acaba de presentar puede resumirse como sigue :

1. Se busca un camino que una la fuente (aquí, el lago) con el objetivo (aquí, la casa), que no lleve (en el sentido de recorrido) ningún conducto saturado y que eventualmente pueda llevar en sentido contrario un conducto por el cual ya pasa agua.
2. Se hace pasar la cantidad máxima posible de materia (aquí, agua) a lo largo del camino encontrado en la etapa anterior.
3. Se vuelve a la primera etapa.

Este método lleva el nombre de algoritmo de Ford-Fulkerson, por el nombre de sus dos inventores.

El momento donde uno se detiene

Efectuando las últimas modificaciones a nuestro ejemplo, se llega a la siguiente situación :

Ahora ya no se encuentra ningún camino que una el lago con la casa que no lleve conductos saturados, pese a que incluso se autorizaría a hacer volver agua por algunos conductos. ¿Quiere decir que se ha encontrado una utilización óptima de las instalaciones ? Esta vez ¡la respuesta es sí ! Pero, ¿cómo estar seguros ?

En nuestro gráfico, pintemos el lago de gris, así como las instalaciones a las cuales se puede todavía hacer llegar agua desde el lago, llevándola por conductos no saturados o haciéndola volver por conductos utilizados. Se obtiene el gráfico de la derecha.
Por ejemplo, la planta de depuración está en gris, ya que ella todavía puede ser alimentada con agua directamente desde el lago. Del mismo modo, el cuartel está en gris debido al camino que pasa por la planta de depuración y el grifo de incendios, y luego se devuelve por el conducto que une este último con el cuartel. De modo general, coloreando de gris las instalaciones, resulta que :

• todo conducto que une una instalación en gris con una instalación sin gris está saturada, y
• todo conducto que une una instalación no gris con una instalación gris no está utilizada.

Consideremos ahora una hipotética mejor solución y comparemos los flujos de agua que pasan entre las regiones en gris y no gris en la solución que se encontró por una parte, y en la solución donde se supone la existencia por otra parte.

• En el sentido ’’gris’’ → ’’no gris’’, ciertamente hay más agua que pasa en la solución a la cual llegamos, ya que en esta todos los conductos están saturados.
• En el sentido ’’no gris’’ → ’’gris’’, ciertamente hay más agua que pasa en la solución hipotética, ya que en la solución a la cual llegamos no pasa nada en absoluto.

De ese modo, si uno hace el balance, la solución que encontramos hace pasar más agua de la zona gris a la no gris (contando en forma negativa el agua que pasa en sentido contrario) que en cualquier otra solución hipotética. Pero por otro lado, la cantidad de agua que pasa de la zona gris a la no gris no es otra que la cantidad de agua que pasa del lago a la casa, dado que no hay acumulación de agua en ninguna instalación. Así, se ha demostrado perfectamente que la solución que encontramos es mejor o equivalente a cualquier otra solución. En otras palabras, ¡se encontró el óptimo !

¿Aplicaciones ?

Por supuesto, el algoritmo de Ford-Fulkerson que se acaba de presentar no solo permite resolver el ejemplo de juguete descrito en este artículo, sino que se aplica a numerosos otros problemas concretos. Por ejemplo puede ser utilizado por una empresa que quiere calcular qué cantidad máxima de mercadería puede despachar desde su lugar de fabricación hasta su punto de venta utilizando las vías férreas.

Este artículo (en inglés) explica cómo usar el algoritmo de Ford-Fulkerson para resolver el problema llamado de los matrimonios, cuyo objetivo es establecer la lista de matrimonios más larga posible sabiendo que cada una y cada uno (supuestamente, todos heterosexuales) han preestablecido una lista de personas con las cuales aceptarían casarse. Vea también este artículo en Images des Maths sobre otra presentación del lema de los matrimonios (sin vínculo explícito con el algoritmo de Ford-Fulkerson).

El algoritmo de Ford-Fulkerson encuentra también aplicaciones en el campo de las matemáticas puras. Por ejemplo, puede ser utilizado para dar otra demostración (que tiene la ventaja de extenderse a situaciones más generales) del resultado del artículo Un problème de remplissage de verres en este sitio. ¿Sabría usted encontrarla ?

Aquí hay otra aplicación más asombrosa : es utilizada en el tratamiento de imágenes para lo que se llama la texturización de imágenes. En términos prácticos, se tiene un motivo de tamaño pequeño que se desea repetir de la forma más bonita posible sobre una gran superficie. Por ejemplo, a partir de una fotografía de algunas espigas de trigo, se desearía fabricar una imagen representando todo un campo de trigo. Tal vez usted ya haya hecho el experimento : colocar simplemente una imagen al lado de la otra, como en la figura de abajo, por lo general da un resultado mediocre.

Para mejorar esto, la idea natural consiste en hacer superposiciones y recortes. Es en la parte del ’’recorte’’ donde el algoritmo de Ford-Fulkerson hace una contribución decisiva. Para mayores detalles sobre este tema, los derivamos a [1] (artículo en inglés).

Juegue por sí mismo

Los autores de este artículo han programado una pequeña aplicación web mostrando el algoritmo de Ford-Fulkerson en acción en una cierta cantidad de situaciones. Está aquí. Atención : se necesita un navegador reciente.

Referencias

[1]
V. Kwatra, A. Schodl, I. Essa, G. Turk, A. Bobick, Graphcut Textures : Image and Video Synthesis Using Graph Cuts, disponible aquí