第四节 与 最大流问题 .pptVIP

第四节 最大流问题 最大流问题是一类应用极为广泛的问题，例如在交通运输网络中有人流、车流、货物流，供水网络中有水流，金融系统中有现金流，通讯系统中有信息流，等等。50年代福特（Ford）、富克逊（Fulkerson）建立的“网络流理论”，是网络应用的重要组成部分。 一、最大流有关概念 如果我们把图5-41年做输油管道网， 为起点， 为终点， 为中转站，边上的数表示该管道的最大输油能力，问应该如何安排各管道输油量，才能使从 到 的总输油量最大？ 管道网络中每边的最大通过能力即容量是有限的，实际流量也不一定等于容量，上述问题就是要讨论如何充分利用装置的能力，以取得最好效果（流量最大），这类问题通常称为最大流问题。 定义20 设有向连通图 的每条边上有非负数称 为边容量，仅有一个r入次为0的点 称为发点（源），一个出次为0的点 称为收点 （汇），其余点为中间点，这样的网络G称为容量网络，常记做 。 对任一G中的边 有流量，称集合 为G的一个流。称满足下列条件的流 为可行流： （1）容量限制条件：对G中每条边， 有 （2）平衡条件：对中间点 ，有 （即中间点 的物资的输入量与输出量相等） 对收、发点 有 （即从 点发出的物资总量等于 点输入量）W为网络流的总流量。 可行流总是存在的，例如 就是一个流量为0的可行流。所谓最大流问题就是在容量网络中，寻找流量最大的可行流。 一个流 ，当 则称流 对边 是饱和的，否则称 对 不饱和。最大流问题实际是个线性规划问题，但是利用它与图的紧密关系，能更为直观简便地求解。 定义21 容量网络 为发、收点，若有边集 为E的子集，将G分为两个子图 其顶点集合分别记 分别属于 ，满足：① 不连通；② 为 的真子集，而 仍连通，则称 为G的割集，记 。 割集 中所有始点在S，终点在 的边的容量之和，称为 的割集容量，记为 。如图5-41中，边集 和边集 都是G的割集，它们割集容量分别为9和11。容量网络G的割集有多个，其中割集容量最小者称为网络G的最小割集容量（简称最小割）。 二、最大流-最小割 定理 由割集的定义不难看出，在容量网络中割集是由 到 的必经之路，无论拿掉哪个割集， 到 便不再相通，所以任何一个可行流的流量不会超过任一割集的容量，也即网络的最大流与最小割容量（最小割）满足下面定理。 定理10 设f为网络G=(V,E,C)的任一可行流，流量为 是分离 的任一割集，则有 由此可知，若能找到一个可行流 一个割集 ，使得 的流量 ，则 一定是最大流，而 就是所有割集中容量最小的一个。下面证明最大流-最小割定理，定理的证明实际上就是给出了寻找最大流的方法。 定理11（最大流-最小割定理）任一网络G中，从 到 的最大流的流量等于分高 的最小割的容量。 证明 设 是一个最大流，流量为W，用下面的方法定义点集 令 若点 且 则令 若点 且 则令 在这种定义下， 一定不属于 ，若否， 则得到一条从 到 的链 ，规定 到 为链 的方向，链上与 方向一致的边叫前向边，与 方向相反的边称为后向边，即 如图5-42中 为前向边 为后向边。 根据 的定义， 中的前向边 上必有 ，后向边上必有 令 当 为前向边 当 为后向边 取 ，显然 。 我们把 修改为 ：