拡張パスとは何ですか？
1. 序章
パスを拡張するというアイデアは、コンピュータサイエンスの2つの異なるコンテキストで浮かび上がります。 これらはマッチング理論と最大フロー問題です。
このチュートリアルでは、拡張パスとは何かについて説明します。 まず、グラフのマッチングのコンテキストでそれらを確認します。 次に、最大フロー問題に関連してそれらを研究します。 また、拡張パスを利用するいくつかのアルゴリズムについても簡単に説明します。
2. マッチング理論におけるパスの拡張
2.1. 定義
マッチングに関して拡張パスとは何かについて話す前に、いくつかの定義が必要です。 マッチングは、グラフのエッジのサブセットであり、2つのエッジが共通の頂点を共有することはありません。
のすべての一致の中で最大のサイズがある場合、最大一致と呼びます。 ifがその頂点に接触する場合に一致する頂点を呼び出します。 それ以外の場合、頂点は一致しません。
下の左側は、 2部グラフでのマッチングの例です（赤い色のエッジはマッチングを表します）。
一致しない頂点から始まり、とからのエッジを交互に含むパスは、。に関する交互のパスです。 一致しない頂点で終わる交互パスを拡張パスと呼びます。
上記のマッチングの場合、パスは交互パスと拡張パスの両方の例です。 このパスは、右側で緑色で強調表示されています。
2.2. 最大一致を見つけるために拡張パスはどのように使用されますか？
のエッジとの対称差を取ることにより、拡張パスを使用して、マッチングをより大きなマッチングに変えることができます。 つまり、との両方にあるエッジを削除します。 他のすべてのエッジを追加/保持します。 これを例で最もよく説明できます。
使用した拡張パスを以下に示します。
ここでは、拡張パス（緑色で表示）を使用して最初の一致を拡張し、より大きな一致を取得しました。 エッジとが削除され、エッジ、、、がに追加されました。 また、エッジを維持しました。
マッチングから始めて、パスを拡張することで繰り返し拡張すると、最終的には常に最適なサイズのマッチング、つまり最大のマッチングが得られることを証明できます。
これは、最大の一致を見つけるためのアルゴリズムの背後にある重要な直感です。
2.3. 最大一致を見つけるために拡張パスを使用するアルゴリズム
拡張パスを使用する有名なアルゴリズムの2つの例は、ハンガリーアルゴリズムとブロッサムアルゴリズムです。 前者を使用して2部グラフで最大の一致を検索し、後者を使用して一般的なグラフで最大の一致を検索できます。 拡張パスを見つけるために、アルゴリズムは通常、深さ優先検索や幅優先検索などのツリー検索を使用しますが、いくつかの小さな変更/追加があります。
3. 最大フロー問題におけるパスの拡張
3.1. いくつかの初期定義
最初にいくつかの重要な定義を見てみましょう。 次に、最大フロー問題の拡張パスが何であるかを確認します。
フローネットワークは、各エッジが非負の容量を持つ有向グラフです。 セルフループを許可せず、エッジが存在しない場合。 最後に、ネットワークにエッジが存在する場合、リバースエッジは存在しません。
合計値が19のフローを含むフローネットワークの例を次に示します。
エッジラベルは、エッジにの容量とフローがあるという事実を伝えるための形式を取ります。
フローネットワークには2つの特別な頂点があります。 ソースとシンク。 ソースは何らかのマテリアルを生成する頂点と考えることができ、シンクはマテリアルを消費する頂点です。
フローネットワーク内のフローは、値が容量の制約を超えないように、ネットワークのエッジに非負の実数を割り当てることとして定義され、フロー保存の原則が適用されます。 フローの保存では、ソースとシンクを除くすべてのノードで、入力フローの合計が出力フローの合計と等しくなければなりません。
で示されるフローの合計値は、ソースを出る合計フローからソースに入る合計フローを引いたものとして定義されます。 最大フロー問題では、フローネットワークが与えられており、最大値のフローを見つけたいと考えています。
3.2. 残留ネットワーク
フローネットワークが与えられた場合、対応する残余ネットワークは、のさまざまなエッジでフローを変更する方法を表します。 フローがそのエッジの容量より少ないエッジインの場合、元のエッジの容量からそのエッジのフローを差し引いた残りの容量を持つ対応するエッジがあります。
元のグラフのエッジが飽和している場合（そのフローがその容量に等しい場合）、対応するエッジは、フローを許可できなくなるため、残りのグラフから省略されます。
以下は、上記のフローネットワークの残差グラフの例です。
この残りのネットワークを見ると、上記の概念が実際に機能していることがわかります。
たとえば、容量が16から11ユニットの流量のエッジがあることがわかります。 したがって、には2つの対応するエッジがあります。 1つのエッジは、からへの前方エッジであり、残りの容量は5です。 もう1つは、からのバックエッジで、残りの容量は11です。
フォワードエッジは、からにさらに5単位のフローを送信できるという事実を表しています。 バックエッジは、11単位のフローをからに送り返すことができることを通知します（これは、からへのフローを減らすことと同じです）。
3.3. パスの拡張
残差ネットワークとは何かを定義したので、パスの拡張について説明します。 フローネットワークの場合、拡張パスは、対応する残余ネットワークのソースからシンクへの単純なパスです。直感的に、拡張パスは、特定のエッジのフローを変更して、ソースからシンクへの全体的なフローを増やします。
たとえば、前の残差グラフの拡張パス（赤で網掛け）は次のとおりです。
このネットワークをフローネットワークとして扱う場合、このパスに沿って4ユニットのフローをからに送信することを考えることができます。 このパスに沿ってフローを送信することは、の特定のエッジでフローを増減することに対応します。 この場合、拡張パスに沿って最大4単位のフローを送信できるため、では、エッジでフローを4単位増やし、エッジでフローを4単位減らします。
これは、パスの拡張に関連する重要なポイントをもたらします。 拡張パスは全体のフローを増加させますが、エッジのフローを増加させるだけではありません。 拡張パスはフローを拡張するため、エッジフローを増加させるだけであると考えるのは簡単です。 しかし、これは必ずしも真実ではありません。
フローネットワーク内の任意のフローとの拡張パスが与えられた場合、このパスで拡張すると、より高い値の新しいフローインが得られることを証明できます。
3.4. 最大フローを見つけるために拡張パスを使用するアルゴリズム
おそらく、最大フローを見つけるために拡張パスを使用する最もよく知られているアルゴリズムは、Ford-Fulkersonアルゴリズムです。 Ford-Fulkerson法の背後にある直感は単純です。ネットワーク内の現在のフローに関して拡張パスが存在する一方で、拡張パスを使用してそのフローを拡張し、新しいフローを取得します。 この戦略は、 max-flow min-cut theorem と呼ばれる有名な定理により、最大フローが見つかることを保証します。これは、拡張パスがない場合にのみフローが最大値になることを示しています。その残差グラフで。
Ford-Fulkerson法で拡張パスを見つける方法に基づいて、より良い実行時間を得ることができます。 たとえば、各反復の拡張パスとして、使用可能な容量を持つ最短パスを選択できます。 次に、Ford-Fulkersonのより高速な実装を取得します。 これは、 Edmonds-KarpAlgorithmと呼ばれます。
最大フローを計算するための別のアルゴリズムは、 Dinic’sAlgorithmと呼ばれます。 各反復で1つの拡張パスを見つけるのではなく、レベルグラフとブロッキングフローという2つの重要なアイデアを利用します。 ブロッキングフローを見つけることにより、Dinicのアルゴリズムは特定の長さのすべての拡張パスを計算します。 次に、このブロッキングフローを使用して、フローを拡張します。
4. 結論
この記事では、最大マッチングと最大フローのコンテキストで拡張パスが何であるかを調べました。 また、拡張パスを利用するいくつかのアルゴリズムについても簡単に説明しました。
