主要内容

maxflow

图中最大流量

在页面中全部折叠

语法

mf = maxflow(G,s,t)
mf = maxflow(G,s,t，算法)
[mf,GF] = maxflow(___）
[mf,GF,cs,ct] = maxflow(___）

描述

例子

曼氏金融= maxflow (G，s t）返回最大流量节点之间年代而且t。如果图G是未加权的(即，G.Edges不包含变量重量),然后maxflow将所有的图边视为权值等于1。

例子

曼氏金融= maxflow (G，s t，算法）指定要使用的最大流量算法。此语法仅在以下情况下可用G是一个有向图。

例子

［曼氏金融，女朋友= maxflow(___）也返回一个有向图对象，女朋友，使用前面语法中的任何输入参数。女朋友是否只使用in中的边形成G有非零流量值的。

例子

［曼氏金融，女朋友，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];权重= [0.77 0.44 0.67 0.75 0.89 0.90 2 0.76 1 1];G =有向图(s,t，权重);情节(G,“EdgeLabel”G.Edges.Weight,“布局”，“分层”）;

图中包含一个axes对象。axes对象包含一个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 =有向图(s,t，权重);H = plot(G，“EdgeLabel”, G.Edges.Weight);

图中包含一个axes对象。axes对象包含一个graphplot类型的对象。

求节点1到节点5之间的最大流量值。指定“augmentpath”使用Ford-Fulkerson算法，并使用两个输出返回非零流的图。

[mf,GF] = maxflow(G,1,5，“augmentpath”）
Mf = 11
GF =属性有向图:边:[6x2表]节点:[5x0表]

突出显示并标记非零流图。

H.EdgeLabel = {};突出(H,女朋友,“EdgeColor”，“r”，“线宽”2);st = GF.Edges.EndNodes;labeledge (H,圣(:1),圣(:,2)GF.Edges.Weight);

图中包含一个axes对象。axes对象包含一个graphplot类型的对象。

打开实时脚本

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

S = [1 1 2 3 3 4 4 5 5];T = [2 3 3 2 5 5 6 4 6];权重= [0.77 0.44 0.67 0.69 0.73 2 0.78 1];G =有向图(s,t，权重);情节(G,“EdgeLabel”G.Edges.Weight,“布局”，“分层”）

图中包含一个axes对象。axes对象包含一个graphplot类型的对象。

求出图的最大流量和最小切割。

[mf，~，cs,ct] = maxflow(G,1,6)
Mf = 0.7300
c =3×11 2 3
ct =3×14 5 6

画出最小切割，用cs节点作为源，而ct节点作为汇。突出了cs节点为红色，而ct节点为绿色。注意，连接这两组节点的边的权值等于最大流量。

H = plot(G，“布局”，“分层”，“源”计算机科学,“汇”ct,.．.“EdgeLabel”, G.Edges.Weight);突出(H, c,“NodeColor”，“红色”)突出(H, ct,“NodeColor”，“绿色”）

图中包含一个axes对象。axes对象包含一个graphplot类型的对象。

输入参数

全部折叠

输入图形，指定为a图或有向图对象。使用图创建无向图或有向图创建一个有向图。

例子:G =图(1,2)

例子:G =有向图([1 2]，[2 3])

节点对，作为节点索引或节点名的单独参数指定，以指示源节点和目标节点。这个表显示了通过节点索引或节点名称引用节点的不同方法。

价值 例子
标量节点索引 1
字符向量节点名称 “一个”
字符串标量节点名称 “一个”

例子:mf = maxflow(G，'A'，'B')

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

数据类型:双|字符|字符串

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

请注意

只能指定nondefault算法带有有向图的选项。

选项 描述
“searchtrees”(默认)

使用Boykov-Kolmogorov算法。通过构造两个与节点相关的搜索树来计算最大流量年代而且t。
“augmentpath”

使用Ford-Fulkerson算法。通过在残差有向图中寻找增广路径迭代计算最大流量。

有向图不能在相同的两个节点之间有任何方向相反的平行边，除非其中一条边的权值为零。如果这个图包含一条边我[j]，那么它可以包含反边我[j]只要重的我[j]的权值是0和/或我[j]是零。
“pushrelabel”

计算最大流量，方法是将节点的多余流量推到相邻节点，然后重新标记该节点。

有向图不能在相同的两个节点之间有任何方向相反的平行边，除非其中一条边的权值为零。如果这个图包含一条边我[j]，那么它可以包含反边我[j]只要重的我[j]的权值是0和/或我[j]是零。

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

输出参数

全部折叠

最大流量，作为标量返回。

流的有向图，返回为有向图对象。女朋友包含相同的节点G，但只包含那些边缘G有非零流量。对于两个节点之间有多条边的多图，女朋友包含一条边，反映通过多条边的流。

最小切割源节点id，作为节点索引或节点名称返回。

  • 如果年代而且t然后指定数值节点索引cs而且ct还要包含节点索引。

  • 如果年代而且t然后指定节点名cs而且ct还要包含节点名。

最小切割目标节点id，作为节点索引或节点名称返回。

  • 如果年代而且t然后指定数值节点索引cs而且ct还要包含节点索引。

  • 如果年代而且t然后指定节点名cs而且ct还要包含节点名。

更多关于

全部折叠

最大流量

在最大流量的情况下，图中的边被认为具有能力由边权值表示。边的容量是指可以通过该边的流量。因此，图中两个节点之间的最大流量会使从源节点通过的流量最大化，年代，到目标节点，t，根据连接边的容量。

删减。

最小切割将有向图节点划分为两个集合，cs而且ct，使得所有连接的边的权值之和cs而且ct(伤口的重量)降到最低。最小切割的权重等于最大流量值，曼氏金融。

里面的条目cs而且ct的节点。G与节点关联年代而且t,分别。cs而且ct满足numel(cs) + numel(ct) = numnodes(G)。

版本历史

在R2015b中引入

另请参阅

|

Baidu
map