FindMaximumFlow

FindMaximumFlow[g,s,t]

求图 g 中从源顶点 s 到目标顶点 t 之间的最大流.

FindMaximumFlow[m,s,t]

求带有边容量矩阵 m 的图中顶点索引 s 和 t 之间的最大流.

FindMaximumFlow[data,{s1,…},{t1,…}]

求多个源 s1、… 和多个目标 t1、… 之间的最大流.

FindMaximumFlow[data,source,target,"property"]

返回 "property" 的值.

FindMaximumFlow[{vw,…},…]

使用规则 vw 指定图 g.

更多信息和选项

  • FindMaximumFlow 在受容量约束的情况下，求从源顶点到目标顶点的最大流.
  • 默认情况下，返回最大流.
  • 矩阵和 SparseArray 对象可以用于 FindMaximumFlow 中.
  • 对于无向图，边具有同时及同容量的两个方向上的流.
  • 忽略自环，并且合并平行边.
  • FindMaximumFlow[data,source,target,"OptimumFlowData"] 返回 OptimumFlowData 对象 flowdata，它可以用于提取额外属性，使用形式为 flowdata["property"].
  • FindMaximumFlow[data,source,target,"property"] 可用于直接给出 "property" 的值.
  • 与最优流数据相关的属性包括：
  • "EdgeList"贡献给流的边列表
    "FlowGraph"贡献给流的顶点和边组成的图
    "FlowMatrix"顶点对之间的边流组成的矩阵
    "FlowTable"边流的格式化表格
    "FlowValue"流的值
    "ResidualGraph"流的剩余图
    "VertexList"贡献给流的顶点列表
  • 可以给出下列选项：
  • EdgeCapacity Automatic每条边的容量
    VertexCapacity Automatic每个顶点的容量
  • 默认设置 EdgeCapacity->Automatic 下，边的容量等于图 g 的 EdgeCapacity；否则是 1.
  • 默认设置 VertexCapacity->Automatic 下，顶点的容量等于图 g 的 VertexCapacity；否则是 Infinity.
  • FindMaximumFlow 作用于无向图、有向图、多重图和混合图.

范例

打开所有单元关闭所有单元

基本范例  (2)

求图中两个顶点之间的最大流：

求 "s" 和 "t" 之间的最大流：

突出显示流：

范围  (10)

FindMaximumFlow 可用于无向图：

有向图：

多重图：

混合图：

具有边容量的图：

使用规则指定图：

计算边容量矩阵的最大流：

计算多个源和多个汇之间的最大流：

求最大流的属性：

最大流的值：

贡献给流的边列表：

边流矩阵：

显示流：

FindMaximumFlow 可用于大规模图：

选项  (2)

EdgeCapacity  (1)

默认情况下，如果存在的话，边的容量是它的 EdgeCapacity 属性，否则是 1：

使用 EdgeCapacity->capacities 来设置边容量：

VertexCapacity  (1)

默认情况下，如果存在的话，顶点的容量是它的 VertexCapacity，否则是 Infinity：

使用 VertexCapacity->capacities 来设置顶点容量：

应用  (7)

交通网络  (3)

根据1940年苏维埃铁路网，求从西苏联运送到东欧目的地的货物的最大量：

从编入索引的城市 {1,5,6,7,9,12,13,18} 到 {44,40} 的最大流量值：

可视化流：

一个服务于六大加拿大城市的铁路网络，以及每日的车厢数目：

求从温哥华到温尼伯可以运载的最大车厢数量：

城市之间的车厢数：

显示车厢流：

在下面给定容量的地区配电网络中，求可以配送到湾仔的最大功率：

显示流：

网络连通性  (2)

一个描述10个组织机构间的信息流的有向网络在某美国中西部城市存在社会福利问题. 求从 COUN 到 COMM 的最大可能信息流：

求最大流和流图：

一个小镇有7个居民，4个俱乐部和3个政治团体. 每个居民是至少一个俱乐部的成员，并且属于恰好一个政治团体. 在一个平衡议会中，每个俱乐部必须提名一个成员来在小镇议会中代表它，因此属于政治团体 的议会成员数目至多为 . 求是否可能创建一个平衡议会:

由于最大流值等于4，这意味着该小镇有一个平衡议会：

流图线上可能的平衡议会是 R1、R2、R4 和 R5：

任务分配问题  (2)

一个公司含有大量不同工作. 每个员工只适合某些工作，而每个人一次最多只需一个任务. 求同时能够执行的最大任务数：

从全部员工到全部任务的最大流给出同时任务的数目：

显示可能的任务分配：

给定一组女士，每个对某一子集的男生感兴趣，求只允许与兴趣匹配的最大匹配：

由于您想要每个人匹配一次，把顶点容量限制为1：

可能的匹配：

属性和关系  (5)

对于内部顶点而言，入流的和等于出流之和：

内部顶点的入流：

内部顶点的出流：

具有自环的图视为简单图：

两个顶点之间的边连通性等于最大流的值：

两个顶点之间的顶点连通性可以使用 FindMaximumFlow 求得：

Wolfram Research (2012)，FindMaximumFlow，Wolfram 语言函数，https://reference.wolfram.com/language/ref/FindMaximumFlow.html （更新于 2015 年）.

文本

Wolfram Research (2012)，FindMaximumFlow，Wolfram 语言函数，https://reference.wolfram.com/language/ref/FindMaximumFlow.html （更新于 2015 年）.

CMS

Wolfram 语言. 2012. "FindMaximumFlow." Wolfram 语言与系统参考资料中心. Wolfram Research. 最新版本 2015. https://reference.wolfram.com/language/ref/FindMaximumFlow.html.

APA

Wolfram 语言. (2012). FindMaximumFlow. Wolfram 语言与系统参考资料中心. 追溯自 https://reference.wolfram.com/language/ref/FindMaximumFlow.html 年

BibTeX

@misc{reference.wolfram_2024_findmaximumflow, author="Wolfram Research", title="{FindMaximumFlow}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindMaximumFlow.html}", note=[Accessed: 21-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_findmaximumflow, organization={Wolfram Research}, title={FindMaximumFlow}, year={2015}, url={https://reference.wolfram.com/language/ref/FindMaximumFlow.html}, note=[Accessed: 21-November-2024 ]}