フローネットワークのソースを表示

'''フローネットワーク'''（{{lang-en-short|Flow network}}）は、[[グラフ理論]]における重み付き有向グラフの一種であり、各枝に'''容量'''（capacity）を設定し、各枝を'''フロー'''（flow）が流れる。各枝のフローはその容量を超えることはない。[[オペレーションズ・リサーチ]]では、重み付きグラフを'''ネットワーク'''と呼び、頂点を'''ノード'''、枝を'''アーク'''と呼ぶ。フローが満足すべき制約条件として、1つのノードに流入するフローとそのノードから流出するフローは常に等しい。ただし、始点（source）と終点（sink）では、その限りではない。このネットワークは、例えば道路網の交通量、パイプを流れる液体、電気回路を流れる電流、その他の何らかのネットワーク上を移動するものをモデル化するのに適している。

== 定義 ==
有限な有向グラフ <math>\ G(V,E)</math> の各枝 <math>\ (u,v) \in E</math> に非負実数の容量 <math>\ c(u,v)</math> が設定されているとする。<math>\ (u, v) \not \in E</math> の場合、<math>\ c(u, v) = 0</math> と見なす。ここで、2つの頂点、始点 <math>\ s</math> と終点 <math>\ t</math> を区別する。フローネットワークは[[実数]][[関数 (数学)|関数]] <math>\ f:V \times V \rightarrow \mathbb{R}</math> で表され、全ノード <math>\ u</math> と <math>\ v</math> について、次が成り立つ。

:{|
| '''容量制限''': || <math>\ f(u,v) \le c(u,v)</math> ある枝を流れるフローはその容量を超えることはできない。
|-
| '''歪対称性''': || <math>\ f(u,v) = - f(v,u)</math> <math>\ u</math> から <math>\ v</math> への全フローは、<math>\ v</math> から <math>\ u</math> への全フローのちょうど反対でなければならない（例を参照）。
|-
| '''フロー保存則''': || <math>\ \sum_{w \in V} f(u,w) = 0</math> ただし <math>\ u=s</math> または <math>\ u=t</math> でない場合。始点と終点以外のノードでは、流入するフローと流出するフローの合計はゼロである。始点はフローを生成し、終点はフローを消費する。
|}

ここで、<math>\ f(u,v)</math> は <math>\ u</math> から <math>\ v</math> へのフローの総和を意味する。グラフが物理的ネットワークを表していて、<math>\ u</math> から <math>\ v</math> へ4単位のフローがあり、<math>\ v</math> から <math>\ u</math> へ3単位のフローがある場合、<math>\ f(u,v)=1</math> および <math>\ f(v,u)=-1</math> となる。

枝の'''残余容量'''（residual capacity）とは、<math>\ c_f(u,v) = c(u,v) - f(u,v)</math> で表される量である。ここから'''残余ネットワーク'''（residual network）<math>\ G_f(V,E_f)</math> が定義され、利用可能な容量で構成されたネットワークを意味する。本来のネットワークには <math>\ u</math> から <math>\ v</math> への枝がない場合でも、残余ネットワークでは <math>\ u</math> から <math>\ v</math> への枝がある場合もある。反対向きのフローは相殺されるため、<math>\ v</math> から <math>\ u</math> へのフローが減少するということは、<math>\ u</math> から <math>\ v</math> へのフローが増加することを意味する。'''増加道'''（augmenting path）とは、残余ネットワーク内の経路 <math>\ (u_1,u_2,\dots,u_k)</math> であって、<math>\ u_1=s</math> かつ <math>\ u_k=t</math> であり、<math>\ c_f(u_i, u_{i+1}) > 0</math> であるような経路を意味する。最大フローのネットワークとは、残余ネットワークに増加道が存在しない場合を指す。

== 例 ==
[[画像:network_flow.png|thumb|right|100px|フローと容量を示したフローネットワーク。]]
右図は、始点 <math>s</math>、終点 <math>t</math>、他の4つのノードから構成されるフローネットワークである。フローと容量は <math>f/c</math> のように示されている。この図において、確かに容量制限、歪対称性、フロー保存則が成り立っている。また、始点 <math>s</math> から終点 <math>t</math> への総フロー量が 5 であることは、<math>s</math> から流出しているフロー量や <math>t</math> に流入しているフロー量が 5 であり、また他のノードにおいてはフローの増減が無いことから確認できる。

[[画像:network_flow_residual.png|right|frame|上記フローネットワークの残余ネットワーク。残余容量を示している。]]
次の図では、上図の残余ネットワークを示している。例えば枝 <math>(d, c)</math> のように、元の容量が 0 だった枝であっても残余容量が正であるものが存在する。なお、この残余ネットワークには増加道 <math>(s, a, c, t)</math>、<math>(s, a, b, d, t)</math>、<math>(s, a, b, d, c, t)</math> が存在することから、上図のネットワークは[[最大フロー問題|最大フロー]]ではないことがわかる。例えば増加道 <math>(s, a, c, t)</math> の残余容量は <math>\min\{ c(s, a) - f(s, a), c(a, c) - f(a, c), c(c, t) - f(c, t) \} = \min\{ 5 - 3, 3 - 2, 2 - 1 \} = \min\{ 2, 1, 1 \} = 1</math> と計算できる。ここで、増加道 <math>(s, a, b, d, c, t)</math> は元のネットワークには存在しない経路であるが、この経路に沿ってフローを送り込むことは可能である。

== 応用 ==
水道管の配管をネットワークとして考える。各水道管には直径があり、特定の量の水流しか流せない。管と管の接続部に流入する水量は、そこから流出する水量と等しい。水道網には水源（始点）と排水溝（終点）がある。途中がどうであれ、始点から終点に水は流れるだけであり、水源からの流出量が一定なら水の消費量は一定である。直観的には、ネットワークの全フローは水源からの流出量と等しい。

交通網や[[送電]]網などもフローネットワークで表すことができる。このような物理ネットワークでは、中間ノードに流入するフローとそこから流出するフローは常に等しい。Béla Bollobás は、このような性質を[[キルヒホッフの法則 (電気回路)|キルヒホッフの法則]]を使って定式化し、後には（Chartrandなどが）保存方程式として一般化した。

フローネットワークは[[生態学]]でも利用されている。すなわち、[[食物連鎖]]における異なる生体間の栄養とエネルギーのフローをフローネットワークとしてモデル化する。そのようなネットワークに関する数学の問題は、流体や交通網のそれとは全く異なる。生態系をネットワークとしてモデル化することは、Robert Ulanowicz らが行ったもので、[[情報理論]]や[[熱力学]]のネットワークに関する成果を取り入れている。

== 一般化と特殊化 ==
フローネットワークについての最も単純で一般的な問題として[[最大流問題]]、すなわち与えられたグラフについて始点から終点への可能な最大フローを求める問題がある。最大フローを求めるアルゴリズムを使って、フローネットワークにモデル化可能な他の問題も解くことができる。例えば[[マッチング (グラフ理論)|2部マッチング]]、[[割当問題]]、[[交通学|交通問題]]などがある。

[[多品種流問題]]では、始点と終点がそれぞれ複数あり、それぞれ固有の品種がフローとして流通する。これは、例えば各種工場から様々な製品が生産され、様々な顧客に「同じ交通網」を通して届けられるのに似ている。

[[最小費用流問題]]では、各枝 <math>u,v</math> には所定のコスト <math>k(u,v)</math> が設定されており、フロー <math>f(u,v)</math> を送るのにかかるコストは <math>f(u,v) \cdot k(u,v)</math> で表される。目的は、所定のフローを始点から終点へ最小費用で送ることである。

[[循環流問題]]では、枝に対して下限 <math>l(u,v)</math> と上限 <math>c(u,v)</math> が与えられる。各枝にはコストも設定されている。終点から始点への枝が追加され、全ノードでフロー保存則が成り立つようになっていることが多い。この場合、上限と下限の間で可能なフローの総計を求める。その名の通り、この問題ではフローはネットワーク上を循環する。

利得のあるネットワークでは、各枝には利得が設定されており、フロー x が利得 g の枝を通ると、最終的にフローが gx となる。

== 参考文献 ==
* {{cite book | author=Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin | title= Network Flows: Theory, Algorithms and Applications | publisher=Prentice Hall | year=1993 | id=ISBN 0-13-617549-X|mr=1205775|zbl=1201.90001 }}
* {{cite book | author=Bollobás, Béla | title= Graph Theory: An Introductory Course | location=Heidelberg | publisher=Springer-Verlag | year=1979 | id=ISBN 3-540-90399-2}}
* {{cite book | author=Chartrand, Gary & Oellermann, Ortrud R. | title=Applied and Algorithmic Graph Theory | location=New York | publisher=McGraw-Hill | year=1993 | id=ISBN 0-07-557101-3}}
* {{cite book | author=Even, Shimon | title=Graph Algorithms | location=Rockville, Maryland | publisher=Computer Science Press | year=1979 | id=ISBN 0-914894-21-8}}
* {{cite book | author=Gibbons, Alan | title=Algorithmic Graph Theory | location=Cambridge | publisher=Cambridge University Press | year=1985 | id=ISBN 0-521-28881-9  ISBN 0-521-24659-8 }}
* {{cite book | author = Thomas H. Cormen, Charles E. Leiserson, [[ロナルド・リベスト|Ronald L. Rivest]], and Clifford Stein | title = Introduction to Algorithms | origyear = 1990 | edition = 2nd edition | year = 2001 | publisher = MIT Press and McGraw-Hill | pages = 696-697 | chapter = 26 | id = ISBN 0-262-03293-7}}

== 関連項目 ==
* [[最大フロー最小カット定理]]
* [[フォード・ファルカーソンのアルゴリズム]]

== 外部リンク ==
* [http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/maxflow/Maxflow.shtml Maximum Flow Problem]
* [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow Maximum Flow]
* [http://www.dis.uniroma1.it/~challenge9/download.shtml Real graph instances]
* [http://www.avglab.com/andrew/soft.html Software and papers for network flow problems]

{{最適化アルゴリズム}}

{{DEFAULTSORT:ふろおねつとわあく}}
[[Category:グラフ理論]]
[[Category:オペレーションズリサーチ]]
[[Category:数学に関する記事]]
[[Category:ネットワーク]]