Arcos en serie con capacidades 8 y 6: ¿flujo máximo?
El menor limita ambos.
En serie, la conservación obliga al mismo flujo por ambos arcos.
La capacidad menor,6, impone una cota superior.
Enviar6 por ambos es factible, así que el máximo es 6.
Dos rutas sin arcos compartidos tienen capacidades 3 y 4. ¿Flujo total máximo?
Las capacidades independientes se suman.
Las dos rutas dadas no comparten arcos ni otro límite adicional en el modelo indicado.
Se pueden saturar respectivamente con 3 y4.
A un nodo intermedio entran 7 y salen 2 por un arco. ¿Cuánto debe salir por el otro si no hay más arcos?
Conservación: entradas iguales a salidas.
El nodo no produce ni consume, por lo que entradas=salidas.
La salida restante debe ser5.
Un corte tiene arcos salientes de capacidades 2,5,1. ¿Cuál es su capacidad?
Suma solo los que salen del conjunto.
La capacidad de un corte suma capacidades que salen del conjunto fuente.
Con los arcos indicados, sumamos2+5+1.
La capacidad es 8.
Explica por qué un corte da una cota para todo flujo.
Suma las ecuaciones de conservación dentro del conjunto.
Sumamos los balances de nodos dentro del lado S del corte; los arcos internos se cancelan.
El valor del flujo es salida por el corte menos entrada, y cada salida está limitada por su capacidad.
Restar entradas no aumenta el resultado, de modo que el valor no supera la suma de capacidades salientes.