1. 概要

このチュートリアルでは、グラフの最大フローを計算して、グラフの最小カットを見つける方法について説明します。最大フロー最小カット定理について説明し、最大フローを見つけるためのアルゴリズムを示します。グラフの流れ。

最後に、例を使用してアルゴリズムを示し、アルゴリズムの時間計算量を分析します。

2. グラフの最小カット

一般に、カットは、連結グラフを2つの互いに素なサブセットに分割するエッジのセットです。カットには、最大カットと最小カットの2つのバリエーションがあります。 最大フロー最小カット定理について説明する前に、最小カットとは何かを理解することが重要です。

頂点セットを2つのセットとに分割するカットを想定します。 カットの正味フローは、フローの合計として定義できます。ここで、は2つのノード、およびです。 同様に、カットの容量は、個々の容量の合計です。ここで、は2つのノード、およびです。

重み付きグラフの最小カットは、グラフから削除されたときにグラフを2つのセットに分割するエッジの重みの最小合計として定義されます。

例を見てみましょう：

このグラフでは、最小カットの例を示しています。 エッジとを削除し、これら2つのエッジの重みの合計は、このグラフの他のすべてのカットの中で最小になります。

3. グラフの最大フロー

正式には、グラフが与えられると、フローインはすべての頂点でキルヒホッフの法則が検証される方法でのベクトルです（ノードでのフローの保存則）。 キルヒホッフの法則によれば、ノード（または頂点）に入るフローの合計は、ノードから出るフローの合計と等しくなければなりません。

このグラフを考えてみましょう：

ここで、すべてのエッジはフロー値を表すため、このグラフのフローのセットまたはベクトルはです。

これらのフロー値は、キルヒホッフの法則を満たしています。 の場合、フローの合計は出力エッジの場合と同じです。 同様に、フローの合計は、の入力エッジに対して等しく、これも以前に計算された合計に等しくなります。 これは、他の頂点についてチェックできます。

ネットワークまたはグラフのフローは、いくつかのプロパティに従います。 フローグラフには、ソースとシンクの2つの特別な頂点があります。 フローネットワークの各エッジには容量があります。 グラフ内のフローは関数であり、各エッジの容量制約を満たします。  エッジの正味の流れは、スキュー対称プロパティに従います。

最大フローは、グラフまたはネットワークがソースノードからそのシンクノードに流れることを許可するフローの最大量として定義されます。

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

最大フロー最小カット定理は、特定のソースから特定のシンクへの任意のネットワークを通る最大フローが、カットの最小合計に正確に等しいことを示しています。この定理は、Ford-を使用して検証できます。フルカーソンアルゴリズム。 このアルゴリズムは、ネットワークまたはグラフの最大フローを見つけます。

最大フロー最小カット定理を正式に定義しましょう。 フローネットワーク、上のフローとします。 ソースからシンクへの最大フローの値は、最小カット分離の容量に等しく、次のようになります。

   

5. フォード・ファルカーソンアルゴリズム

5.1. 残留ネットワークと拡張パス

Ford-Fulkersonアルゴリズムは、残差ネットワーク拡張パスとカットという3つの重要な概念に基づいています。グラフでカットについてはすでに説明しました。

残余ネットワークは、として定義できます。ここで、。 残存容量はとして定義されます。

拡張パスは、残りのネットワークのソースノードからシンクノードへの単純なパスです。

また、このアルゴリズムでは Netflowグラフを使用して、グラフの各エッジのフローと容量を示します。

5.2. 一般的なアイデア

アルゴリズムはグラフ内の実行可能なフローから始まり、フローは繰り返し改善されます。

この流量が最大の場合、この値を満たす流量関数と最小カットを決定することができます。 フローが最大でない場合、その目的は、このフローに対応する改善パスを強調表示することです。

最初に、アルゴリズムはソースノードとシンクノード間のフロー値をに設定することから始まります。 各反復で、拡張パスを見つけてフロー値を増やします。アルゴリズムを終了し、拡張パスが見つからなくなったらフロー値を返します。

5.3. 擬似コード

Ford-Fulkersonアルゴリズムの擬似コードを見てみましょう。

6. 例

最初に、有向連結グラフを取得し、その上でFord-Fulkersonアルゴリズムを実行します。 各ステップで、拡張パスを選択し、残差グラフとNetflowグラフを表示します。

まず、パスを選択します。 このパスでは、最小容量はです。 次に、残差グラフとNetflowグラフを作成します。

アルゴリズムを続行し、次の拡張パスを選択します。

次の選択は：

それでも、より多くの拡張パスを選択できます。 パスを選択します：

次に、残差グラフを観察して、さらに拡張されたパスを見つけることができるかどうかを見てみましょう。

ソースノードからの現在の残差グラフを見ると、パスを介してシンクノードに到達することはできません。 したがって、これ以上拡張パスが見つからないため、アルゴリズムを終了します。 ここで、アルゴリズムによれば、シンクノードからの最大発信フローは、ソースノードの最大着信フローと等しくなるはずです。 これを確認しましょう。

ノードからの最大発信フローはであり、ソースノード の最大着信フローはであるため、 Ford-Fulkersonアルゴリズムは正常に機能し、グラフの最大フローを正しく提供します。

ここで、最大フロー最小カット定理によれば、このグラフの最小カットは、グラフの最大フローに等しくなります。 したがって、このサンプルグラフの最小カットはです。

7. 時間計算量分析

Ford-Fulkersonアルゴリズムは、拡張パスを見つけるために使用される方法に大きく依存します。 拡張パスは、幅優先探索（BFS）または深さ優先探索（DFS）を使用して見つけることができます。 BFSまたはDFSを使用して拡張パスを選択した場合、アルゴリズムは多項式時間で実行されます。

BFSの実行時間は、に等しくなります。ここで、は残差グラフのエッジの数です。 エッジごとにフローが増加し、最悪の場合、最大フロー値に達します。 したがって、アルゴリズムはほとんどの場合繰り返されます。 したがって、Ford-Fulkersonアルゴリズムの全体的な時間計算量はになります。

8. 結論

このチュートリアルでは、グラフの最大フロー値を計算して最小カットを見つける方法について説明しました。 グラフの最大フロー問題を解決するために、フォード・ファルカーソンアルゴリズムを提示しました。

グラフの最小カットを見つけるために、最大フロー最小カット定理について説明します。 最後に、例を使用してFord-Fulkersonアルゴリズムを検証し、時間計算量を分析しました。