图论之流网络和流

流动网络是用于对物料流动建模的有向图。有两个不同的顶点。一种是以一定的稳定速率生产物料的源, 另一种是以相同的恒定速度消耗物料的水槽。材料在系统中任何标记处的流动是元件移动的速率。

可以使用流动网络对一些现实生活中的问题进行建模, 例如液体通过管道的流动, 通过电线的电流和货物的输送。

定义：流网络是有向图G =（V, E）, 使得

1. 对于每个边（u, v）∈E, 我们将一个非负权重容量c（u, v）≥0关联;如果（u, v）∉E, 则假定c（u, v）= 0。
2. 有两个区别点, 即源s和宿t。
3. 对于每个顶点v∈V, 都有一条从s到t的包含v的路径。

令G =（V, E）为流动网络。让我们成为网络的源头, 让我们成为汇点。 G中的流是一个实值函数f：V x V→R, 使得以下属性成立：

• 容量约束：对于所有u, v∈V, 我们需要f（u, v）≤c（u, v）。
• 偏斜对称性：对于所有u, v∈V, 我们需要f（u, v）=-f（u, v）。
• 流量守恒：对于所有u∈V- {s, t}, 我们需要

量f（u, v）可以为正也可以为负, 称为从顶点u到顶点v的净流量。在最大流量问题中, 我们给定了一个流量网络G, 其流量为s, 流量为t, 我们希望找到从s到t的最大值流。

这三个属性可以描述如下：

1. 容量约束确保通过每个边缘的流量不大于容量。
2. 偏斜对称性意味着从u到v的流量是从v到u的流量的负数。
3. 流量守恒属性表示从源或汇以外的顶点流出的总净流量为0。换句话说, 流入av的量与每个顶点v∈流出v的量相同。 V-{s, t}

流量的值是来自源的净流量,

进入顶点v的正净流量描述为

对称地描述离开顶点的正净流量。流量守恒属性的一种解释是, 除了源或汇之外, 进入顶点的正净流量必须等于离开顶点的正净流量。

如果f（u, v）是所有（u, v）∈E的整数, 则称流f为整数值。显然, 该流的值是整数是整数值流。