1、第八章 图与网络分析主要内容：8.1 图与网络的基本知识8.2 最短路问题8.3 最大流问题8.4 最小费用流问题8.1 图与网络基本知识一、引言1。产生哥尼斯堡七桥难题哥尼斯堡（现名加里宁格勒）是欧洲一个城市，Pregei河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如A）出发，经过各桥一次且仅一次最后回到原地呢？数学家Euler在1736年解决：8.1 图与网络基本知识二、图与网络的基本概念8.1 图与网络基本知识图论是专门研究图的理论的一门数学分支，主要研究点和线之间的 几何关系。图论是离散数学的范畴。8.1 图与网
2、络基本知识一、图的有关概念表示为： G=（V，E） V-点集合 E-边集合简称图，由点和边组成。l无向图：带箭头的联线，表示不对称关系。l弧：不带箭头的联线，表示对称关系。l边：反映对象之间关系的一种工具。l图：表示两个对象之间的某种特定关系。l连线：表示研究对象。l点：8.1 图与网络基本知识二、无向图的有关概念：有多重边的图。l 多重图：无环，无多重边的图。l 简单图：两点之间多于一条边。l 多重边：若u=v， e是环。l 环： e是点u，v的关联边。l 关联边：e=u,vE， 则u,v是e的端点，称u,v相邻。l 端点：8.1 图与网络基本知识二、无向图的有关概念：V1v2v3v4e1e
3、2e5e4e6e3 次为偶数的点。 l 偶点：次为奇数的点。 l 奇点： 次为0的点。 l 孤立点： 悬挂点的关联边。 l 悬挂边：次为1的点。 l 悬挂点： 例: 如图示 d(v1)=4，d(v4)=4 以点v为端点的边数称为v的次。表示为： d(v) l 次：8.1 图与网络基本知识二、无向图的有关概念定理8-2：在任意一个图中，奇顶点的个数必为偶数。定理8-1：在一个图中，所有顶点次的和等于边的两倍。圈中边均不相同。 l 简单圈：链中边均不相同。 l 简单链：圈中无重复的点和边。 l 初等圈：链中无重复的点和边。 l 初等链：如一条链中起点和终点重合。 l 圈：点边交错序列。 l 链：8
4、.1 图与网络基本知识二、无向图的有关概念：图G去掉点v及v的关联边的图。 l G-v：对G=（V，E）， 若G=(V，E), 使V=V，E是E的子集，则G是G的一个支撑子图。l 支撑子图：对不连通图，每一连通的部分称为一个连通分图。 l 连通分图：任意两点之间至少有一条链。 l 连通图：例8-2：有7个人围桌而坐，如果要求每次相邻的人都与以前完全不同，试问不同的就座方案共有多少种？8.1 图与网络基本知识提示：用顶点表示人，用边表示两者相邻。共有3种方案。8.1 图与网络基本知识三、有向图的有关概念:有多重弧。 l 多重有向图：无自环，无多重弧。 l 简单有向图：圈中无重复的点和弧。 l 初
5、等圈（回路）：链中无重复的点和弧。 l 初等链（道路）：如一条链中起点和终点重合。 l 圈（回路）：点弧交错序列。 l 链（道路）：对弧a=(u，v)， u为a的始点，v为a的终点。 l 始点和终点：由点和弧组成。表示为：D=（V，A） V-点集合 A-弧集合 l 有向图：树：一个无圈的无向连通图称为树。如果一个无圈的图中每一个分支都是树，则称图为森林。8.1 图与网络基本知识四、 树的概念树的性质：1) 在图中任意两点之间必有一条而且只有一条通路。2）在图中划去一条边，则图不连通。3）在图中不相邻的两个顶点之间加一条边，可得一个且仅得一个圈。4）图中边数为：p-1（p为顶点数）例例8-4：一
6、个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分人同时选修D、C、A，一部分人同时选修B、C、F，一部分人同时选修B、E，还有一部分人同时选修A、B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。8.1 图与网络基本知识解：以每门课程为一个顶点，共同被选修的课程之间用边相连，得图，按题意，相邻顶点对应课程不能连续考试，不相邻顶点对应课程允许连续考试，因此，作图的补图，问题是在图中寻找一条哈密顿道路，如CEAFDB，就是一个符合要求的考试课程表。8.1 图与网络基本知识CBCBCB8.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算法：求无负权网络最短路问题；（2）逐步逼近算法：求带负权网络最短路问题；（3）Floyd算法：求网络上任
10、意两点间的最短路问题。8.2 最短路问题一、Dijkstra算法：求无负权网络最短路问题。采用标号法： P标号和T标号(Permanent and Tentative Label)P标号标号：已确定出最短路的节点(永久性标号)。T标号标号：未确定出最短路的节点，表示其距离的上限（试探性标号）。算法的每一步都把某一点的T标号改为P标号直至改完为止。v4v1v2v3v5v6v7v864744565791548.2 最短路问题一、 Dijkstra算法v4v1v2v3v5v6v7v864744565791548.2 最短路问题一、 Dijkstra算法解：（1）P(V1)=0 T(Vi)=+ (i=
11、2,3,8)（2） 考察V1V2和V1V3两边：T(V2)=minT(V2),P(V1)+l12=min+,0+4 =4T(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 =9T(V5)=minT(V5),P(V2)+l25=min+,4+4 =8比较所有T标号，T(V3)最小，有P(V3)=6。并记录路径(V1,V3)。v4v1v2v3v5v6v7v864744565791548.2 最短路问题
12、一、 Dijkstra算法（4） 考察V3V4和V3V5两边：T(V4)=minT(V4),P(V3)+l34=min9,6+4 =9T(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 =13T(V7)=minT(V7),P(V5)+l57=min+,8+6 =14比较所有T标号，T(V4)最小，有P(V4)=9。并记录路径(V2,V4)。依此类推，一直计算到（8）（8）考察V8点，只有一个T标号
13、，T(V8)=15，令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 最短路问题i8.2 最短路问题例：求图示中V1点到各点的最短路。v1v2v3v4v7v8-3274-256-14345-3v5v628.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
15、) +l61 ，P17(1) +l71， P18(1) +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 最短路问题10101015MM0-1M3MMMMV89914MMMM02M7MMMV7666611M4M0-3MMMMV633366MMMM0MMMMV5-3-3-3-3-3-3MMMM04MMV4000005MM6MM0MMV3222222MMM
16、4M-20MV2000000MMMM-3520V1V8V7V6V5V4V3V2V1P(6)1jP(5)1jP(4)1jP(3)1jP(2)1jP(1)1jlij ji8.2 最短路问题三、Floyd算法l 算法功能：求网络上任意两点间的最短路。l 算法步骤：（1）令网络的权矩阵为D=(dij)nn，lij为Vi到Vj的距离。其中：ijijld当(Vi,Vj)E其他（2）输入权矩阵为D(0)=D。（3）计算D(k) =(dij(k)nn (k=1,2,3,n)。其中：,min) 1() 1() 1(kkjkikkijkijdddd三、Floyd算法8.2 最短路问题例13： P267。求解：见手
17、工和Excel。8.3 最大流问题一、基本概念和基本定理1。网络与流定义： 对有向图G=(V，E)：vs 发点，vt 收点，其余 - 中间点c(vi,vj) - 弧(vi，vj)的容量，简写为cijG=(V，A，C) 容量网络fij - 弧(vi，vj)上的流量2。可行流与最大流可行流满足：8.3 最大流问题称为网络流量W有对WfvEvvjtttj),( ：有对WfvEvvsjsjs),( ：ffEvvkiEvvijikji),(),(0有对t；sivi：,；平衡条件：)2 （对cfEvvijijji0 ),容量限制条件：)13。增广链。增广链: 几个概念: 对可行流ijff 8.3 最大流问
18、题m其全体记为后向弧反弧的方向与链的方向相-m其全体记为前向弧致弧的方向与链的方向一-m网络中的一条链 ),.,(tsvv非零流弧 0ijf零流弧 0ijf非饱和弧 ijijcf 饱和弧 ijijcf 8.3 最大流问题 增广链： 设f是一可行流，是从始点到终点的一条链，若满足下列条件，称其为一条增广链。非零流弧对后向弧非饱和弧对前向弧0，则令j=min(fji, i)，并给Vj标号(-Vi, j)。(b) (Vi,Vj) E，且fij0，则令j=min(cij-fij, i)，并给Vj标号(+Vi, j)。l 重复上述标号过程，直到Vt被标号或不再有顶点可标号为止。8.3 最大流问题6。求最
19、大流的标号算法（2）调整过程：ijtijtijffffij令（a）(Vi,Vj)为可增广链上前向边(Vi,Vj)为可增广链上后向边(Vi,Vj)不在可增广链上（b）去掉所有标号，回到第（1）步，重新标号8.4 最小费用流问题最小部分树问题的应用例子 已知有A、B、C、D、E、F六个城镇间的道路网络 如图，现要在六个城镇间架设通讯网络（均沿道路架设），每段道路上的架设费用如图。求能保证各城镇均能通话且总架设费用最少的架设方案。EACBFD51069353978284最短路问题的应用例子 某汽车公司正在制订5年内购买汽车的计划。下面给出一辆新汽车的价格以及一辆汽车的使用维修费用(万元)： 年号 1 2 3 4 5 价格22.12.32.42.6 汽车使用年龄0112233445维修费用0.71.11.522.5试用网络分析中求最短路的方法确定公司可采用的最优策略。方法：以年号作顶点绘图，连线表示连续使用期间，以 费用作路长。最大流问题的应用例子 汽车由A城通往B城的可能的路线如下图所示。环境保护部门拟建立足够数量的汽车尾气检查站，以便使每辆汽车至少必须经过一个检查站。建立检查站的费用根据各路段的条件而有所不同(如图上数字所示)。若求这个问题的最小费用解，可使用 模型。 a. 最短路模型； b.最大流模型； c.最小支撑树模型AacbdefgB824452643367378
