Chap图与网络分析实用

Copyrights 2006-powered by nerdpal HIT最短路问题:从给定的网络图中找出某一点到其它点的最短距离公认的求最短路径问题的较好的算法是由E.W.Dijkstra(狄克斯屈拉)于1959年给出的标号法最短路问题第1页/共45页Copyrights 2006-powered by nerdpal HITV1V5V6V2V3V75727241360226V4Dijkstra标号法第3页/共45页Copyrights 2006-powered by nerdpal HITV1V5V6V2V3V75727241360226V45Dijkstra标号法第4页/共45页Copyrights 2006-powered by nerdpal HITV1V5V6V2V3V75727241360226V456Dijkstra标号法第5页/共45页Copyrights 2006-powered by nerdpal HITV1V5V6V2V3V75727241360226V45677Dijkstra标号法第6页/共45页Copyrights 2006-powered by nerdpal HITV1V5V6V2V3V75727241360226V4567710Dijkstra标号法第7页/共45页Copyrights 2006-powered by nerdpal HIT2V1V5V6V2V3V7577241360226V4Dijkstra标号法有向图第9页/共45页Copyrights 2006-powered by nerdpal HIT2V1V5V6V2V3V7577241360226V45Dijkstra标号法有向图第10页/共45页Copyrights 2006-powered by nerdpal HIT2V1V5V6V2V3V7577241360226V459Dijkstra标号法有向图第11页/共45页Copyrights 2006-powered by nerdpal HIT2V1V5V6V2V3V7577241360226V45119Dijkstra标号法有向图第12页/共45页Copyrights 2006-powered by nerdpal HIT2V1V5V6V2V3V7577241360226V4511129Dijkstra标号法有向图第13页/共45页Copyrights 2006-powered by nerdpal HIT2V1V5V6V2V3V7577241360226V451112915Dijkstra标号法有向图第14页/共45页Copyrights 2006-powered by nerdpal HIT最短路问题的数学模型第15页/共45页p图的基本概念与模型p树图和图的最小生成树p最短路问题p中国邮递员问题p网络最大流运筹学基础及应用之图与网络分析第16页/共45页Copyrights 2006-powered by nerdpal HIT一个邮递员从邮局出发，走遍他负责投递的每一条街道，然后再返回邮局，问应选择什么样的路线，使走的路程最短？V1V4V10V2V3V8V7V6V5V11V12V13V944444474522521521中国邮路问题类似于欧拉回路欧拉回路第17页/共45页Copyrights 2006-powered by nerdpal HITKonigsberg七桥问题欧拉回路欧拉图ACBDABCD第18页/共45页Copyrights 2006-powered by nerdpal HITa)是欧拉图；b)不是欧拉图，但存在欧拉回路；c)即不是欧拉图，也不存在欧拉回路。例(a)(b)(b)(c)(c)第19页/共45页Copyrights 2006-powered by nerdpal HITV1V4V10V2V3V8V7V6V5V11V12V13V944444474522521521中国邮路问题每条边上最多重复一次在图G的每个回路上，有重复的边的长度不超过回路总长的一半欧拉图将奇点两两相连，变成偶点第20页/共45页Copyrights 2006-powered by nerdpal HITV1V4V10V2V3V8V7V6V5V11V12V13V944444474522521521中国邮路问题在图G的每个回路上，有重复的边的长度不超过回路总长的一半第21页/共45页Copyrights 2006-powered by nerdpal HITV1V4V10V2V3V8V7V6V5V11V12V13V944444474522521521中国邮路问题第22页/共45页p图的基本概念与模型p树图和图的最小生成树p最短路问题p中国邮递员问题p网络最大流运筹学基础及应用之图与网络分析第23页/共45页Copyrights 2006-powered by nerdpal HIT5 网络最大流一 引言在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。而网络系统的最大流问题是图与网络流理论中的最优化问题，它对于解决生产实际问题起着十分重要的作用。第24页/共45页Copyrights 2006-powered by nerdpal HIT每条弧旁边的权就是对应的容量(最大通过能力)。要求指定一个产品运输方案，使得从st的货运量最大，这是寻求网络系统的最大流问题，即从发点s到收点t允许通过的最大流量。tv3v2v1v4s1069879552Cij5 网络最大流第25页/共45页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，称为零流。第26页/共45页Copyrights 2006-powered by nerdpal HIT5 网络最大流 该图给出了网络上的一个流（运输方案）,每一个弧上的流量 fij 就是运输量，例如 fs1=8，fs2=5，f13=4 等等tv3v2v1v4s(8)(1)(4)(8)(5)(9)(5)(4)(0)fij第27页/共45页Copyrights 2006-powered by nerdpal HIT5 网络最大流网络系统上流流的特点：(1)发点的总流出量和收点的总流入量必相等；(2)每一个中间点的净流量=0，即流入量-流出量=0；(3)每一条弧上的流量不能超过它的最大通过能力（即容量）。第28页/共45页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)表示可行流的流量。第29页/共45页Copyrights 2006-powered by nerdpal HIT5 网络最大流第30页/共45页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的弧为零流弧。第31页/共45页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)第32页/共45页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)第33页/共45页Copyrights 2006-powered by nerdpal HIT5 网络最大流结论:在网络D中,任何一个可行流 f 的流量 v(f)都小于或等于这个网络中任何一个割(V,V)的容量.设是网络D中连接发点 s 和收点 t 的一条链。定义链的方向是从st，于是链上的弧被分为两类：一是弧的方向与链的方向相同，叫做前向弧，记作+;二是弧的方向与链的方向相反，叫做后向弧，记作-.第34页/共45页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)第35页/共45页Copyrights 2006-powered by nerdpal HIT5 网络最大流增广链，如果链满足以下条件：1在弧（vi,vj）+上，有 0=fij cij，即+中的每一条弧是非饱和弧。2在弧（vi,vj）-上，有 0 fij=cij，即-中的每一条弧是非零流弧。第36页/共45页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)第37页/共45页Copyrights 2006-powered by nerdpal HIT第38页/共45页Copyrights 2006-powered by nerdpal HIT5 网络最大流定理1 网络中的一个可行流 f*是最大流当且仅 当不存在关于 f*的增广链。定理2 在网络中 st 的最大流量等于最小割的容量。定理1实际上提供了寻求网络系统最大流的方法：如果网络D中有一个可行流 f，只要判断网络是否存在关于可行流 f 的增广链。如果没有增广链，那么 f 一定是最大流。如有增广链，可以按照定理2，不断增大可行流f的流量，最终可以得到一个最大流。第39页/共45页Copyrights 2006-powered by nerdpal HIT感谢您的欣赏！第45页/共45页