图论算法---最大流问题ppt课件.ppt

图论算法 - 最大流问题 长沙市雅礼中学 朱 全 民 运输网络 现在想将一些物资从S 运抵T ，必须经过一些中转站。连接中 转站的是公路，每条公路都有最大运载量。 每条弧代表一条公路，弧上的数表示该公路的最大运载量。 最多能将多少货物从S 运抵T ？ 4 2 4 8 4 7 3 6 2 1 S T V1 V2 V3 V4 公路运输图基本概念 这是一个典型的网络流模型。为了解答此题，我们先 了解网络流的有关定义和概念。 若有向图G=(V,E) 满足下列条件： 1. 有且仅有一个顶点S ，它的入度为零，即d-(S) = 0 ，这 个顶点S 便称为源点，或称为发点。 2. 有且仅有一个顶点T ，它的出度为零，即d+(T) = 0 ，这 个顶点T 便称为汇点，或称为收点。 3. 每一条弧都有非负数，叫做该边的容量。边(vi, vj) 的容 量用cij表示。 则称之为网络流图，记为G = (V, E, C)