グラフの最小カット(the Minimum Cut)を求める

ECLiPSe CLPでグラフの最小カットを求める方法を説明します。

グラフのカットというのは、最大流問題で用いた、エッジに許容流量の設定のあるスタートとゴールのノードを持つ有向グラフのすべてのノードを、「スタート側」「ゴール側」の2種類のノードに分けることをいいます。

ノードをどのように分けてもよいので、カットの仕方には複数通りの方法があります。
グラフに|V|個のノードがあったとして、スタートとゴールのノードのみどちら側か決まっているので 2^(|V|-2)通り のカットの方法があります。

最小カットというのは、複数あるカットのうち、「カット容量が最小となるもの(そしてその容量)」のことを言います。
カット容量とは、ノードとノードを結ぶすべてのエッジのうち「スタート側に属するノード」から「ゴール側に属するノード」の方向のエッジの許容流量の総計のことを言います(スタート側→スタート側、ゴール側→ゴール側、ゴール側→スタート側 のエッジの容量は数えない)

最小カット容量は、スタート→ゴールの流れのボトルネックのようなもので、この値がそのまま最大流と等しくなるとのことです。
(最小カット容量=最大フロー)

前置き長くなりましたが上記最小カットを求めます。
library(all_min_cuts) の述語 all_min_cuts/8 を使います。

all_min_cuts(+Graph, +CapacityArg, +SourceNode, +SinkNode, -MaxFlowValue, -MaxFlowEdges, -MinCuts, -MinCutEdges)

Grapha – グラフ
CapacityArg – エッジ e(_,_,A) のAのどこが最大流量か設定する
SourceNode – スタートのノード番号
SinkNode – ゴールのノード番号
MaxFlowValue – 最大フロー(=最小カット容量)(戻り値)
MaxFlowEdges – 「フロー - エッジ」のリスト(戻り値)
MinCuts – 最小カット容量をもつカットのリスト(複数あれば複数)(戻り値)
MinCutEdges – すべての最小カット組(それぞれのカット組はスタート側-ゴール側を分けるエッジのリスト)(戻り値)

①以下の図でノード1がスタート、ノード7がゴールとして最小カットを求めます。
OR_Excercise_1_3_max

プログラム:

実行結果(見やすいように手で改行入れてます):

最小カットは9で
ノード 4-7、6-7、5-7 のエッジがスタート側とゴール側を分けるエッジのようです。

②以下のグラフで最小カットを求めます。
OR_excersise_1_4

プログラム(便宜的にスタートノードとゴールノードをそれぞれノード5、ノード6に置き換え):

実行結果:

最大フロー(最小カット)10、
ノード1-4、1-3、2-3 を結ぶエッジがスタート側とゴール側を結ぶ

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

次のHTML タグと属性が使えます: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">