《运筹学第八章图与网络分析》由会员分享，可在线阅读，更多相关《运筹学第八章图与网络分析（48页珍藏版）》请在金锄头文库上搜索。
1、第八章 图与网络分析,主要内容： 8.1 图与网络的基本知识,8.2 最短路问题,8.3 最大流问题,8.4 最小费用流问题,8.1 图与网络基本知识,一、引言 1。产生 哥尼斯堡七桥难题,例8-1：哥尼斯堡七桥问题,哥尼斯堡（现名加里宁格勒）是欧洲一个城市，Pregei河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如A）出发，经过各桥一次且仅一次最后回到原地呢？,数学家Euler在1736年解决：,8.1 图与网络基本知识,二、图与网络的基本概念,8.1 图与网络基本知识,图论是专门研究图的理论的一门数学分支，主要研究点
2、和线之间的 几何关系。,图论是离散数学的范畴。,8.1 图与网络基本知识,一、图的有关概念,表示为： G=（V，E） V-点集合 E-边集合,简称图，由点和边组成。,无向图：,带箭头的联线，表示不对称关系。,弧：,不带箭头的联线，表示对称关系。,边：,反映对象之间关系的一种工具。,图：,表示两个对象之间的某种特定关系。,连线：,表示研究对象。,点：,8.1 图与网络基本知识,二、无向图的有关概念：,无环，允许有多重边的图。,多重图：,无环，无多重边的图。,简单图：,两点之间多于一条边。,多重边：,若u=v， e是环。,环：,e是点u，v的关联边。,关联边：,e=u,vE， 则u,v是e的端点，
3、称u,v相邻。,端点：,8.1 图与网络基本知识,二、无向图的有关概念：,次为偶数的点。,偶点：,次为奇数的点。,奇点：,次为0的点。,孤立点：,悬挂点的关联边。,悬挂边：,次为1的点。,悬挂点：,例: 如图示 d(v1)=4，d(v4)=4,以点v为端点的边数称为v的次。表示为： d(v),次：,8.1 图与网络基本知识,二、无向图的有关概念,定理8-2：在任意一个图中，奇顶点的个数必为偶数。,定理8-1：在一个图中，所有顶点次的和等于边的两倍。,圈中边均不相同。,简单圈：,链中边均不相同。,简单链：,圈中无重复的点和边。,初等圈：,链中无重复的点和边。,初等链：,如一条链中起点和终点重合。
4、,圈：,点边交错序列。,链：,8.1 图与网络基本知识,二、无向图的有关概念：,图G去掉点v及v的关联边的图。,G-v：,对G=（V，E）， 若G=(V，E), 使V=V，E是E的子集，则G是G的一个支撑子图。,支撑子图：,对不连通图，每一连通的部分称为一个连通分图。,连通分图：,任意两点之间至少有一条链。,连通图：,例8-2：有7个人围桌而坐，如果要求每次相邻的人都与以前完全不同，试问不同的就座方案共有多少种？,8.1 图与网络基本知识,提示：用顶点表示人，用边表示两者相邻。共有3种方案。,8.1 图与网络基本知识,三、有向图的有关概念:,有多重弧。,多重有向图：,无自环，无多重弧。,简单有
5、向图：,圈中无重复的点和弧。,初等圈（回路）：,链中无重复的点和弧。,初等链（道路）：,如一条链中起点和终点重合。,圈（回路）：,点弧交错序列。,链（道路）：,对弧a=(u，v)， u为a的始点，v为a的终点。,始点和终点：,由点和弧组成。表示为：D=（V，A） V-点集合 A-弧集合,有向图：,树：一个无圈的无向连通图称为树。如果一个无圈的图中每一个分支都是树，则称图为森林。,8.1 图与网络基本知识,四、 树的概念,树的性质： 在图中任意两点之间必有一条而且只有一条通路。,2）在图中划去一条边，则图不连通。,3）在图中不相邻的两个顶点之间加一条边，可得一个且仅得一个圈。,4）图中边数为：p
6、-1（p为顶点数）,例8-4：一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分人同时选修D、C、A，一部分人同时选修B、C、F，一部分人同时选修B、E，还有一部分人同时选修A、B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。,8.1 图与网络基本知识,解：以每门课程为一个顶点，共同被选修的课程之间用边相连，得图，按题意，相邻顶点对应课程不能连续考试，不相邻顶点对应课程允许连续考试，因此，作图的补图，问题是在图中寻找一条哈密顿道路，如CEAFDB，就是一个符合要求的考试课程表。,8.1 图与网络基本知识,8.1 图与网
7、络基本知识,四、 树的概念,图的支撑树（生成树）： 1）定义:设图T=(V，E) 是图G=(V,E)的支撑子图,如果T是一个树, 则称T是G的一个支撑树。,最优树（最小生成树、最小支撑树）： 在赋权图G中，一棵生成树所有树枝上权的总和，称为生成树的权。具有最小权的生成树，称为最优树（或最小树）。,2）定理5：图G=（V，E）有支撑树的充分必要条件是G是连通的。,四、 树的概念 求最小生成树的方法有破圈法和避圈法。,8.1 图与网络基本知识,五、欧拉回路与中国邮递员问题,8.1 图与网络基本知识,一笔划问题 欧拉链（道路）： 图中存在一条链，过每边一次且仅一次。 欧拉圈（回路）：图中存在一简单圈
8、， 过每边一次且仅一次。 欧拉图：具有欧拉圈的图。,一笔划问题,8.1 图与网络基本知识,定理：连通多重图G是欧拉图，当且仅当G中无奇点 。 推论： 连通多重图G有欧拉链，当且仅当G恰有两个奇点。,五、欧拉回路与中国邮递员问题,例8-3：哈密尔顿（Hamilton）回路是英国数学家哈密尔顿1857年提出。给出一个正12面体图形，共有20个顶点表示20个城市，要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次，最后回到原处的周游世界线路（并不要求经过每条边）。,8.1 图与网络基本知识,8.1 图与网络基本知识,中国邮递员问题,五、欧拉回路与中国邮递员问题,一个邮递员，负责某一地区的信
9、件投递。他每天要从邮局出发，走遍该地区所有的街道再返回邮局，问应如何安排送信的路线可以使所走的总路程最短？,8.1 图与网络基本知识,中国邮递员问题 奇偶点作业法：若图中无奇点，问题已解决；,五、欧拉回路与中国邮递员问题,否则： 1）第一可行方案的确定： 奇点配对，找奇点间的一条链。,3）最优性判定：满足a)和b)两条。,8.1 图与网络基本知识,中国邮递员问题,2）调整可行方案，使重复边总长度下降。,a)最优方案中， 每一边上最多有一条重复边。,b)最优方案中，每个圈上重复边的总权不大于圈总权的一半。,8.2 最短路问题,三种算法求解三类最短路问题：（1）Dijkstra算法：求无负权网络最
10、短路问题；,（2）逐步逼近算法：求带负权网络最短路问题；,（3）Floyd算法：求网络上任意两点间的最短路问题。,8.2 最短路问题,一、Dijkstra算法：求无负权网络最短路问题。,采用标号法： P标号和T标号(Permanent and Tentative Label),P标号：已确定出最短路的节点(永久性标号)。,T标号：未确定出最短路的节点，表示其距离的上限 （试探性标号）。,算法的每一步都把某一点的T标号改为P标号直至改完为止。,v4,8.2 最短路问题,一、 Dijkstra算法,8.2 最短路问题,一、 Dijkstra算法,解：（1）P(V1)=0 T(Vi)=+ (i=2,
11、3,8),（2） 考察V1V2和V1V3两边：,T(V2)=minT(V2),P(V1)+l12=min+,0+4 =4,T(V3)=minT(V3),P(V1)+l13=min+,0+6 =6,比较所有T标号，T(V2)最小，有P(V2)=4。并记录路径(V1,V2)。,（3） 考察V2V4和V2V5两边：,T(V4)=minT(V4),P(V2)+l24=min+,4+5 =9,T(V5)=minT(V5),P(V2)+l25=min+,4+4 =8,比较所有T标号，T(V3)最小，有P(V3)=6。并记录路径(V1,V3)。,8.2 最短路问题,一、 Dijkstra算法,（4） 考察V
12、3V4和V3V5两边：,T(V4)=minT(V4),P(V3)+l34=min9,6+4 =9,T(V5)=minT(V5),P(V3)+l35=min8,6+7 =8,比较所有T标号，T(V5)最小，有P(V5)=8。并记录路径(V2,V5)。,（3） 考察V5V6和V5V7两边：,T(V6)=minT(V6),P(V5)+l56=min+,8+5 =13,T(V7)=minT(V7),P(V5)+l57=min+,8+6 =14,比较所有T标号，T(V4)最小，有P(V4)=9。并记录路径(V2,V4)。,依此类推，一直计算到（8） （8）考察V8点，只有一个T标号，T(V8)=15，令
13、P(V8)=15)，记录路径（V7，V8），计算结束。,反推得最V1至V8的最短路为V1V2 V5 V7 V8,路长15。,8.2 最短路问题,一、Dijkstra算法：求无负权网络最短路问题。,计算步骤：,（1）给Vs以P标号，P（Vs）=0，其余各点给T标号，T（Vi）=+；,（2）若Vi点为刚得到P标号的点，考虑点Vj: (Vi,Vj)属于E，且Vj为T标号。则修改T(Vj)T(Vj)=minT(Vj),P(Vi)+lij；,（3）比较所有T标号的点，把最小者改为P标号，即：P（Vi）=minT(Vi) 当存在两个以上最小者时，可同时改为P标号。,二、逐次逼近法 基本思想：令P1j表示从
14、v1到vj的最短路长，P1i为v1到vi的最短路长，则必有下列方程： P1j=min(P1i+lij),8.2 最短路问题,i,8.2 最短路问题,例：求图示中V1点到各点的最短路。,8.2 最短路问题,解：初始条件为： P11(1)=0， P12(1)=2， P13(1)=5， P14(1)=-3， P15(1)=P16(1)= P17(1)= P18(1)= ,第一轮迭代： P11(2)=minP11(1) +l11 ，P12(1) +l21 ， P13(1) +l31 ， P14(1) +l41 ， P15(1) +l51 ，P16(1) +l61 ，P17(1) +l71， P18(1
15、) +l81 =0,求解：见Excel表格求解。,P12(2)=minP11(1) +l12 ，P12(1) +l22 ， P13(1) +l32 ， P14(1) +l42 ， P15(1) +l52 ，P16(1) +l62 ，P17(1) +l72， P18(1) +l82 =2,依此类推。,8.2 最短路问题,10,10,10,15,M,M,0,-1,M,3,M,M,M,M,V8,9,9,14,M,M,M,M,0,2,M,7,M,M,M,V7,6,6,6,6,11,M,4,M,0,-3,M,M,M,M,V6,3,3,3,6,6,M,M,M,M,0,M,M,M,M,V5,-3,-3,-3,-3,-3,-3,M,M,M,M,0,4,M,M,V4,0,0,0,0,0,5,M,M,6,M,M,0,M,M,V3,2,2,2,2,2,2,M,M,M,4,M,-2,0,M,V2,0,0,0,0,0,0,M,M,M,M,-3,5,2,0,V1,V8,V7,V6,V5,V4,V3,V2,V1,P(6)1j,P(5)1j,P(4)1j,P(3)1j,P(2)1j,P(1)1j,lij,j i,8.2 最短路问题,三、Floyd算法,算法功能：求网络上任意两点间的最短路。,算法步骤：,（1）令网络的权矩阵为D=(dij)nn，lij为Vi到Vj的距离。,
