主要内容

graphmaxflow

(删除)计算有向图中的最大流量

graphmaxflow已被删除。使用maxflow代替。详情请参见版本历史．

语法

［MaxFlow，FlowMatrix，减少= graphmaxflow(G，综述，TNode）
[…= graphmaxflow(G，综述，TNode,“能力”,CapacityValue,……)
[…= graphmaxflow(G，综述，TNode,“方法”,MethodValue,……)

参数

G 表示有向图的n × n邻接矩阵。矩阵中的非零元素G表示边的容量。
综述 节点G．
TNode 节点G．
CapacityValue 列向量，指定矩阵中边的自定义容量G．对于矩阵中的每一个非零值(边)，它必须有一个条目G．向量中自定义容量的顺序必须与矩阵中非零值的顺序匹配G当按列遍历时。默认情况下,graphmaxflow从矩阵中的非零项中获取容量信息G．
MethodValue 字符向量或字符串，指定用于查找最小生成树(MST)的算法。的选择是:

  • “埃德蒙兹”-使用Edmonds和Karp算法，该算法的实现基于一种称为标记算法．时间复杂度为* E O (N ^ 2),在那里N而且E分别为节点数和边数。

  • “戈德堡”—默认算法。使用戈德堡算法，它使用的通用方法称为preflow-push．时间复杂度为O (N ^ 2 *√(E)),在那里N而且E分别为节点数和边数。

描述

提示

有关图论函数的介绍性信息，请参见图论函数．

［MaxFlow，FlowMatrix，减少= graphmaxflow(G，综述，TNode）计算有向图的最大流量G从节点综述到节点TNode．输入G是一个表示有向图的n × n邻接矩阵。矩阵中的非零元素G表示边的容量。输出MaxFlow是最大流量，和FlowMatrix是一个邻接矩阵，包含每条边的所有流量值。FlowMatrix（X，Y)是来自节点的流X到节点Y．输出减少逻辑行向量是否表示所连接的节点综述在计算了最小切割之间综述而且TNode．如果最小切割问题存在多万博 尤文图斯个解，则减少是一个矩阵。

提示

算法决定了减少的时间复杂度为O (2 ^N）,在那里N是节点数。如果不需要此信息，请使用graphmaxflow函数没有第三个输出。

[…= graphmaxflow(G，综述，TNode,……”PropertyName”,PropertyValue,……)调用graphmaxflow使用属性名/属性值对的可选属性。可以以任意顺序指定一个或多个属性。每一个PropertyName必须用单引号括起来，不区分大小写。这些属性名/属性值对如下:

[…= graphmaxflow(G，综述，TNode,“能力”,CapacityValue,……)允许您为边缘指定自定义容量。CapacityValue列向量是否对矩阵中的每一个非零值(边)都有一个条目G．向量中自定义容量的顺序必须与矩阵中非零值的顺序匹配G当按列遍历时。默认情况下,graphmaxflow从矩阵中的非零项中获取容量信息G．

[…= graphmaxflow(G，综述，TNode,“方法”,MethodValue,……)允许指定用于查找最小生成树(MST)的算法。的选择是:

  • “埃德蒙兹”-使用Edmonds和Karp算法，该算法的实现基于一种称为标记算法．时间复杂度为* E O (N ^ 2),在那里N而且E分别为节点数和边数。

  • “戈德堡”—默认算法。使用戈德堡算法，它使用的通用方法称为preflow-push．时间复杂度为O (N ^ 2 *√(E)),在那里N而且E分别为节点数和边数。

参考文献

[1]埃德蒙兹，J.和卡普，R.M.(1972)。网络流问题算法效率的理论改进。美国计算机学会学报19, 248 - 264。

戈德堡，A.V.(1985)。一种新的最大流量算法。MIT/LCS/TM-291，麻省理工学院计算机科学实验室。

[3] Siek, j.g.， Lee, L-Q，和Lumsdaine, A.(2002)。Boost图形库用户指南和参考手册，(上马鞍河，新泽西州:皮尔逊教育)。

版本历史

在R2006b中引入

全部展开