图论之流网络和流

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

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

定义:流网络是有向图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为整数值。显然, 该流的值是整数是整数值流。

微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?