Теорема Форда-Фалкерсона о потоке минимальной стоимости

Теорема:

[math] G [/math] — сеть с истоком [math] s [/math] и стоком [math] t [/math]. Пусть [math] f [/math] — поток минимальной стоимости в сети [math] G [/math] среди потоков величины [math] a [/math]. [math] P [/math] — путь минимальной стоимости [math] s \leadsto t [/math]. Тогда для [math]\forall \delta : 0 \leq \delta \leq c_f(P)[/math] поток [math]f + \delta \cdot f_P[/math] — поток минимальной стоимости среди потоков величины [math]a + \delta[/math].