最大フロー最小カット定理

最大フロー最小カット定理：ネットワークにおける流量の限界

最大フロー最小カット定理は、ネットワークにおける最大流量問題を解くための重要な定理です。この定理は、ネットワークを流れる物質の最大流量が、ネットワーク内のボトルネック、すなわち最も容量の小さい経路（カット）によって決定されることを示しています。

定義

まず、フローネットワークを定義します。フローネットワークは、有向グラフG(V, E)で表現され、各辺(u, v)∈Eには非負の実数の容量c(u, v)が割り当てられています。また、始点（ソース）sと終点（シンク）tが指定されています。このネットワーク上でのフローfは、各辺(u, v)に割り当てられた非負の実数f(u, v)で表され、容量制約(0 ≤ f(u, v) ≤ c(u, v))と、ノードにおける流量保存則を満たします。フローの流量|f|は、ソースsから出ていくフローの合計として定義されます。

次にカットを定義します。カット(S, T)は、ノード集合Vを2つの互いに素な部分集合SとTに分割することで定義されます。ここで、ソースsはSに、シンクtはTに含まれます。カット(S, T)の容量c(S, T)は、SからTに向かう辺の容量の合計です。

定理の主張

最大フロー最小カット定理は、フローネットワークの最大フローの流量|f_max|と、最小カットの容量c(S, T)_minが常に等しいことを主張します。すなわち、

= c(S, T)_min

この等式は、ネットワークの最大流量が、ネットワーク内の最も容量の小さいカットによって制限されることを意味しています。

証明の概要

この定理の証明は、フォード・ファルカーソンアルゴリズムを利用して行うことができます。フォード・ファルカーソンアルゴリズムは、反復的にsからtへの増加道を探索し、フローを増加させることで最大フローを求めるアルゴリズムです。増加道とは、sからtへの経路で、その経路上のすべての辺に流量の余裕がある経路です。

アルゴリズムが終了したとき、sから到達可能なノードの集合をS、到達不可能なノードの集合をTとすると、(S, T)はカットとなります。このカットにおいて、SからTに向かう辺はすべて容量が使い果たされており、TからSに向かう辺の流量は0です。そのため、このカットの容量は最大フローの流量と等しくなります。したがって、最大フローの流量は最小カットの容量以下であることが示されます。

逆に、任意のカット(S, T)について、その容量は常に最大フローの流量以上であることが示せます。これは、フローの流量保存則から導かれます。したがって、最大フローの流量は最小カットの容量以上であることが示されます。

以上のことから、最大フローの流量と最小カットの容量は等しいという結論が導かれます。

例

具体的な例を用いて、最大フロー最小カット定理を理解しましょう。（図は省略）…ここでは、いくつかのノードとエッジからなるネットワークを想定します。各エッジには容量が指定されています。最大フローを求めるアルゴリズムを実行することで、最大フローの流量を計算できます。また、いくつかのカットを検討することで、最小カットの容量を計算できます。最終的に、最大フローの流量と最小カットの容量が等しくなることを確認できます。

歴史

最大フロー最小カット定理は、1956年にElias, Feinstein, Shannonによって独立に証明されました。また、FordとFulkersonも同年に別の証明を与えています。この定理は、線形計画法の双対定理の特別な場合とみなすこともできます。

関連事項

フォード・ファルカーソンのアルゴリズム
線形計画法
双対定理
ネットワークフロー理論

最大フロー最小カット定理は、ネットワークフロー理論における基本的な定理であり、ネットワーク設計や最適化問題など、幅広い分野に応用されています。

もう一度検索