Data Structures and Network Algorithms: 8.4 最小費用流

増加パスの概念は、より一般的なネットワークフローの問題に拡張できる。
Gを各辺[u, w]が容量とフローの1ユニットごとのコストcost(v, w)を持つグラフとする。
簡単のため、コストを歪対称的(skew symmetric)とする。すなわち (1)
フローfのコストは、(2)
フローは同じ流量を持つ全てのフローの中で最小のコストを持つとき、(3) であるという。
最小費用流問題とは、(4) である。

定理8.11

フローfは、(5)、またそのときに限り、費用最小である。

定理8.12

fを費用最小のフローとする。このとき (6) 、fにフローを増加して得られた (7) である。

補題8.4

費用最小増加法では、一連の増加パスは非減少のコストを持つ。

解答
1.
2.
3. 費用最小
4. 費用最小な最大流を見つける問題
5. その残余グラフRがコストが負である閉路を持たないとき
6. 費用最小の増加パスに沿って
7. フローも費用最小