8 图与网络4--最大流问题.pdf

Chapter8 图与网络优化 ( Graph Theory and Network Analysis ) 本章主要内容： 图的基本概念与模型 最大流问题 树与图的最小树 最小费用最大流问题 最短路问题 中国邮递员 网络的最大流 Page 2 如何制定一个运输计划使生产地到销售地的产品输送量最大。 这就是一个网络最大流问题。 网络的最大流 Page 3 下图是一个输油管道网，v 为起点，v 为终点，v ~v 为中转站， s t 1 6 弧旁的数表示该管道的最大输油量。 问题：如何安排，才能使从v 到v 的输油量最大？ s t v1 2 v2 o o 4 6 4 2 v5 v3 vs o 3 o o 2 o vt 7 4 2 1 1 o 3 o v6 v4 基本概念： Page 4 1. 容量网络：对网络上的每条弧(v ,v )都给出一个最大的通 i j 过能力，称为该弧的容量，简记为c 。容量网络中通常规定 ij 一个发点(也称源点，入次为0 ，记为s)和一个收点(也称汇点， 出次为0 ，记为t) ，网络中其他点称为中间点。 4 ① ③ 7 4 1 s 4 6 t 8 2 9 ② 2 ④ 网络的最大流 Page 5 2. 网络的最大流 是指网络中从发点到收点之间允许通过的最大流量。 3. 流与可行流 流是指加在网络各