maxflow

グラフの最大フロー

構文

mf = maxflow(G,s,t)

mf = maxflow(G,s,t,algorithm)

[mf,GF] = maxflow(___)

[mf,GF,cs,ct] = maxflow(___)

説明

mf = maxflow(G,s,t) は、ノード s と t の間の最大フローを返します。グラフ 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');

ノード 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);

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

[mf,GF] = maxflow(G,1,5,'augmentpath')

mf = 
11

GF = 
  digraph with properties:

    Edges: [6×2 table]
    Nodes: [5×0 table]

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

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

最小カットの計算

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

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')

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

[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')

入力引数

G — 入力グラフ

graph オブジェクト | digraph オブジェクト

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

例: G = graph(1,2)

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

s,t — ノード ペア (個別の引数として指定)

ノード インデックス | ノード名

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

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

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

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

データ型: double | char | string

algorithm — 最大フロー アルゴリズム

'searchtrees' (既定値) | 'augmentpath' | 'pushrelabel'

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

メモ

既定以外の 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')

出力引数

mf — 最大フロー

スカラー

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

GF — フローの有向グラフ

digraph オブジェクト

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

cs — 最小カットのソース ノード ID

ノード インデックス | ノード名

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

• s と t が数値ノード インデックスを指定する場合、cs と ct もノード インデックスを含みます。

• s と t がノード名を指定する場合、cs と ct もノード名を含みます。

ct — 最小カットのターゲット ノード ID

スカラー | ベクトル | 文字ベクトル | 文字ベクトルの cell 配列

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

• s と t が数値ノード インデックスを指定する場合、cs と ct もノード インデックスを含みます。

• s と t がノード名を指定する場合、cs と ct もノード名を含みます。

詳細

最大フロー

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

最小カット

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

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

拡張機能

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

バージョン履歴

R2015b で導入

参考

graph | digraph