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(___) 还使用上述语法中的任何输入参数返回有向图对象 GFGF 仅使用 G 中具有非零流值的边构造。

示例

[mf,GF,cs,ct] = maxflow(___) 还返回源和目标节点 ID csct,表示与最大流相关联的最小割

示例

全部折叠

创建并绘制一个加权图。加权边表示流量。

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. The axes 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. The axes 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. The axes 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. The axes 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. The axes contains an object of type graphplot.

输入参数

全部折叠

输入图,指定为 graphdigraph 对象。可使用 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'(默认值)

使用 Boykov-Kolmogorov 算法。通过构造与节点 st 相关联的两个搜索树,计算最大流。

'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,以节点索引或节点名称形式返回。

  • 如果 st 指定数值节点索引,则 csct 也包含节点索引。

  • 如果 st 指定节点名称,则 csct 也包含节点名称。

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

  • 如果 st 指定数值节点索引,则 csct 也包含节点索引。

  • 如果 st 指定节点名称,则 csct 也包含节点名称。

详细信息

全部折叠

最大流

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

最小割

最小割指将有向图节点分为两个组 - csct,且连接 csct 的所有边的权重之和(割的权重)最小。最小割的权重等于最大流值 mf

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

另请参阅

|

在 R2015b 中推出