第6章图与网络分析课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第6章 图与网络分析,图的基本概念与模型,树图和图的最小部分树,最短路问题,网络的最大流,最小费用流,第6章 图与网络分析图的基本概念与模型,1,1.图的基本概念与模型,运筹学中研究的图用来表明一些研究,对象,和这些对象之间的相互,关系,。,用点表示研究对象，用边表示这些对象之间的联系，则图G可以定义为,点,和,边,的集合，记作,G=V，E,如果给图中的点和边赋以具体的含义和权数，如距离、费用等，称为,网络图,。,1.图的基本概念与模型运筹学中研究的图用来表明一些研究对象和,2,端点、关联边、相邻,环、多重边、简单图,次、奇点、偶点、孤立点,链、圈、路、回路、连通图,完全图、偶图,子图、部分图,端点、关联边、相邻,3,【例】,有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F六个项目的比赛。如下表所示，打的是各运动员报名参加的比赛项目。问六个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。,A,B,C,D,E,F,甲,乙,丙,丁,戊,己,A,C,B,E,D,F,【例】有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、,4,2.树图和图的最小部分树,树图是无圈的连通图。,性质1：任何树图中必存在次为1的点；,性质2：具体n个顶点的树图的边数恰好为（n-1）条；,性质3：任何具有n个点、（n-1）条边的连通图是树图。,2.树图和图的最小部分树树图是无圈的连通图。,5,2.树图和图的最小部分树,图的最小部分树,如果G,1,是G,2,的部分树，又是树图，则称G,1,是G,2,的部分树（或支撑树）。,树图的各条边称为树枝，一般图含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树。,定理1：图中任一个点i，若j是与i相邻点中距离最近的，则边i，j一定必含在该图的最小部分树内。,推论：把图的所有点分为V和V两个集合，则两集合之间连线的最短边一定包含在最小部分树内。,2.树图和图的最小部分树图的最小部分树,6,D,E,避圈法,【例】如下图所示，S、A、B、C、D、E、T代表村镇，它们间连线表明村镇间现有道路交通情况，连线旁数字代表道路的长度。现要求沿图中道路架设电线，使上述村镇全部同上电，应如何架设使总的路线长度为最短。,B,S,A,C,T,2,5,4,1,7,5,2,1,3,5,7,4,DE避圈法【例】如下图所示，S、A、B、C、D、E、T代表村,7,D,E,破圈法,【例】如下图所示，S、A、B、C、D、E、T代表村镇，它们间连线表明村镇间现有道路交通情况，连线旁数字代表道路的长度。现要求沿图中道路架设电线，使上述村镇全部同上电，应如何架设使总的路线长度为最短。,B,S,A,C,T,2,5,4,1,7,5,2,1,3,5,7,4,DE破圈法【例】如下图所示，S、A、B、C、D、E、T代表村,8,3.最短路问题,最短路问题一般来说就是,从给定的网络图中找出任意两点之间距离最短的一条路,。这里的距离只是权数的代称，在实际的网络图中，权数可以是时间、费用等。,求解最短路问题有两种算法：,求从某一点至其它各点之间最短距离的,狄克斯屈拉,（Dijkstra）算法；,求网络图上任意两点之间最短距离的,矩阵,算法；,3.最短路问题最短路问题一般来说就是从给定的网络图中找出任,9,狄克斯屈拉算法,5,7,2,2,1,2,6,6,4,3,7,0,L,11,=0,L,1p,=minL,11,+d,12,L,11,+d,13,=min0+5,0+2=2=L,13,L,1p,=minL,11,+d,12,L,13,+d,34,L,13,+d,36,=min0+5,2+7,2+4=5=L,12,L,1p,=minL,12,+d,25,L,12,+d,24,L,13,+d,34,L,13,+d,36,=,=min5+7,5+2,2+7,2+4=6=L,16,2,5,6,狄克斯屈拉算法572212664370L11=0256,10,狄克斯屈拉算法,5,7,2,2,1,2,6,6,4,3,7,0,L,1p,=minL,12,+d,25,L,12,+d,24,L,13,+d,34,L,16,+d,64,L,16,+d,65,L,16,+d,67,=min5+7,5+2,2+7,6+2,6+1,6+6=7=L,14,=L,15,L,1p,=minL,15,+d,57,L,16,+d,67,=min7+3,6+6=10,=L,17,2,5,6,7,7,10,狄克斯屈拉算法572212664370L1p=minL12,11,【练习】,4,6,5,7,1,5,5,2,4,1,6,8,0,4,5,5,9,10,16,【练习】465715524168045591016,12,矩阵算法,5,7,2,2,1,2,6,6,4,3,7,矩阵算法57221266437,13,构造一个新矩阵D,（1）,该矩阵给出了网络中任意两点之间直接到达和包括一个中间点时的最短距离。矩阵D,（1）,中每个元素的计算方式为：,构造一个新矩阵D（1）,该矩阵给出了网络中任意两点之间直接,14,一般有矩阵D,（k）,给出了网络中任意两点之间直接到达，经过一个、两个、,、到（2,k,-1）个中间点时比较得到的最短距离。矩阵D,（k）,中每个元素的计算方式为：,一般有矩阵D（k）给出了网络中任意两点之间直接到达，经过一个,15,【例】某人购买一台摩托车，准备在今后4年内使用。他可在第一年初购买一台新车，连续使用4年，也可于任何一年末换一台新车。已知各年初的新车购置价如下表1。不同役龄车的年使用维护费及年末处理价如下表2。要求确定该人使用摩托车的最优更新策略，使4年内用于购买、更新及使用维护的总费用为最省。单位：万元。,第一年,第二年,第三年,第四年,年初的购置价,2.5,2.6,2.8,3.1,摩托车役龄,01年,12年,23年,34年,年使用维护费,0.3,0.5,0.8,1.2,该役龄年末处理费,2.0,1.6,1.3,1.1,【例】某人购买一台摩托车，准备在今后4年内使用。他可在第一年,16,第一年,第二年,第三年,第四年,年初的购置价,2.5,2.6,2.8,3.1,摩托车役龄,01年,12年,23年,34年,年使用维护费,0.3,0.5,0.8,1.2,该役龄年末处理费,2.0,1.6,1.3,1.1,0.8,0.9,1.1,1.4,1.7,1.8,2,2.8,2.9,4.2,0,0.8,1.7,2.6,3.7,第一年第二年第三年第四年年初的购置价2.52.62.83.1,17,一个邮递员从邮局出发，走遍他负责投递的每一条街道，然后再返回邮局，问应选择什么样的路线，使走的路程为最短。因为这个问题由中国数学工作者提出，故称为,中国邮路问题,。,欧拉回路,的定义是：连通图G中，若存在一条回路，经过每边一次且仅一次，称这条回路为欧拉回路。称具有欧拉回路的图为欧拉图。,【例】,设某邮递员负责投递的街道如图所示，要求找出该邮递员的最短投递路线。,4,4,5,7,5,4,1,2,4,5,4,2,1,4,4,2,2,一个邮递员从邮局出发，走遍他负责投递的每一条街道，然后再返回,18,连通图G是欧拉图的充分必要条件是图中的点全为,偶点,。,（1）每条边上最多重复一次；,（2）在图G的每个回路上，有重复边的长度不超过回路总长的一半。,4,4,5,7,5,4,1,2,4,5,4,2,1,4,4,2,2,连通图G是欧拉图的充分必要条件是图中的点全为偶点。44575,19,4.网络最大流,网络最大流的有关概念,有向图与容量网络,有向图上的连线是有规定指向的，称作,弧,；,所谓容量网络是指对网络上的每条弧都给出一个最大的通过能力，称为该,弧的容量,，记为c(v,i,v,j,)或简写c,ij,；,在容量网络中通常规定一个,发点,（记为s）和一个,收点,（记为t），网络中既非发点又非收点的其它点称为中间点；,网络最大流,是指网络中从发点到收点之间允许通过的最大流量。,4.网络最大流网络最大流的有关概念,20,4.网络最大流,流与可行流,所谓,流,是指加在网络各条弧上的一组负载量，记作f(v,i,v,j,)或简写为f,ij,；,若网络上所有的f,ij,=0，这个流称为,零流,；,在容量网络上满足以下条件的一组流称为可行流：,容量限制条件，对所有弧有,中间点平衡条件,4.网络最大流流与可行流,21,4.网络最大流,割和流量,割是指将容量网络中的发点和收点分割开，并使st的流中断的一组弧的集合。,割的容量是组成它的集合中的各弧的容量之和。,9(4),9(9),8(8),7(5),5(4),2(0),6(1),5(5),10(8),4.网络最大流割和流量9(4)9(9)8(8)7(5)5(,22,9(4),9(9),8(8),7(5),5(4),2(0),6(1),5(5),10(8),V,V,割,容量,9(4)9(9)8(8)7(5)5(4)2(0)6(1)5(,23,4.网络最大流,最大流最小割定理,如果在网络的发点和收点之间能找到一条链，在这条链上所有指向为st的弧（称为,前向弧,，记作,+,），存在f0，这样的链称为,增广链,。,4.网络最大流最大流最小割定理,24,4.网络最大流,最大流最小割定理,当增广链存在时，找出,再令,定理：,在网络中st的最大流量等于它的最小割集的容量,。,4.网络最大流最大流最小割定理,25,4.网络最大流,Ford-Fulkerson标号算法,首先给发点s标号 。括弧中的第一个数字是使这个点得到标号的前一个点的代号；括弧中的第二个数字表示从上一个标号到这个标号点的流量的最大允许调整值。,列出与已标号点相邻的所有未标号点：,考虑从已标号点i出发的弧（i，j）：,j点不标号,j点标号,4.网络最大流Ford-Fulkerson标号算法j点不标,26,列出与已标号点相邻的所有未标号点：,考虑所有指向已标号点i的弧（h，i）：,如果某未标号点k有两个以上相邻的标号点，为减少迭代次数，可按I、II中所述规则分别计算出 的值，并取其中最大的一个标记。,重复第2步，可能出现两种结局：,标号过程中断，t得不到标号，说明网络中不存在增广链，给定的流量即为最大流。记已标号点的集合为V,未标号点集合为V，（V，V）为网络的最小割；,t点得到标号，反向追踪找出增广链；,h点不标号,h点标号,列出与已标号点相邻的所有未标号点：h点不标号h点标号,27,修改流量，设图中原有可行流为f，按一下方式获得新的可行流f：,抹掉图中所有标号，重复第1到第4步，直至图中找不到任何增广链，即出现第3步的结局I为止，这时网络图中的流量即为最大流。,修改流量，设图中原有可行流为f，按一下方式获得新的可行流f,28,9(4),9(9),8(8),7(5),5(4),2(0),6(1),5(5),10(8),9(4),9(9),8(8),7(5),5(4),2(0),6(1),5(5),10(8),7(,6,),5(,3,),9(,5,),6(,0,),10(,9,),最小割,最大流：14,9(4)9(9)8(8)7(5)5(4)2(0)6(1)5(,29,5(5),6(4),3(3),5(4),2(0),3(3),3(2),4(4),2(2),2(0),8(6),6(6),5(5),6(,5,),3(3),5(,5,),2(0),3(,2,),3(,3,),4(4),2(,1,),2(0),8(,7,),6(6),最小割,最大流：13,5(5)6(4)3(3)5(4)2(0)3(3)3(2)4(,30,D,B,C,E,A,F,1,2,3,4,5,6,7,8,9,10,11,12,13,【例】某河流中有4个岛屿，从两岸至各岛屿及各岛屿之间的桥梁编号如图所示，在一次敌对的军事行动中，问至少应炸断哪几座桥梁，才能完全切断两岸的交通联系？,DBCEAF12345678910111213【例】某河流中,31,D,B,