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

Теорема:

[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].

Доказательство:

[math]\triangleright[/math]

Пусть [math] g [/math] — минимальный поток величины [math]a + \delta[/math] в [math]G[/math]. Рассмотрим поток [math]g - f[/math] в сети [math]G_f[/math]. Его величина равна [math]\delta[/math]. По теореме о декомпозиции его можно представить как сумму элементарных потоков вдоль путей [math]P_i : s \leadsto t[/math] и циклов [math]C_i[/math]. По лемме в этом представлении нет отрицательных циклов, так как поток [math]f[/math] минимальный, положительных циклов нет, так как поток [math]g[/math] минимальный. То есть [math]p(C_i) = 0[/math] для всех циклов. Тогда [math]p(g - f) = \sum\limits_{P_i} p(P_i)\cdot c_f(P_i) \geq p(P) \cdot \sum\limits_{P_i}c_f(P_i) = p(P) \cdot \delta[/math]. Тогда [math]\delta \cdot g_P[/math] — поток минимальной стоимости среди потоков величины [math]\delta[/math] в сети [math]G_f[/math]. Отсюда получаем требуемое.

[math]\triangleleft[/math]