Flujo máximo y cambiarlo por productos de capacidad de los bordes

Question

Si C es una constante positiva, es decir, si sumamos o restamos C a la capacidad de todas las aristas, el flujo máximo cambia (puede aumentar o disminuir). Mi pregunta es, ¿por qué si multiplicamos la capacidad de todas las aristas por C, el flujo máximo es producto de C?

¿por qué es esto cierto?

Answer 1

Una forma de pensar en esto es mediante el infame teorema del flujo máximo y el corte mínimo, que establece;

El valor máximo del flujo desde un nodo fuente s a un nodo sumidero t en una red capacitada es igual a la capacidad mínima entre todos los cortes s-t. [S,Sbar]

Dado que, después de multiplicar todas las capacidades por una constante C, el corte s-t mínimo no cambia, además las capacidades de los arcos que emanan de S se multiplican todas por C, la nueva capacidad del corte s-t mínimo será C veces la capacidad anterior, lo que significa que el nuevo valor de flujo máximo será el valor de flujo máximo anterior * C.

Answer 2

Supongamos que nos dan una función de flujo y una función de capacidad. Obsérvese que si multiplicamos todas las capacidades y flujos por $C$ Entonces obtendremos el flujo adecuado. De hecho, es trivial comprobar que las restricciones de capacidad, la simetría de la inclinación y las conservaciones del flujo se mantienen. Además, el valor del flujo es $C$ veces más grande. Del mismo modo, para cualquier flujo en la red con capacidades multiplicadas por $C$ podemos construir un flujo con $C$ veces más pequeño valor.