Estos problemas pueden tratar flujos en cañerías, energías, vehículos en sus respectivas redes acorde al problema (transportar la mayor cantidad de elementos, conocer donde se da el mayor flujo para cierto fin, etc).

• Se pueden representar mediante grafos donde los ejes/aristas transportan algún tipo de flujo y los vértices son conmutadores de tráfico entre estos ejes/aristas.
• Capacidad es la cantidad máxima posible a transportar por un eje.
• Fuente es el vértice que genera el tráfico saliente.
• Sumidero es el vértice que absorbe el tráfico entrante.
• Flujo es la cantidad transportada en un eje.
• Sea G(V, E) un grafo dirigido, para todo e en E llamaremos Ce (un valor entero mayor o igual a cero) a su capacidad, existe un único vértice “s” en V llamado fuente (sin ejes entrantes), existe un único vértice “t” en V llamado sumidero (sin ejer salientes), mientras tanto los demás vértices los llamaremos internos.
• El flujo entre s-t es una función que mapea a cada eje un valor real no negativo.

Corte

Consiste en dividir los nodos del mismo en dos conjuntos A y B donde “s” pertenece a A y “t” pertenece a B. Este corte define un limite al caudal máximo del flujo y cualquier flujo s-t debe cruzar en algún punto de A a B.

El problema del flujo máximo consiste en encontrar el flujo de máximo valor posible dada una red de flujo y es resuelto mediante el algoritmo de Ford-Fulkerson.

Grafo residual

Dada una red de flujo G y un flujo “f” en G, se define el grafo residual Gf al grafo con :

• Los mismos vértices de G.
• Ejes hacia adelante, es decir, para cada eje “e” en el que f(e) < Ce el mismo será incluído en Gf con capacidad Ce - f(e) (con la capacidad residual del flujo).
• Ejes hacia atrás, para cada eje “e” en el que f(e) > 0 incluiremos “e’” en el sentido contrario (si e = (u, v) entonces e’ = (v, u)) con capacidad f(e).

Cuellos de botella