图论之流网络和流

2022-04-20 IT知识

流动网络是用于对物料流动建模的有向图。有两个不同的顶点。一种是以一定的稳定速率生产物料的源, 另一种是以相同的恒定速度消耗物料的水槽。材料在系统中任何标记处的流动是元件移动的速率。
可以使用流动网络对一些现实生活中的问题进行建模, 例如液体通过管道的流动, 通过电线的电流和货物的输送。
定义：流网络是有向图G =（V, E）, 使得

对于每个边（u, v）∈E, 我们将一个非负权重容量c（u, v）≥0关联; 如果（u, v）?E, 则假定c（u, v）= 0。
有两个区别点, 即源s和宿t。
对于每个顶点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的最大值流。
这三个属性可以描述如下：

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

文章图片
流量的值是来自源的净流量,

文章图片
进入顶点v的正净流量描述为

文章图片
对称地描述离开顶点的正净流量。流量守恒属性的一种解释是, 除了源或汇之外, 进入顶点的正净流量必须等于离开顶点的正净流量。
【图论之流网络和流】如果f（u, v）是所有（u, v）∈E的整数, 则称流f为整数值。显然, 该流的值是整数是整数值流。

推荐阅读

上一篇：PyTorch与TensorFlow差异比较（有什么区别（哪个更好？））

下一篇：图论（网络流量问题）