フローネットワーク（）は、グラフ理論における重み付き有向グラフの一種であり、各枝に容量（capacity）を設定し、各枝をフロー（flow）が流れる。各枝のフローはその容量を超えることはない。オペレーションズ・リサーチでは、重み付きグラフをネットワークと呼び、頂点をノード、枝をアークと呼ぶ。フローが満足すべき制約条件として、1つのノードに流入するフローとそのノードから流出するフローは常に等しい。ただし、始点（source）と終点（sink）では、その限りではない。このネットワークは、例えば道路網の交通量、パイプを流れる液体、電気回路を流れる電流、その他の何らかのネットワーク上を移動するものをモデル化するのに適している。有限な有向グラフ formula_1 の各枝 formula_2 に非負実数の容量 formula_3 が設定されているとする。formula_4 の場合、formula_5 と見なす。ここで、2つの頂点、始点 formula_6 と終点 formula_7 を区別する。フローネットワークは実数関数 formula_8 で表され、全ノード formula_9 と formula_10 について、次が成り立つ。ここで、formula_11 は formula_9 から formula_10 へのフローの総和を意味する。グラフが物理的ネットワークを表していて、formula_9 から formula_10 へ4単位のフローがあり、formula_10 から formula_9 へ3単位のフローがある場合、formula_18 および formula_19 となる。枝の残余容量（residual capacity）とは、formula_20 で表される量である。ここから残余ネットワーク（residual network）formula_21 が定義され、利用可能な容量で構成されたネットワークを意味する。本来のネットワークには formula_9 から formula_10 への枝がない場合でも、残余ネットワークでは formula_9 から formula_10 への枝がある場合もある。反対向きのフローは相殺されるため、formula_10 から formula_9 へのフローが減少するということは、formula_9 から formula_10 へのフローが増加することを意味する。増加道（augmenting path）とは、残余ネットワーク内の経路 formula_30 であって、formula_31 かつ formula_32 であり、formula_33 であるような経路を意味する。最大フローのネットワークとは、残余ネットワークに増加道が存在しない場合を指す。右図は、始点 formula_34、終点 formula_35、他の4つのノードから構成されるフローネットワークである。フローと容量は formula_36 のように示されている。この図において、確かに容量制限、歪対称性、フロー保存則が成り立っている。また、始点 formula_34 から終点 formula_35 への総フロー量が 5 であることは、formula_34 から流出しているフロー量や formula_35 に流入しているフロー量が 5 であり、また他のノードにおいてはフローの増減が無いことから確認できる。次の図では、上図の残余ネットワークを示している。例えば枝 formula_41 のように、元の容量が 0 だった枝であっても残余容量が正であるものが存在する。なお、この残余ネットワークには増加道 formula_42、formula_43、formula_44 が存在することから、上図のネットワークは最大フローではないことがわかる。例えば増加道 formula_42 の残余容量は formula_46 と計算できる。ここで、増加道 formula_44 は元のネットワークには存在しない経路であるが、この経路に沿ってフローを送り込むことは可能である。水道管の配管をネットワークとして考える。各水道管には直径があり、特定の量の水流しか流せない。管と管の接続部に流入する水量は、そこから流出する水量と等しい。水道網には水源（始点）と排水溝（終点）がある。途中がどうであれ、始点から終点に水は流れるだけであり、水源からの流出量が一定なら水の消費量は一定である。直観的には、ネットワークの全フローは水源からの流出量と等しい。交通網や送電網などもフローネットワークで表すことができる。このような物理ネットワークでは、中間ノードに流入するフローとそこから流出するフローは常に等しい。Béla Bollobás は、このような性質をキルヒホッフの法則を使って定式化し、後には（Chartrandなどが）保存方程式として一般化した。フローネットワークは生態学でも利用されている。すなわち、食物連鎖における異なる生体間の栄養とエネルギーのフローをフローネットワークとしてモデル化する。そのようなネットワークに関する数学の問題は、流体や交通網のそれとは全く異なる。生態系をネットワークとしてモデル化することは、Robert Ulanowicz らが行ったもので、情報理論や熱力学のネットワークに関する成果を取り入れている。フローネットワークについての最も単純で一般的な問題として最大フロー問題、すなわち与えられたグラフについて始点から終点への可能な最大フローを求める問題がある。最大フローを求めるアルゴリズムを使って、フローネットワークにモデル化可能な他の問題も解くことができる。例えば2部マッチング、割り当て問題、交通問題などがある。多品種フロー問題では、始点と終点がそれぞれ複数あり、それぞれ固有の品種がフローとして流通する。これは、例えば各種工場から様々な製品が生産され、様々な顧客に「同じ交通網」を通して届けられるのに似ている。最小コストフロー問題では、各枝 formula_48 には所定のコスト formula_49 が設定されており、フロー formula_50 を送るのにかかるコストは formula_51 で表される。目的は、所定のフローを始点から終点へ最小コストで送ることである。循環フロー問題では、枝に対して下限 formula_52 と上限 formula_53 が与えられる。各枝にはコストも設定されている。終点から始点への枝が追加され、全ノードでフロー保存則が成り立つようになっていることが多い。この場合、上限と下限の間で可能なフローの総計を求める。その名の通り、この問題ではフローはネットワーク上を循環する。利得のあるネットワークでは、各枝には利得が設定されており、フロー x が利得 g の枝を通ると、最終的にフローが gx となる。

出典:wikipedia