Más Allá de la Capacidad Física

  El Algoritmo de Flujo Máximo

El objetivo del algoritmo de flujo máximo es determinar la cantidad total de flujo, f(s,t), que puede ser enviado desde el nodo fuente s al nodo sumidero t, respetando dos restricciones fundamentales:

1. Restricción de capacidad: Para cada arista $(u,v)\in E$, el flujo f(u,v) no puede exceder su capacidad c(u,v). Es decir, $0\le f(u,v)\le c(u,v)$.

2. Conservación del flujo: Para cada nodo intermedio $v\in V\setminus \{s,t\}$, la suma del flujo que entra al nodo es igual a la suma del flujo que sale del nodo. Formalmente, ${\sum }_{(u,v)\in E}f(u,v)={\sum }_{(v,w)\in E}f(v,w)$. Esto asegura que el flujo no se crea ni se destruye en nodos intermedios.

Algoritmos como Ford-Fulkerson (y sus variantes como Edmonds-Karp) o Dinic son los caballos de batalla para resolver este problema. Estos algoritmos operan encontrando caminos aumentantes en la red residual, que es una representación dinámica de las capacidades restantes en la red. Cada vez que se encuentra un camino aumentante, se incrementa el flujo total hasta que no se pueden encontrar más caminos.

En la ingeniería de sistemas, este algoritmo es vital para:

• Optimización de ancho de banda: Calcular la máxima capacidad de transferencia de datos entre dos puntos en una red de comunicaciones.

Ahora veamos un video explicativo sobre la Determinación de ancho de banda que requiere una empresa:

• Planificación de la capacidad de servidores: Determinar el máximo volumen de solicitudes que un clúster de servidores puede manejar.

• Análisis de fiabilidad de redes: Identificar la capacidad máxima de una red de suministro eléctrico o una tubería en un sistema hidráulico.

para ello es  bueno evaluar estos criterios:

• Credibilidad 
• Coherencia 
• Integridad 
• Fiablidad