跳转到内容
- 弧上的权重称为容量。
- 网络的起点称为源（S）；网络的终点称为汇点（T）。
- 承载其全部容量的弧被称为饱和的。
- 割是指将 S 与 T 分开的连续线，并且不穿过任何节点。
- 除了 S 和 T 之外，流入一个节点的流量总和必须等于流出该节点的流量总和。
- 最大流 - 最小割定理
- 通过网络的流量不能超过任何割的价值。
- 最大流量等于最小割的价值。
- 这意味着，如果您能够通过观察找到具有相同值的流量和割，那么最大流 - 最小割定理告诉您，您已经获得了最大流量。
- 标记过程通过系统地增加任何初始流量来找到最大流量
- 以任何初始流量或零流量开始。
- 用两条弧替换每条弧：一条显示流量可以增加的量（其剩余容量），另一条显示流量可以减少的量（其潜在回流）。
- 如果 S 仍然与 T 相连，则找到从 S 到 T 的新流量，并根据需要更改剩余容量和潜在回流。
- 重复步骤 3，直到 S 与 T 断开连接。
- 如果 S 与 T 断开连接，则最大流量是步骤 1 和 3 中所有流量的总和。
- 如果网络具有多个源，则创建一个新的超级源；如果它具有多个汇点，则创建一个新的超级汇点。
- 如果节点具有限制的容量，则用两个无限制的节点替换它，这两个节点通过具有相关容量的弧连接。
- 对于弧具有上限和下限容量的网络，割的价值为
- 从 S 到 T 方向穿过割线的上限容量的总和减去从 T 到 S 方向穿过割线的下限容量的总和。
- 对于这样的网络，对于标记过程，回流使用最小容量计算。例如，对于一条上限容量为 8、下限容量为 1 的弧上的流量 5，剩余容量为 3，潜在回流为 4。
