MATLAB 帮助中心
本页翻译不是最新的。点击此处可查看最新英文版本。
图中的最大流
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
G
s,t
s
t
G.Edges
Weight
maxflow
示例
mf = maxflow(G,s,t,algorithm) 指定要使用的最大流算法。此语法仅在 G 为有向图时可用。
algorithm
[mf,GF] = maxflow(___) 支持上述语法中的任何输入参量,且可返回有向图对象 GF。GF 仅使用 G 中具有非零流值的边构造。
GF
[mf,GF,cs,ct] = maxflow(___) 还返回源和目标节点 ID cs 和 ct,表示与最大流相关联的最小割。
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' 使用 Ford-Fulkerson 算法,并使用两个输出以返回非零流的图。
'augmentpath'
[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 节点以绿色突出显示。请注意,连接这两组节点的边的权重等于最大流。
H = plot(G,'Layout','layered','Sources',cs,'Sinks',ct, ... 'EdgeLabel',G.Edges.Weight); highlight(H,cs,'NodeColor','red') highlight(H,ct,'NodeColor','green')
graph
digraph
输入图,指定为 graph 或 digraph 对象。可使用 graph 创建一个无向图,或使用 digraph 创建一个有向图。
示例: G = graph(1,2)
G = graph(1,2)
示例: G = digraph([1 2],[2 3])
G = digraph([1 2],[2 3])
节点对组,指定为单独的节点索引或节点名称参量,用于指示源节点和目标节点。下表显示通过节点索引或节点名称引用节点的不同方法。
1
'A'
"A"
示例: mf = maxflow(G,'A','B')
mf = maxflow(G,'A','B')
示例: mf = maxflow(G,1,10)
mf = maxflow(G,1,10)
数据类型: double | char | string
double
char
string
'searchtrees'
'pushrelabel'
最大流算法,指定为下表中的条目之一。
注意
对于有向图,您只能指定非默认 algorithm 选项。
使用博伊科夫-科尔莫戈洛夫算法。通过构造与节点 s 和 t 相关联的两个搜索树,计算最大流。
使用 Ford-Fulkerson 算法。通过求残差有向图中的增广路径,以迭代方式计算最大流。
有向图中相同的两个节点之间不能有相反方向的任何平行边,除非这些边中某条边的权重为零。因此,如果图包含边 [i j],则仅当 [i j] 的权重为零和/或 [j i] 的权重为零时,它才能包含反向边 [j i]。
[i j]
[j i]
通过将某节点的余流推送到其相邻节点并为该节点重新添加标签,计算最大流。
示例: mf = maxflow(G,'A','D','augmentpath')
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,且连接 cs 和 ct 的所有边的权重之和(割的权重)最小。最小割的权重等于最大流值 mf。
cs 和 ct 中的条目指示 G 的分别与节点 s 和 t 相关联的节点。cs 和 ct 满足 numel(cs) + numel(ct) = numnodes(G)。
numel(cs) + numel(ct) = numnodes(G)
全部展开
backgroundPool
ThreadPool
在 R2015b 中推出
graph | digraph
You clicked a link that corresponds to this MATLAB command:
Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.
选择网站
选择网站以获取翻译的可用内容,以及查看当地活动和优惠。根据您的位置,我们建议您选择:。
您也可以从以下列表中选择网站:
如何获得最佳网站性能
选择中国网站(中文或英文)以获得最佳网站性能。其他 MathWorks 国家/地区网站并未针对您所在位置的访问进行优化。
美洲
欧洲
亚太
联系您当地的办事处