最大流问题1.pptVIP

最大流问题 具有实际背景的例子 国庆大假期间旅游非常火爆，机票早已订购一空。成都一家旅行社由于信誉好、服务好，所策划的国庆首都游的行情看好，要求参加的游客众多，游客甚至不惜多花机票钱暂转取道它地也愿参加此游。旅行社只好紧急电传他在全国各地的办事处要求协助解决此问题。很快，各办事处将其已订购机票的情况传到了总社。根据此资料，总社要作出计划，最多能将多少游客从成都送往北京以及如何取道转机。下面是各办事处已订购机票的详细情况表： 多个发点多个收点的情形 最大匹配问题 例 * 给定一个有向图G＝(V,E)，其中仅有一个点的入次为零称为发点（源），记为vs，仅有一个点的出次为零称为收点（汇），记为vt，其余点称为中间点。 基本概念 3 5 1 1 4 2 3 5 2 vs v2 v1 v3 v4 vt 对于G中的每一个弧(vi,vj)，相应地给一个数cij（cij≥0），称为弧(vi,vj)的容量。我们把这样的D称为网络（或容量网络），记为G＝(V,E,C)。 所谓网络上的流，是指定义在弧集E上的函数f＝{f(vi,vj)}，并称f(vi,vj)为弧(vi,vj)上的流量，简记为fij。 可行流、可行流的流量、最大流。 3,1 5,2 1,0 1,0 4,1 2,2 3,1 5,2 2,1 vs v2 v1 v3 v4 vt 标示方式：每条边上标示两个数字，第一个是容量，第二是流量 可行流、可行流的流量、最大流。 可行流是指满足如下条件的流： （1）容量限制条件：对G中每条边(vi,vj), 有 （2）平衡条件： 对中间点，有： （即中间点vi的物资输入量等于输出量） 对收点vt与发点vs，有： （即vs发出的物资总量等于vt接收的物资总量），W是网络的总流量。 可行流总是存在的，例如f={0}就是一个流量为0的可行流。 所谓最大流问题就是在容量网络中寻找流量最大的可行流。 一个流f={fij}，当fij=cij，则称f对边(vi, vj)是饱和的，否则称f对边(vi, vj)不饱和。 最大流问题实际上是一个线性规划问题。 但利用它与图的密切关系，可以利用图直观简便地求解。 给定容量网络G＝(V,A,E)，若点集V被剖分为两个非空集合V1和V2，使 vs∈V1 ，vt∈V2，则把弧集(V1,V2)称为（分离vs和vt的）割集。 显然，若把某一割集的弧从网络中去掉，则从vs到vt便不存在路。所以，直观上说，割集是从vs到vt的必经之路。 3 5 1 1 4 2 3 5 2 vs v2 v1 v3 v4 vt 图中红色曲线表示的割集是端点分别在集合V1={vs, v1, v2}与V2={v3, v4, vt}的弧集。但割集不是唯一的。 割集的容量(简称割量) 最小割集 割集(V1, V2)中所有起点在V1，终点在V2的边的容量的和称为割集容量。例如下图中所示割集的容量为5（注意不是6） 3 5 1 1 4 2 3 5 2 vs v2 v1 v3 v4 vt 在容量网络的所有割集中，割集容量最小的割集称为最小割集（最小割）。 对于可行流f＝{fij}，我们把网络中使fij＝cij的弧称为饱和弧，使fijcij的弧称为非饱和弧；把使fij＝0的弧称为零流弧，使fij0的弧称为非零流弧。 设f是一个可行流，μ是从vs到vt的一条链，若μ满足前向弧都是非饱和弧,后向弧都是都是非零流弧,则称μ是（可行流f的）一条增广链。 3,1 5,2 1,0 1,0 4,1 2,2 3,1 5,2 2,1 vs v2 v1 v3 v4 vt 若μ是联结发点vs和收点vt的一条链，我们规定链的方向是从vs到vt，则链上的弧被分成两类：前向弧、后向弧。 对最大流问题有下列定理： 定理1 容量网络中任一可行流的流量不超过其任一割集的容量。 定理2（最大流-最小割定理）任一容量网络中，最大流的流量等于最小割集的割量。 推论1 可行流f*＝{fij*}是最大流，当且仅当G中不存在关于f*的增广链。 求最大流的标号法 标号法思想是：先找一个可行流。对于一个可行流，经过标号过程得到从发点vs到收点vt的增广链；经过调整过程沿增广链增加可行流的流量，得新的可行流。重复这一过程，直到可行流无增广链，得到最大流。 标号过程: (1)给vs标号(-,+∞)，vs成为已标号未检查的点，其余都是未标号点。 (2)取一个已标号未检查的点vi，对一切未标号点vj：若有非饱和弧(vi,vj)（即以vi为起点的非饱和弧），则vj标号(vi,l(vj))，其中l(vj)＝min[l(vi),cij – fij]，vj成为已标号未检查的点；若有