图论之流网络和流

流动网络是用于对物料流动建模的有向图。有两个不同的顶点。一种是以一定的稳定速率生产物料的源, 另一种是以相同的恒定速度消耗物料的水槽。材料在系统中任何标记处的流动是元件移动的速率。
可以使用流动网络对一些现实生活中的问题进行建模, 例如液体通过管道的流动, 通过电线的电流和货物的输送。
定义:流网络是有向图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为整数值。显然, 该流的值是整数是整数值流。

    推荐阅读