読者です 読者をやめる 読者になる 読者になる

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. cost(v, w) = -cost(w, v)
2. cost(f) = \sum_{f(v,w)>0}cost(v, w) f(v, w) = \sum_{v, w} cost(v, w) f(v, w) / 2
3. 費用最小
4. 費用最小な最大流を見つける問題
5. その残余グラフRがコストが負である閉路を持たないとき
6. 費用最小の増加パスに沿って
7. フローも費用最小