《管理运筹学 第七章图与网络分析》由会员分享，可在线阅读，更多相关《管理运筹学 第七章图与网络分析（83页珍藏版）》请在金锄头文库上搜索。
1、第七章 图与网络分析,北京物资学院信息学院 2017年5月,北京物资学院运筹学课件,本章主要内容,1 图的基本概念 2 最小树问题 3 最短路问题 4 最大流问题,1 图的基本概念,具体问题的图,抽象问题的图,蛋白质相互作用图,基因相互作用关系图,具体问题的图：城市之间的铁路交通图、地铁线路图、航空线路图等。 抽象问题的图：球队进行比赛的关系图、 一群人的认识关系图、社交网络图、基因调控关系图等,图是反映对象之间关系的一种工具，如果我们把对象用点表示，关系用线表示，就构成了一个图。,关系,对称的关系：甲与乙有这种关系，则乙与甲也有这种关系，如两点之间的距离等。 不对称的关系：甲与乙有这种关系，
2、但乙与甲未必有这种关系：如两个人的认识关系，比赛结果、交通路线中的单行线等。,关系的表示,对称的关系用边表示：e=vi,vj或e=vj,vi 不对称的关系用带箭头的弧表示：a=(vi,vj),图的分类： 无向图：G=(V,E) 有向图：D=(V,A),一般用p 和 q 分别表示一个图中的顶点数和边数,一、无向图中的一些概念,边的端点 e1=v1,v2,称v1,v2 相邻，e是v1及v2 的关联边,环：两个端点相同的边； 多重边：两个端点之间多于一条的边； 简单图：无环、无多重边的图； 多重图：无环、但允许有多重边的图,点次：以v为端点的边的条数，称为v的点次， 记为dG(v)或d(v).（在计
3、算点次时，环算2次） 悬挂点：次为1的点；悬挂边：悬挂点的关联边； 孤立点：次为0的点； 奇点：次为奇数的点；偶点：次为偶数的点。,定理1. 图G=(V,E)中，所有点的次之和是边数的两倍.即,定理2. 任一个图中，奇点的个数是偶数。,证明：设V1和V2分别是G中奇点和偶点的集合，由定理1，有,链：图G=(V,E)中一个点边交替的序列,如果满足,则称之为一条联结vi1和vik的链。,简单图中的链可以简记为,链的起点、中间点、终点,圈：起点和终点重合的链。,简单链（圈）：链（圈）中所含的边均不相同。 初等链（圈）：链（圈）中所含的点均不相同。又称为路（回路）,连通图：任何两个顶点之间至少有一条链
4、的图。 连通分支：不连通图的每一个连通部分图。,子图、支撑子图：图G=(V,E), G=(V,E),若VV，EE，则称G是G的子图；V= V，EE，则称G是G的支撑子图。,割集：设G=(V,E)，SV, T=VS, (S,T)=e|e=vivj, viS, viT 则称(S,T)是G的一个割集。,完全图：一个简单图中若任意两点之间均有边相连，则称之为完全图。 偶图（二分图）：如果一个图的顶点能够分成两个不相交的非空集合V1，V2，使同一集合中任意两点之间均不相邻，则称之为偶图（二分图）。,二、有向图中的一些概念,给定有向图D=(V,A). 基础图：从D中去掉所有弧上的箭头后得到的无向图称为D的
5、基础图，记为G(D). 弧的始点、终点：a=(u,v),u为始点，v为终点。 链：D中的一个点弧交替序列，如果在基础图中对应的是一条链，则称之为D的一条链。（弧可以是逆向的） 路：如果一条链中的所有弧都是正向的，则称为一条路。 回路：起点和终点相同的路称为回路。 （简单路回路）、初等路（回路）可以类似定义。,引例:自来水管道的铺设问题 校门A点(水源); 需要使用自来水的场所共有7个: v1,v2,v7; 问题:为了各个场所都用上自来水,怎样铺设管道才能使挖开的道路数目最少?,共挖开9条路,共挖开6条路,2 最小树问题,树的定义及性质 图的支撑树 最小树问题,树的定义及性质,定义:无圈的连通图
6、称为树.,e1,e2,e4,e3,v4,v1,v5,v3,v2,v6,v7,v8,e5,e6,e7,树的性质： 1.设G是一个树，p(G)2,则G中至少有两个悬挂点。 2.如下三个论断中的两个保证G是树：（1）连通;（2）无圈; （3）q(G)=p(G)-1. 3. G=(V,E)是一个树的充要条件是G中任意两个顶点间有且仅有一条链。 4.从一个树中去掉任意一条边，则余下的图是不连通的。 5.在树中不相邻的两个点间添上一条边，恰好得到一个圈。,e1,e2,e4,e3,v4,v1,v5,v3,v2,v6,v7,v8,e5,e6,e7,图的支撑树,定义：设T=(V,E）是图G=(V,E)的支撑子图
7、，如果T=(V,E)是一个树，则称T是一个支撑树。,图 G,G的一个支撑树,连通图的支撑树满足： （1）支撑性；（2）连通性；（3）无圈性。,2. 求连通图的支撑树的方法：,支撑性 连通性,无圈性,破圈法,支撑性 无圈性,连通性,避圈法,连通性 无圈性,支撑性,反圈法,破圈法,找圈、破圈、直到无圈为止,A,v1,v2,v3,v4,v7,v6,v5,避圈法,（1）由连通图的所有顶点生成一个不含边的子图； （2）加边，但不能生成圈，直到连通为止。,反圈法,把图的顶点分成S和VS两部分，则割集(S,VS)中必有一条边包含在图的支撑树中。,S,VS,思考：假若考虑道路的长度，要求挖开的路面总长度最短，
8、问题该如何解决？,这就是我们接下来要介绍的最小树问题,最小树问题,赋权图:给图G=V,E中的每一条边vi ,vj赋上一个数字wij,称这样的图为赋权图， wij称为边vi ,vj上的权。 权可以表示距离、时间、费用等，通常为非负值。,支撑树的权：如果T=(V,E)是G的一个支撑树，则称E中所有边的权之和为支撑树T的权，记为w(T)。即,上例中支撑树的权为 3+7+5+2+2+3+4=26,最小支撑树：如果支撑树T*的权w(T*)是G的所有支撑树的权中最小者，则称T*是G的最小支撑树（简称最小树）。,最小树问题：求一个赋权图的最小支撑树。,求最小树的方法,1. 破圈法 2. 避圈法（Kruska
9、l算法） 3. 反圈法(Dijkstra算法),破圈法,从赋权图中任取一个圈，去掉圈中权最大的边，直到无圈为止。,A,v1,v2,v3,v4,v7,v6,v5,2,3,7,4,3,5,5,2,4,5,6,2,7,避圈法,Step 1 将赋权图G中的所有边按权从小到大排序； Step 2 取G的所有顶点生成一个不含边的图T； Step 3 将G的边按权从小到大的顺序依次添加到T中，使T中不含圈，直到T成为连通图为止。（对于形成圈的边不添加）,反圈法,定理：把图的顶点分成S和 VS两部分，则割集(S,VS)中权最小的边必包含在图的最小支撑树中。,7,5,2,10,S,VS,Step 1 从图G中任
10、取一点vi, 让viS, 其余各点均包含在S=VS中。 Step 2 从（S,S)中选一条权最小的边e=vivj，加到T中。 Step 3 令S vjS, SvjS，(将所选边的另一个顶点添加到S中）。 Step 4 重复2、3两步，直到图中所有点均包含在S中为止。,课堂练习：1.分别用三种方法求下图的最小支撑树,2,5,4,3,1,7,4,3,4,1,5,7,v1,v2,v3,v4,v5,v6,v7,水源,2. 某农场的水稻田用堤埂分割成很多小块。为了用水灌溉，需要挖开一些堤埂。问最少挖开多少条堤埂，才能使水浇灌到每小块稻田？,作业 P221： 第3题,3 最短路问题,问题的提出 最短路问题
11、的Dijkstra算法 求任意两点之间最短距离的矩阵算法,问题的提出,例1. 已知如图所示交通网络图，边旁的数字表示通过这段路所需要的费用，现某人要从v1出发到v8去，问他该走哪条路线才能花费最少？,该问题就是要在赋权图中所有从v1到v8 的路中，找一条权最小的路。称之为最短路。 其中路的权指路上所有边对应的权之和，又称为路长。,2. 最短路问题的Dijkstra算法,当边(弧)权wij 0 时，目前公认的求最短路的最好算法是由Dijkstra于1959年提出的，称为Dijkstra算法。这个算法事实上可以求出从一个给定的点到任意点的最短路。,算法的基本原理：,问：1.上图中从v1 到v3 的
12、最短路分别是多少？ 2.两图中从v1 到v3 的边权相等，为什么最短路不同？,3. 假若v2 到v3 的边权不知道(如下图)，还能否确定从v1到v3的最短路？,左图无法确定,右图中最短路为从v1直接到v3,路长为8.,例：某人要从甲地到乙地，可以选择的路线共有4条，分别需要经过A、B、C、D四个地方，如下图。假如经过A、B去乙地的路长已知；而从甲地经过C、D到乙地的路长未知，但是从甲到C、D的路长已知，分别为20、45公里，那么能否确定从甲地经过A、B、C、D哪个地方去乙地最近？,很明显，选择经过A到乙地一定是最短的路。因为从C、D到乙地的路长虽然还不知道，但是根据已知条件，可以推断出它们的路
13、长一定比12公里长，所以不会比经过A到乙地短。,算法的实现过程： 从起点出发，逐步向外探寻最短路，直到终点。,探寻最短路的方式：,给顶点标号 （标出从起点到各顶点的最短路及路长） 一旦找到从起点到vi的最短路，我们就给顶点vi标上标号，其中 （a）起点vs的标号为0，0； （b）顶点vi的标号为Lsi，i ，其中Lsi 表示从vs到vi的最短路的路长， i用来说明顶点vi的标号是从哪个顶点得到的（最短路的来源）。,算法的步骤： 1.给始点vs（最短路的起点）标号0，0。 2.确定割并计算相应的指标值： 由所有一个端点已标号另一个端点未标号的边构成割，记为：,对割里的每一条边（vi，vj），按下
14、式计算指标kij值： kij = Lsi+ wij 即kij等于边（vi，vj）中的已标号点vi的标号（Lsi，i）中的Lsi加上边（vi，vj）的权wij。,3 扩大标号范围。 找出当前割中指标值最小的一条边，给该边的未标号点vj标号（kij ,vi）。 4.重复2、3两步，直到终点vt得到标号为止。,v1,v6,v4,v7,v2,v5,v8,v3,7,8,6,7,8,8,7,6,4,2,5,例求例1中v1到v8的最短路,0，0,3,算例：,v1,v6,v4,v7,v2,v5,v8,v3,7,8,6,7,8,8,7,6,4,2,5,0，0,6，v1,3,v1,v6,v4,v7,v2,v5,v
15、8,v3,7,8,6,7,8,8,7,6,4,2,5,0，0,6，v1,7，v1,3,v1,v6,v4,v7,v2,v5,v8,v3,7,8,6,7,8,8,7,6,4,2,5,0，0,6，v1,7，v1,3,8，v1,v1,v6,v4,v7,v2,v5,v8,v3,7,8,6,7,8,8,7,6,4,2,5,0，0,6，v1,7，v1,3,8，v1,12，v4,14，v4,v1,v6,v4,v7,v2,v5,v8,v3,7,8,6,7,8,8,7,6,4,2,5,0，0,6，v1,7，v1,3,8，v1,12，v4,14，v4,14，v5,v1,v6,v4,v7,v2,v5,v8,v3,7,8,6,7,8,8,7,6,4,2,5,0，0,6，v1,7，v1,3,8，v1,12，v4,14，v4,14，v5,19，v
