Chap6图与网络分析.pptx

p图的基本概念与模型p树图和图的最小生成树p最短路问题p中国邮递员问题p网络最大流运筹学基础及应用之图与网络分析Copyrights 2006-powered by nerdpal HITo最短路问题:从给定的网络图中找出某一点到其它点的最短距离o公认的求最短路径问题的较好的算法是由E.W.Dijkstra(狄克斯屈拉)于1959年给出的标号法最短路问题Copyrights 2006-powered by nerdpal HITV1V5V6V2V3V75727241360226V4Dijkstra标号法Copyrights 2006-powered by nerdpal HITV1V5V6V2V3V75727241360226V45Dijkstra标号法Copyrights 2006-powered by nerdpal HITV1V5V6V2V3V75727241360226V456Dijkstra标号法Copyrights 2006-powered by nerdpal HITV1V5V6V2V3V75727241360226V45677Dijkstra标号法Copyrights 2006-powered by nerdpal HITV1V5V6V2V3V75727241360226V4567710Dijkstra标号法Copyrights 2006-powered by nerdpal HIT2V1V5V6V2V3V7577241360226V4Dijkstra标号法有向图Copyrights 2006-powered by nerdpal HIT2V1V5V6V2V3V7577241360226V45Dijkstra标号法有向图Copyrights 2006-powered by nerdpal HIT2V1V5V6V2V3V7577241360226V459Dijkstra标号法有向图Copyrights 2006-powered by nerdpal HIT2V1V5V6V2V3V7577241360226V45119Dijkstra标号法有向图Copyrights 2006-powered by nerdpal HIT2V1V5V6V2V3V7577241360226V4511129Dijkstra标号法有向图Copyrights 2006-powered by nerdpal HIT2V1V5V6V2V3V7577241360226V451112915Dijkstra标号法有向图Copyrights 2006-powered by nerdpal HIT最短路问题的数学模型p图的基本概念与模型p树图和图的最小生成树p最短路问题p中国邮递员问题p网络最大流运筹学基础及应用之图与网络分析Copyrights 2006-powered by nerdpal HIT一个邮递员从邮局出发，走遍他负责投递的每一条街道，然后再返回邮局，问应选择什么样的路线，使走的路程最短？V1V4V10V2V3V8V7V6V5V11V12V13V944444474522521521中国邮路问题类似于欧拉回路欧拉回路Copyrights 2006-powered by nerdpal HITKonigsberg七桥问题欧拉回路欧拉图ACBDABCDCopyrights 2006-powered by nerdpal HITa)是欧拉图；b)不是欧拉图，但存在欧拉回路；c)即不是欧拉图，也不存在欧拉回路。例(a)(b)(b)(c)(c)Copyrights 2006-powered by nerdpal HITV1V4V10V2V3V8V7V6V5V11V12V13V944444474522521521中国邮路问题每条边上最多重复一次在图G的每个回路上，有重复的边的长度不超过回路总长的一半欧拉图将奇点两两相连，变成偶点Copyrights 2006-powered by nerdpal HITV1V4V10V2V3V8V7V6V5V11V12V13V944444474522521521中国邮路问题在图G的每个回路上，有重复的边的长度不超过回路总长的一半Copyrights 2006-powered by nerdpal HITV1V4V10V2V3V8V7V6V5V11V12V13V944444474522521521中国邮路问题p图的基本概念与模型p树图和图的最小生成树p最短路问题p中国邮递员问题p网络最大流运筹学基础及应用之图与网络分析Copyrights 2006-powered by nerdpal HIT5 网络最大流一 引言在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。而网络系统的最大流问题是图与网络流理论中的最优化问题，它对于解决生产实际问题起着十分重要的作用。Copyrights 2006-powered by nerdpal HIT每条弧旁边的权就是对应的容量(最大通过能力)。要求指定一个产品运输方案，使得从st的货运量最大，这是寻求网络系统的最大流问题，即从发点s到收点t允许通过的最大流量。tv3v2v1v4s1069879552Cij5 网络最大流Copyrights 2006-powered by nerdpal HIT5 网络最大流二基本概念定义设一个加权有向图D(V,A)，在V中指定一个发点s和一个收点t，其他的点叫做中间点。对于D中的弧(vi,vj)A，都有一个权cij 叫做弧的容量。这样的图D称做一个网络系统，简称网络，记做D(V,A,C)。网络D上的流，是指加在弧集合A上的一组负载量,记作f(vi,vj),或fij.若网络上所有的fij=0，称为零流。Copyrights 2006-powered by nerdpal HIT5 网络最大流该图给出了网络上的一个流（运输方案）,每一个弧上的流量 fij 就是运输量，例如fs1=8，fs2=5，f13=4 等等tv3v2v1v4s(8)(1)(4)(8)(5)(9)(5)(4)(0)fijCopyrights 2006-powered by nerdpal HIT5 网络最大流网络系统上流流的特点：(1)发点的总流出量和收点的总流入量必相等；(2)每一个中间点的净流量=0，即流入量-流出量=0；(3)每一条弧上的流量不能超过它的最大通过能力（即容量）。Copyrights 2006-powered by nerdpal HIT5 网络最大流定义网络上的一个流f 称作可行流，若f满足以下条件：（1）容量条件：对于每一个弧（vi,vj）A，有0 fij cij（2）平衡条件：对于发点s，有fsj-fjs=v(f)对于收点 t，有ftj-fjt=-v(f)对于中间点，有fij-fji=0v(f)表示可行流的流量。Copyrights 2006-powered by nerdpal HIT5 网络最大流Copyrights 2006-powered by nerdpal HIT5 网络最大流任意一个网络都存在可行流。如零流v(f)=0v(f)=0,就满足可行流的条件。网络系统中最大流问题就是在给定的网络上寻求一个可行流 f f,其流量 v(f)v(f)达到最大值。设流f=ff=fijij 是网络D上的一个可行流，f fijij=c=cijij的弧称为饱和弧；f fijijc0 0 的弧为非零流弧，f fijij=0=0的弧为零流弧。Copyrights 2006-powered by nerdpal HIT割是指将网络中的发点和收点分割开,并使st的流中断的一组弧的集合.K将网络上的点分割成V和V，sV,tV,称弧集（V,V）=(v1,v3),(v2,v4)是分离s和t的割.注意:弧(v3,v2)即使不割断,从st的流仍然中断.Ktv3v2v1v4s10(8)6(1)9(4)8(8)7(5)9(9)5(5)5(4)2(0)Cij(fij)Copyrights 2006-powered by nerdpal HIT将割中所有弧的容量之和称作割的容量，记作,即Ktv3v2v1v4s10(8)6(1)9(4)8(8)7(5)9(9)5(5)5(4)2(0)Cij(fij)Copyrights 2006-powered by nerdpal HIT5 网络最大流结论:在网络D中,任何一个可行流 f 的流量 v(f)都小于或等于这个网络中任何一个割(V,V)的容量.设是网络D中连接发点 s 和收点 t 的一条链。定义链的方向是从st，于是链上的弧被分为两类：一是弧的方向与链的方向相同，叫做前向弧，记作+;二是弧的方向与链的方向相反，叫做后向弧，记作-.Copyrights 2006-powered by nerdpal HIT饱和弧:(s,v1),(v2,v4),(v3,t);其他的弧都是非饱和弧;(v3,v2)是零流弧.如图，在链（s,v1,v2,v3,v4,t)中，+=(s,v1),(v1,v2),(v4,t),-=(v3,v2),(v4,v3).5 网络最大流tv3v2v1v4s10(8)6(1)9(4)8(8)7(5)9(9)5(5)5(4)2(0)Cij(fij)Copyrights 2006-powered by nerdpal HIT5 网络最大流增广链，如果链满足以下条件：1在弧（vi,vj）+上，有0=fij cij，即+中的每一条弧是非饱和弧。2在弧（vi,vj）-上，有0 fij=cij，即-中的每一条弧是非零流弧。Copyrights 2006-powered by nerdpal HIT5 网络最大流如图，链=（s,v2,v1,v3,v4,t）就是一条增广链。tv3v2v1v4s10(8)6(1)9(4)8(8)7(5)9(9)5(5)5(4)2(0)Cij(fij)Copyrights 2006-powered by nerdpal HITCopyrights 2006-powered by nerdpal HIT5 网络最大流定理1网络中的一个可行流f*是最大流当且仅当不存在关于f*的增广链。定理2在网络中st的最大流量等于最小割的容量。定理1实际上提供了寻求网络系统最大流的方法：如果网络D中有一个可行流f，只要判断网络是否存在关于可行流f 的增广链。如果没有增广链，那么f 一定是最大流。如有增广链，可以按照定理2，不断增大可行流f的流量，最终可以得到一个最大流。