算法中的网络流是什么意思？请简单介绍一下啊？
发布网友
发布时间：2022-04-19 09:42
共1个回答
热心网友
时间：2023-06-28 09:05
现在想将一些物资从S运抵T，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。如下图：
每条弧代表一条公路，弧上的数表示该公路的最大运载量。最多能将多少货物从S运抵T？
这是一个典型的网络流模型。为了解答此题，我们先了解网络流的有关定义和概念。
若有向图G=(V,E)满足下列条件：
1、 有且仅有一个顶点S，它的入度为零，即d-(S) = 0，这个顶点S便称为源点，或称为发点。
2、 有且仅有一个顶点T，它的出度为零，即d+(T) = 0，这个顶点T便称为汇点，或称为收点。
3、 每一条弧都有非负数，叫做该边的容量。边(vi, vj)的容量用cij表示。
则称之为网络流图，记为G = (V, E, C)
