Muchos problemas de informática pueden estar representados por un grafo que consta de nodos y vínculos entre ellos. Algunos ejemplos son los problemas de flujo de red, que involucran el transporte de bienes o material en una red, como un sistema ferroviario.
Puedes representar un flujo de red mediante un gráfico cuyos nodos son ciudades y cuyos arcos son líneas ferroviarias entre ellos. (Se llaman flujos porque sus propiedades son similares a las del agua que fluye a través de una red de tuberías).
Una restricción clave en los flujos de red es que cada arco tiene una capacidad, es decir, la cantidad máxima que se puede transportar a través del arco en un período fijo.
El problema máximo de flujo es determinar la cantidad total máxima que se puede transportar a través de todos los arcos de la red, sujeta a las restricciones de capacidad.
La primera persona en estudiar este problema fue el matemático ruso A.N. Tolstói, en la década de 1930. En el siguiente mapa, se muestra la red ferroviaria real con la que quería encontrar el máximo de flujo.
OR-Tools proporciona varios agentes de resolución para problemas de flujo de red en sus bibliotecas de graph.
En las siguientes secciones, se presentan ejemplos de problemas de flujo de red y se muestran cómo resolverlos: