Main Content

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

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' 使用 Ford-Fulkerson 算法，并使用两个输出以返回非零流的图。

[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 节点以绿色突出显示。请注意，连接这两组节点的边的权重等于最大流。

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'
字符串标量节点名称"A"

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

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

数据类型: double | char | string

最大流算法，指定为下表中的条目之一。

注意

对于有向图，您只能指定非默认 algorithm 选项。

选项描述
'searchtrees'（默认值）

使用博伊科夫-科尔莫戈洛夫算法。通过构造与节点 s 和 t 相关联的两个搜索树，计算最大流。

'augmentpath'

使用 Ford-Fulkerson 算法。通过求残差有向图中的增广路径，以迭代方式计算最大流。

有向图中相同的两个节点之间不能有相反方向的任何平行边，除非这些边中某条边的权重为零。因此，如果图包含边 [i j]，则仅当 [i j] 的权重为零和/或 [j i] 的权重为零时，它才能包含反向边 [j i]。

'pushrelabel'

通过将某节点的余流推送到其相邻节点并为该节点重新添加标签，计算最大流。

有向图中相同的两个节点之间不能有相反方向的任何平行边，除非这些边中某条边的权重为零。因此，如果图包含边 [i j]，则仅当 [i j] 的权重为零和/或 [j i] 的权重为零时，它才能包含反向边 [j i]。

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

输出参量

全部折叠

最大流，以标量形式返回。

流的有向图，以 digraph 对象形式返回。GF 包含的节点与 G 相同，但仅包含 G 的具有非零流的边。对于相同的两个节点之间具有多条边的多重图来说，GF 只包含一条边，反映多条边的流向。

最小割源节点 ID，以节点索引或节点名称形式返回。

  • 如果 s 和 t 指定数值节点索引，则 cs 和 ct 也包含节点索引。

  • 如果 s 和 t 指定节点名称，则 cs 和 ct 也包含节点名称。

最小割目标节点 ID，以节点索引或节点名称形式返回。

  • 如果 s 和 t 指定数值节点索引，则 cs 和 ct 也包含节点索引。

  • 如果 s 和 t 指定节点名称，则 cs 和 ct 也包含节点名称。

详细信息

全部折叠

最大流

在最大流情景中，图中的边被视为具有由边权重表示的容量。边的容量是可通过该边的流量。因此，图中两个节点之间的最大流代表基于各连接边的容量可从源节点 s 传递到目标节点 t 的最大流量。

最小割

最小割指将有向图节点分为两个组 - cs 和 ct，且连接 cs 和 ct 的所有边的权重之和（割的权重）最小。最小割的权重等于最大流值 mf。

cs 和 ct 中的条目指示 G 的分别与节点 s 和 t 相关联的节点。cs 和 ct 满足 numel(cs) + numel(ct) = numnodes(G)。

扩展功能

基于线程的环境
使用 MATLAB® backgroundPool 在后台运行代码或使用 Parallel Computing Toolbox™ ThreadPool 加快代码运行速度。

版本历史记录

在 R2015b 中推出

另请参阅

|