ネットワークフロー問題
【英】：network flow problem
概要
ネットワーク上のフローを扱う最適化問題の総称. 最大フロー問題, 最小費用フロー問題, 輸送問題, 多品種フロー問題, 利得/損失付きフロー問題(一般化フロー問題)などがある. 最短路問題, 割当問題, 最小カット問題もネットワークフロー問題として扱うこともある.
詳説
ネットワーク上のモノの流れを扱う．モノは与えられた有向グラフ
の各枝に沿って流れ，点で分岐や合流をする．ただし，各枝
の容量
を超えず，各点
から出る正味の流量が，与えられた供給量
と等しくなるようにする．枝aを流れる量を
としたとき，
を満たす
をフローといい，フローを扱った最適化問題をネットワークフロー問題という [1] ．ただし，
は点から出る (へ入る) 枝の全体を表す．
代表的なネットワークフロー問題に最大フロー問題がある．最大フロー問題とは，特別な点として入口
と出口
があり，
以外での供給量が0であるとき，から入る量 (フロー値) を最大にするようなフロー (最大フロー) を求める問題であり，以下のように定式化できる．
点の部分集合
がを含み，を含まないとき，を
カットという．始点がにあり終点がにない枝の容量の和をの容量といい，容量最小のカットを最小カットという．任意のフローのフロー値は任意のカットの容量よりも大きくなり得ない．この値が一致するようなフローとカットが存在することを示したのが，最大フロー最小カット定理 [2] である．実際，あるカットの容量に一致するフロー値をもつフローが以下の操作で得られる．
まず，任意のフローに対し，補助ネットワーク
を定義する．
は，与えられたグラフと同じ点集合
をもち，枝集合が
のグラフとする．ただし，
は，枝の向きを逆にした枝である．
は，
の枝に定義される残余容量であり，
で与えられる．補助ネットワーク上のからへの有向道を増加道という．増加道に沿ってフローの更新を繰り返し，フロー値を増加させる方法を増加道法という．任意のフローから始め，以下の手順を繰り返す．
手順1: 
を作成し，増加道
をみつける．増加道がなければ終了．
手順2: 
は上の枝
を求め，上のすべての枝に関して，
ならば，を
増加し，
ならば，を減少させる．
増加道が存在しなくなったとき，上でから到達可能な点集合をとすると，はカットであり，その容量はフロー値と一致する．よって，増加道法が終了したときのフローが最大フローであり，が最小カットである．
増加道の選択を，枝数最小や，最大の基準で行うと，多項式時間の最大フローアルゴリズムとなる．一方，流量保存則を緩和したプリフローを用い，増加道が存在しないようなプリフローを維持しながら，最大フローを求めるプッシュ・再ラベル法も効率よい最大フローアルゴリズムである．
最小費用フロー問題もネットワーク・フロー問題の一つである．各枝のフロー1単位あたりの費用
が与えられているとき，総費用
を最小にするフローを求める問題である．特に，すべての点で供給量
のとき，循環フローという．また，輸送問題も最小費用フロー問題の特殊ケースである．複数の供給地と需要地があり，各々の供給/需要量と，各供給地と需要地間の輸送費用がわかっているとき，供給/需要を満たし，輸送にかかる総費用を最小とする輸送方法とその輸送量を決定する輸送問題は，容量制約のない2部グラフ上の最小費用フロー問題である．
最小費用フローアルゴリズムも多数ある．補助ネットワーク上の費用を
で定義すると，フローが最小費用である必要十分条件は，その補助ネットワーク上に負の費用の閉路が存在しないことである．補助ネットワーク上の負の費用の閉路を繰り返し除去することによって最適フローを求めるのが負閉路消去法である．この他にも，点に対応する双対変数を与え，相補スラック条件を満たす枝からなるネットワーク上で最大フロー問題を繰り返し解く方法，最短路問題を繰り返し解く方法，単体法を用いたネットワーク単体法などがある．いずれの方法も強多項式時間アルゴリズムが存在する．
最大フロー問題，最小費用フロー問題ともに，容量，供給量が整数で与えられているときには，整数値の最適フローが存在することが知られている．また，ネットワークの構造を用いた効率よいアルゴリズムがいくつか存在する．一方，１つのネットワーク上に複数品種を流す多品種フロー問題は，品種ごとに流量保存則が満たされており，かつすべての品種をあわせて容量制約が満たされている多品種フローを扱う．多くのアルゴリズムは線形計画法の手法に基づいている．整数値の多品種フローを求める問題はNP完全である．
[1] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993.
[2] L. R. Ford, Jr. and D. R. Fulkerson, Flows in Networks, Princeton University Press, 1962.
[3] B. Korte and J. Vygen, Combinatorial Optimization, 4th ed., Springer, 2007. 浅野孝夫 他 訳, 『組合せ最適化』, シュプリンガー・フェアラーク東京，2005．
[4] アルゴリズムデータベース http://www-or.amp.i.kyoto-u.ac.jp/algo-eng/db/
| グラフ･ネットワーク： | デルタマトロイド ナップサック問題 ネットワーク ネットワークフロー問題 フェンシェル型双対定理 プリム法 ベルマン・フォード法 |
| 組合せ最適化： | グレブナー基底 データ構造 ナップサック問題 ネットワークフロー問題 ハッシュ表 パーフェクトグラフ パーフェクトグラフ予想 |
「network flow problem」の例文・使い方・用例・文例
- network flow problemのページへのリンク
