Main Content

maxflow

グラフの最大フロー

説明

mf = maxflow(G,s,t) は、ノード st の間の最大フローを返します。グラフ G が重みなしの場合 (つまり G.Edges が変数 Weight を含まない)、maxflow はすべてのグラフ エッジが重み 1 をもつものとして扱います。

mf = maxflow(G,s,t,algorithm) は、使用する最大フロー アルゴリズムを指定します。この構文は、G が有向グラフの場合にのみ使用できます。

[mf,GF] = maxflow(___) は、前述の構文に示した任意の入力引数を使用して、有向グラフ オブジェクト GF も返します。GF は、非ゼロのフロー値をもつ G のエッジのみを使用して構成されます。

[mf,GF,cs,ct] = maxflow(___) はさらに、ソースとターゲットのノード ID cs および ct を返します。これらは最大フローに対応する最小カットを表します。

すべて折りたたむ

重み付きグラフを作成し、プロットします。重み付きエッジはフロー容量を表します。

s = [1 1 2 2 3 4 4 4 5 5];
t = [2 3 3 4 5 3 5 6 4 6];
weights = [0.77 0.44 0.67 0.75 0.89 0.90 2 0.76 1 1];
G = digraph(s,t,weights);
plot(G,'EdgeLabel',G.Edges.Weight,'Layout','layered');

Figure contains an axes object. The axes object contains an object of type graphplot.

ノード 1 からノード 6 までの最大フローを求めます。

mf = maxflow(G,1,6)
mf = 1.2100

グラフを作成してプロットします。重み付きエッジはフロー容量を表します。

s = [1 1 2 2 3 3 4];
t = [2 3 3 4 4 5 5];
weights = [10 6 15 5 10 3 8];
G = digraph(s,t,weights);
H = plot(G,'EdgeLabel',G.Edges.Weight);

Figure contains an axes object. The axes object contains an object of type graphplot.

ノード 1 とノード 5 の間の最大フロー値を求めます。'augmentpath' を指定してフォード・ファルカーソン アルゴリズムを使用し、2 つの出力を使用して非ゼロ フローのグラフを返します。

[mf,GF] = maxflow(G,1,5,'augmentpath')
mf = 11
GF = 
  digraph with properties:

    Edges: [6x2 table]
    Nodes: [5x0 table]

非ゼロ フローのグラフを強調表示し、ラベルを付けます。

H.EdgeLabel = {};
highlight(H,GF,'EdgeColor','r','LineWidth',2);
st = GF.Edges.EndNodes;
labeledge(H,st(:,1),st(:,2),GF.Edges.Weight);

Figure contains an axes object. The axes object contains an object of type graphplot.

重み付きグラフを作成し、プロットします。エッジの重みはフロー容量を表します。

s = [1 1 2 3 3 4 4 5 5];
t = [2 3 3 2 5 5 6 4 6];
weights = [0.77 0.44 0.67 0.69 0.73 2 0.78 1 1];
G = digraph(s,t,weights);
plot(G,'EdgeLabel',G.Edges.Weight,'Layout','layered')

Figure contains an axes object. The axes object contains an object of type graphplot.

グラフの最大フローおよび最小カットを求めます。

[mf,~,cs,ct] = maxflow(G,1,6)
mf = 0.7300
cs = 3×1

     1
     2
     3

ct = 3×1

     4
     5
     6

cs ノードをソース、ct ノードをシンクとして使用して、最小カットをプロットします。cs ノードを赤、ct ノードを緑で強調表示します。これら 2 セットのノードを連結するエッジの重みが最大フローに等しくなります。

H = plot(G,'Layout','layered','Sources',cs,'Sinks',ct, ...
    'EdgeLabel',G.Edges.Weight);
highlight(H,cs,'NodeColor','red')
highlight(H,ct,'NodeColor','green')

Figure contains an axes object. The axes object contains an object of type graphplot.

入力引数

すべて折りたたむ

入力グラフ。graph オブジェクトまたは digraph オブジェクトとして指定します。無向グラフの作成には graph を、有向グラフの作成には digraph を使用します。

例: G = graph(1,2)

例: G = digraph([1 2],[2 3])

ノード ペア。ソース ノードとターゲット ノードを表すノード インデックスまたはノード名の個別の引数として指定します。次の表は、ノードをノード インデックスまたはノード名で参照するさまざまな方法を示しています。

スカラー ノード インデックス1
文字ベクトルのノード名'A'
string スカラーのノード名"A"

例: mf = maxflow(G,'A','B')

例: mf = maxflow(G,1,10)

データ型: double | char | string

最大フロー アルゴリズム。次の表のいずれかの項目として指定します。

メモ

既定以外の algorithm オプションは、有向グラフにのみ指定できます。

オプション説明
'searchtrees' (既定)

ボイコフ・コルモゴロフ アルゴリズムを使用します。ノード s および t に関連する探索木を 2 本作成することにより、最大フローを計算します。

'augmentpath'

フォード・ファルカーソン アルゴリズムを使用します。残余有向グラフで増加経路を検出することにより、最大フローを繰り返し計算します。

有向グラフでは、エッジのいずれかの重みが 0 でない限り、同じ 2 つのノード間に逆方向の平行エッジを含むことができません。したがって、グラフがエッジ [i j] を含む場合、[i j] の重みが 0 かつ/または [j i] の重みが 0 の場合にのみ逆向きエッジ [j i] を含むことができます。

'pushrelabel'

ノードの過剰フローを隣接ノードに押し付け、ノードにラベルを付け直すことにより、最大フローを計算します。

有向グラフでは、エッジのいずれかの重みが 0 でない限り、同じ 2 つのノード間に逆方向の平行エッジを含むことができません。したがって、グラフがエッジ [i j] を含む場合、[i j] の重みが 0 かつ/または [j i] の重みが 0 の場合にのみ逆向きエッジ [j i] を含むことができます。

例: mf = maxflow(G,'A','D','augmentpath')

出力引数

すべて折りたたむ

最大フロー。スカラーとして返されます。

フローの有向グラフ。digraph オブジェクトとして返されます。GFG と同じノードを含みますが、非ゼロ フローをもつ G のエッジのみを含みます。同じ 2 つのノード間に複数のエッジがある多重グラフでは、GF に複数のエッジを通過するフローを表す単一のエッジが含まれます。

最小カットのソース ノード ID。ノード インデックスまたはノード名として返されます。

  • st が数値ノード インデックスを指定する場合、csct もノード インデックスを含みます。

  • st がノード名を指定する場合、csct もノード名を含みます。

最小カットのターゲット ノード ID。ノード インデックスまたはノード名として返されます。

  • st が数値ノード インデックスを指定する場合、csct もノード インデックスを含みます。

  • st がノード名を指定する場合、csct もノード名を含みます。

詳細

すべて折りたたむ

最大フロー

最大フローのコンテキストでは、グラフ内のエッジは、エッジの重みで表される "容量" をもつと見なされます。エッジの容量は、そのエッジを通過できるフローの量です。したがって、グラフ内の 2 つのノード間の最大フローは、連結エッジの容量に基づいて、ソース ノード s からターゲット ノード t まで通過するフローの量を最大にします。

最小カット

最小カットは、csct を連結するすべてのエッジの重みの合計 (カットの重み) が最小になるように、有向グラフのノードを 2 つのセット cs および ct に分割します。最小カットの重みは最大フロー値 mf と等しくなります。

cs および ct の要素はそれぞれ、ノード s および t に対応する G のノードを示します。csctnumel(cs) + numel(ct) = numnodes(G) を満たします。

拡張機能

スレッドベースの環境
MATLAB® の backgroundPool を使用してバックグラウンドでコードを実行するか、Parallel Computing Toolbox™ の ThreadPool を使用してコードを高速化します。

バージョン履歴

R2015b で導入

参考

|