图与网络分析剖析ppt课件.ppt

《图与网络分析剖析ppt课件.ppt》由会员分享，可在线阅读，更多相关《图与网络分析剖析ppt课件.ppt（263页珍藏版）》请在三一办公上搜索。

1、2022/12/25,1,运筹学OPERATIONS RESEARCH,2022/12/25,2, 1图的基本概念与模型, 2树图和图的最小部分树, 3最短路问题, 4网络的最大流,第六章 图与网络分析（图论）,Graph Theory and Network Analysis,2022/12/25,3,图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论、信息论、工程技术、交通运输、经济管理、电子计算机等各项领域。对于科学研究、市场和社会生活中的许多问题，可以用图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论

2、的方法，简便、快捷地加以解决。 随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。,引言,2022/12/25,4,图论起源于一些游戏，最有代表性的是所谓的“七桥问题”，即一笔画问题。 德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如下图所示。,2022/12/25,5,当地的居民热衷于这样一个问题：一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出

3、发地。 大家都没有成功，但不知道为什么。,哥尼斯堡的七桥问题,2022/12/25,6,为了寻找答案，1736年欧拉把陆地缩为一点，把桥作为连接点的边，将这个问题抽象成图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。这就是著名的Euler问题。 欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出。（每个结点关联的边数要均为偶数）。欧拉的论文题目是“依据几何位置的解题方法”，欧拉被公认为图论的创始人。这就是古典图论中的第一个著名问题。,2022/12/25,7,A,C,D,B,简捷表示事物之间的本质联系，归纳事物之间的一

4、般规律。,2022/12/25,8,1857年，英国数学家哈密尔顿发明了一种游戏：给出一个正12面体图形，共有20个顶点表示20个城市，要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次，最后回到原处的周游世界线路（注意：并不要求经过每条边，要求经过每一顶点）。 也称旅行者“环球旅行问题”或哈密尔顿（Hamilton）回路 。,哈密尔顿（Hamilton）回路,2022/12/25,9,环球旅行问题：,2022/12/25,10,2022/12/25,11,2022/12/25,12,2022/12/25,13,2022/12/25,14,2022/12/25,15,2022/12/

5、25,16,2022/12/25,17,2022/12/25,18,2022/12/25,19,2022/12/25,20,2022/12/25,21,2022/12/25,22,2022/12/25,23,2022/12/25,24,2022/12/25,25,2022/12/25,26,2022/12/25,27,环球旅行问题的另一解,2022/12/25,28,注意：欧拉回路：经过边一次，没有说顶点；（顶点没有要求，但可以理解为：顶点可以多次，而且必须经过每一个顶点，因为经过边必须经过顶点）哈密尔顿回路：经过顶点一次，没有说边。（边没有要求，不过可以理解为：边经过一次或者可以不经过）,2

6、022/12/25,29,情侣问题： 已知有M个男士，N个女士。每个男（女）士都对一些女（男）士倾慕，现问在这群人士中如何搭配，使较多的有情人终成眷属。城市交通改善问题： 随着私家车的不断出现，城市交通状况越来越拥挤，虽然城市在不断改善，但堵车现象仍然越来越多，出行难已成为一个社会问题。假设你是该城市的交通局长，在投资最少（或有限）的条件下应采用何种方法使交通状况得到好转。（交通网络不做大的变化）（应从交通瓶颈入手）,另外，这一时期，还有许多，诸如迷宫问题、博弈问题、棋盘上马的行走路线等问题，吸引了许多学者，这些看起来无足轻重的游戏引出了许多有实际意义的新问题，开辟了新的学科。,2022/12

7、/25,30,在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。,例：有六支球队进行足球比赛，我们分别用点v1v6 表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1 队战胜v2 队，v2 队战胜v3队，v3 队战胜v5 队，如此等等。这个胜负情况，可以用下图所示的有向图反映出来。,v3,v1,v2,v4,v6,v5,2022/12/25,31,6.1 图的基本概念与模型,图（graph）是由一些结点或顶点（ nodes or vertices ）以及连接点的边（edges）构成。记做G = V,E ，其中 V 是顶点的集合，E 是边的集

8、合。,一、 基本概念,给图中的点和边赋以具体的含义和权值，我们称这样的图为网络图（赋权图），记作N。,2022/12/25,32,图中的点用 v 表示，边用 e 表示，对每条边可用它所联结的点表示，如图，则有：,e1 = v1 , v1，e2 = v1 , v2或e2= v2 , v1,用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。通常用点表示研究对象,用点与点之间的线表示研究对象之间的特定关系。一般情况下，图中点的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图，工程图等本质上是不同的。, 图G区别于几何

9、学中的图。这里只关心图中有多少个点以及哪些点之间有连线。,V = v1 , v2 , v3 , v4 , v5，,E = e1 , e2 , e3 , e4 , e5 , e6 , e7, e8，,2022/12/25,33,可见图论中的图与几何图、工程图是不一样的。,例如：在一个人群中，对相互认识这个关系我们可以用图来表示。,2022/12/25,34,端点，关联边，相邻,若边 e 可表示为e = vi , vj，称 vi 和 vj 是边 e 的端点(end vertex) ；同时称边 e 为点 vi 和 vj 的关联边(incident edge);若点 vi , vj 与同一条边关联，称

10、点 vi 和 vj 相邻；若边 ei 与 ej 有公共端点，称边 ei 和 ej 相邻,点相邻：同一条边的两个端点称为相邻(adjacent)节点；边相邻：具有共同端点的边称为相邻边,2022/12/25,35,环, 多重边, 简单图,如果边e的两个端点相重，称该边为环(loop) 。如右图中边e1为环。如果两个点之间多于一条，称为多重边(parallel edges) ，如右图中的e4和e5，对无环、无多重边的图称作简单图(simple graph) 。含多重边的图称为多重图。,简单图,多重图,环,多重边,2022/12/25,36,次，奇点，偶点，孤立点,与某个点相关联的边的数目，称为该点

11、的次（或度、线度，degree），记作 d(vi)。次为奇数的点称为奇点(odd), 次为偶数的点称为偶点(even)；次为零的点称为孤立点 (isolated vertex) ；次数为 1 的点称为悬挂点(pendant vertex)，与悬挂点关联的边称为悬挂边。 图中可以只有点，而没有边；而有边必有点,如图：,奇点为 v5 ， v3,偶点为 v1 , v2 , v4 , v6,孤立点为 v6,2022/12/25,37,d(v1)=4,d(v2)=3,悬挂点,孤立点,悬挂边,偶点,奇点,2022/12/25,38,图的基本性质：,定理1 任何图中，顶点次数之和等于所有边数的2倍。,定理2

12、 任何图中，次为奇数的顶点必为偶数个。,证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的2倍。,证明：设V1和V2分别为图G中奇点与偶点的集合。由定理1可得：,2m为偶数，且偶点的次之和 也为偶数，所以 必为偶数，即奇数点的个数必为偶数。,推论：图的各顶点的次的和是偶数。,2022/12/25,39,例：以下各序列能不能是某个简单图的各顶点的次的序列？为什么？（a）7，6，5，4，3，3，2（b）6，6，5，4，3，3，1（c）6，5，5，4，3，2，1（b）1，1，2，3，2,2022/12/25,40,（a）7，6，5，4，3，3，2不能

13、。7个顶点的简单图，每个顶点的次不会超过6；（b）6，6，5，4，3，3，1不能。若有两个次为6的点，则其中的每一个必定都与其余的6个点相邻，因此除这两个为6的点以外的5个点，每个点的次都至少是2，而不会有次为1的点（c）6，5，5，4，3，2，1不能。若去掉次为1的点及其关联边，剩下的图有6个顶点，次的序列为5，5，5，4，3，2，类似上题，是不可能的。（d）1，1，2，3，2不能。各点的次的和为奇数。,2022/12/25,41,链，圈，路，回路，连通图,图中存在点和边的交替序列=v0,e1,v1,e2,ek,vk，点相邻,没有重复的边，只有重复的点 ，称为链(link)，起点和终点重合的

14、链称为圈(loop) ； 特殊的链，链中顶点不相同，边也不相同的交替序列称为路(path)；起点和终点重合的路称为回路(circuit)（此处链的定义即欧拉链；路为哈密尔顿问题）。 任意两点之间至少有一条链相连的图，称为连通图（没有孤立的点、边），否则称该图为不连通的。,链,路,圈,2022/12/25,42,说明： 一般来说，链和路的定义没有此要求（无向图来说，路与链、圈和回路意义相同）。此处链的定义应该叫简单链，即欧拉链；路的定义应该叫初等链，为哈密尔顿问题。,2022/12/25,43,完全图，偶图,一个简单图中若任意两点之间均有边相连，称这样的图为完全图，含有 n 个顶点的完全图，其边

15、数有 条。 如果图的顶点能分成两个互不相交的非空集合 V1 和V2 , 使在同一集合中任意两个顶点均不相邻，称这样的图为偶图（也称二分图），如果偶图的顶点集合V1 和V2 之间的每一对顶点都有一条边相连，称这样的图为完全偶图，完全偶图中V1 含m 个顶点，V2 含有 n 个顶点，则其边数共 m n 条。,2022/12/25,44,二分图（偶图）,图G=(V,E)的点集V可以分为两个非空子集X，Y，集XY=V,XY=,使得同一集合中任意两个顶点均不相邻，称这样的图为二分图（偶图）。,(a),(b),(c),(a)明显为二分图，(b)也是二分图，但不明显，改画为(c)时可以清楚看出。,2022/

16、12/25,45,子图、部分图 设 G1=V1 , E1,G2=V2 ,E2 子图定义：如果 V2 V1 , E2 E1 称 G2 是 G1 的子图，也就是一个图里的部分边和点； 部分图（支撑子图）：如果 V2 = V1 , E2 E1 称 G2 是 G1 的部分图；如果子图与原图中的点相同而边比原图少。（部分图也是子图，但子图不一定是部分图）,2022/12/25,46,G1,G1= V1 , E1 ,2022/12/25,47,G2= V2 ,E2 子图,G2,2022/12/25,48,部分图：V3 = V1 , E3 E1 称 G3 是 G1 的部分图；,G3子图部分图（支撑子图）,G

17、3,2022/12/25,49,G4（部分图）,2022/12/25,50,二、图的模型 对要研究的问题确定具体对象及这些对象间的性质联系并用图的形式表示出来，这就是对研究的问题建立图的模型。,2022/12/25,51,例1 ：有甲,乙,丙,丁,戊,己6名运动员报名参加A,B,C,D,E,F 6个项目的比赛。下表中打的是各运动员报告参加的比赛项目。问6个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。,2022/12/25,52,解：用图来建模。把比赛项目作为研究对象，用点表示。如果2个项目有同一名运动员参加，在代表这两个项目的点之间连一条线，可得下图。,书上例1问题是在图中

18、寻找一条哈密尔顿道路。做图6-3的补图。,2022/12/25,53,在图中找到一个点序列，使得依次排列的两点不相邻，即能满足要求。如：1) A,C,B,F,E,D2) D,E,F,B,C,A,2022/12/25,54,例：一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分人同时选修D、C、A，一部分人同时选修B、C、F，一部分人同时选修B、E，还有一部分人同时选修A、B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。,2022/12/25,55,A,F,E,D,C,B,解：以每门课程为一个顶点，共同被选修的课程之间用

19、边相连，得图。,2022/12/25,56,按题意，相邻顶点对应课程不能连续考试，不相邻顶点对应课程允许连续考试，因此，作图的补图。,2022/12/25,57,A,F,E,D,C,B,2022/12/25,58,A,F,E,D,C,B,2022/12/25,59,A,F,E,D,C,B,问题是在图中寻找一条哈密尔顿道路。,2022/12/25,60,A,F,E,D,C,B,2022/12/25,61,A,F,E,D,C,B,2022/12/25,62,A,F,E,D,C,B,2022/12/25,63,A,F,E,D,C,B,如CEAFDB，就是一个符合要求的考试课程表。,2022/12/2

20、5,64,例：有7个人围桌而坐，如果要求每次相邻的人都与以前完全不同，试问不同的就座方案共有多少种？ 解：用顶点表示人，用边表示两者相邻，因为最初任何两个人都允许相邻，所以任何两点都可以有边相连。,2022/12/25,65,1,2,3,7,6,4,5,2022/12/25,66,假定第一次就座方案是（1，2，3，4，5，6，7，1），那么第二次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。,2022/12/25,67,1,2,3,7,6,4,5,2022/12/25,68,1,2,3,7,6,4,5,2022/12/25,69,1,2,3,7,6,4,5,2022/12/25,

21、70,1,2,3,7,6,4,5,2022/12/25,71,1,2,3,7,6,4,5,2022/12/25,72,1,2,3,7,6,4,5,2022/12/25,73,1,2,3,7,6,4,5,2022/12/25,74,1,2,3,7,6,4,5,2022/12/25,75,假定第二次就座方案是（1，3，5，7，2，4，6，1），那么第三次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。,2022/12/25,76,1,2,3,7,6,4,5,2022/12/25,77,1,2,3,7,6,4,5,2022/12/25,78,1,2,3,7,6,4,5,2022/12/2

22、5,79,1,2,3,7,6,4,5,2022/12/25,80,1,2,3,7,6,4,5,2022/12/25,81,1,2,3,7,6,4,5,2022/12/25,82,1,2,3,7,6,4,5,2022/12/25,83,1,2,3,7,6,4,5,2022/12/25,84,假定第三次就座方案是（1，4，7，3，6，2，5，1），那么第四次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边，只留下7点孤立点，所以该问题只有三个就座方案。,2022/12/25,85,1,2,3,7,6,4,5,2022/12/25,86,1,2,3,7,6,4,5,2022/12/25,8

23、7,1,2,3,7,6,4,5,2022/12/25,88,1,2,3,7,6,4,5,2022/12/25,89,1,2,3,7,6,4,5,2022/12/25,90,1,2,3,7,6,4,5,2022/12/25,91,1,2,3,7,6,4,5,2022/12/25,92,课后习题1-3课后1：这一类求库存最少的问题称为染色问题，一般尚未解决。用图的观点分析实际问题，首先要认定点代表什么，边代表什么。注意一是要恰当反映实际问题，二是要尽量使后面的计算能够简便。思路：8个点代表8种药品，不能放一贮藏室内连一条边如果能在图中找出k个顶点的子图是完全图的话，那么这个子图的k个顶点对应的药品

24、必须每种一室S:ABR:DP:CT,2022/12/25,93,课后2：次、相邻。已知景点与几条边关联；与哪些点相邻思路：A.看图可知，两个景点之间若有路可通（于是他们相邻），则只有一条，这是旅行者往返此两点间的必由之路；B.又注意到不同景点的关联边条数不全相同，这是确定不同景点的相对位置的依据；C.此人从A开始先到的恰是16个不同景点，依次经过的两个景点间连上一条边（表示这两个景点间有一条路相连），即计算这两个点的“次”时，每个点的“次”都加上一个“1”，从17个景点开始，以后到达的景点此前已到达过，故只需在排成一行的16个点中相应两个点的上方或下方，记上相应景点记号，连上一条边来表示相应的

25、道路。次为2的点：AHDE 次为3的点：KOLPIMJN次为4的点：GBCF,2022/12/25,94,2022/12/25,95,课后3：做补图第一天：AE；第二天：CB；第三天：DF。,2022/12/25,96,2树图和图的最小部分树,在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树。 树图：倒置的树，根(root)在上，树叶(leaf)在下。 多级辐射制的电信网络、管理的指标体系、决策树、家谱、分类学、组织结构等都是典型的树图。,树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。,2022/12/25,97,例：乒乓求单打比赛抽签后，可用图来表示

26、相遇情况，如下图所示。,运动员,2022/12/25,98,例：某企业的组织机构图也可用树图表示。,2022/12/25,99,例：已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。 如果用六个点v1v6代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就作成一个图。由于任意两个城市之间均可以通话，这个图必须是连通图。并且，这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。下图是一个不含圈的连通图，代表了一个电话线网。,v6,v3,v4,v2,v5,v1,2022/

27、12/25,100,树图（简称树，记作 T(V, E)）是无圈的连通图。（无圈，无多重边）,一. 树的性质,性质1.任何树中必存在次为1的点。 （没有圈，没有回路）证明：反证法,性质2.具有 n 个顶点的树恰有（n-1）条边。 证明：归纳法,性质3.任何具有n 个点、(n - 1)条边连通图是树。 证明：反证法,2022/12/25,101,以上性质说明： 1.树是边数最多的无圈的连通图，树中只要任意再加一条边，必出现圈。,2.树中任意两点之间有且只有一条通路,以上7个命题都可以作为树的定义,3.从树中任意删掉一条边，就不再连通。（树是最脆弱的连通图）,2022/12/25,102,二. 图的

28、最小部分树（最小支撑树）,如果 G1 是 G2 的部分图，又是树图，则称 G1 是 G2 的部分树（或支撑树）； 树图的各条边称为树枝(假定各边均有权重)； 树枝总长最小的部分树，称为该图的最小部分树(也称最小支撑树)。最小支撑树问题就是赋权图的最优化问题之一。,如前所述，在已知的几个城市之间联结电话线网，要求总长度最短和总建设费用最少，这个问题的解决可以归结为最小支撑树问题。 再如，城市间交通线的建造等，都可以归结为这一类问题。,2022/12/25,103,例如,图b 是图a 的一个支撑树。,v6,v5,v2,v3,v4,v1,v6,v5,v2,v3,v4,v1,a,b,2022/12/2

29、5,104,2022/12/25,105,2022/12/25,106,2022/12/25,107,2022/12/25,108,2022/12/25,109,定理1.图中任一个点 i ，若 j 是与 i 相邻点中距离最近的，则边 i , j 一定包含在该图的最小部分树中。证明：反证法,推论：把图的所有点分成 V 和 两个集合，则两集合之间连线的最短边一定包含在最小部分树内。,2022/12/25,110,三.求最小部分树：避圈法和破圈法,寻找最小部分树的方法主要有避圈法和破圈法两种。,避圈法步骤：,1.从图中任选一点 vi ，让 vi V ，图中其余点均包含在 中；,2.从 V 与 的连线

30、中找出最小边，这条边一定包含在最小部分树中，不妨设这条边为vi , vj将其加粗，标记为最小部分树中的边。,3.令 VvjV， - vj ；,4.重复2、3两步，一直到图中所有点均包含在 V 中。,2022/12/25,111,避圈法,2022/12/25,112,书上方法： 任选一点vi。找出与其相连的最小边，设为vi,vj,找出与vi,vj点相连的最小边，设为vj,vj+1,接下来找出与（ vi,vj，,vj+1）相连的最小边，如果有两个相等的最小边，只要不构成圈都可以选。以此类推，直到所有的点选完为止。 特点：从任一顶点开始,2022/12/25,113,例：分别用两种避圈法构造下图的最

31、小部分树。,第一种解法：,1. 在点集中任选一点，不妨取 S，令 V=S,2. 找到和 S 相邻的边中，权值最小的 S , A 。,2022/12/25,114,3. V=S , A,4. 重复第2，3步，找到下一个点。,2022/12/25,115,首先从图中选一条权最小的边，然后连续从未被选取的边中选一条权最小的边，并使其与已选取的边不构成圈。在此过程中，如果有多条边的权都最小，则全选。当所选的边的数目等于n-1条为止，算法结束，则得到最小树。 特点：从最小权的边开始,避圈法另一种做法：,2022/12/25,116,第二种做法求解过程：,2022/12/25,117,避圈法:原则为：从最

32、短边开始添加，加边的过程中不能形成圈，直到点点连通(即:n-1条边)。,2022/12/25,118,树与图的最小树,v1,v2,v3,v4,v5,v6,4,3,5,2,1,Min C(T)=15,2022/12/25,119,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,避圈法,2022/12/25,120,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,2022/12/25,121,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1

33、,23,36,2022/12/25,122,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,2022/12/25,123,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,2022/12/25,124,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,2022/12/25,125,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,2022/12/25,126,破圈法求解步

34、骤：, 在网络图中寻找一个圈。若不存在圈，则已经得到最小树； 去掉该圈中权数最大的边；（如果有相同的几条边都是权最大的，任去其一）反复重复 两步，直到最小树。特点：从任意一个圈开始,2022/12/25,127,破圈法,2022/12/25,128,部分树,2022/12/25,129,用破圈法求解上例：,1. 任意找到一回路，不妨取 DETD，去掉边权最大的边T ,E ;,2022/12/25,130,2. 从剩余的子图中任找一回路，同样去掉回路中边权最大的一条边，得一新的子图；依次类推。,2022/12/25,131,破圈法：任取一圈，去掉圈中最长边，直到无圈。,v1,v2,v3,v4,v

35、5,v6,4,3,5,2,1,边数n-1=5,2022/12/25,132,得到最小树：,Min C(T)=15,2022/12/25,133,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,2022/12/25,134,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,2022/12/25,135,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,2022/12/25,136,v1,v7,v4,v3,v2,v5,v6,20,15,

36、9,16,25,3,28,17,4,1,23,2022/12/25,137,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,2022/12/25,138,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,2022/12/25,139,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,2022/12/25,140,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,2022/12/25,141,v1,v7,v4,v3,v2,v5,v6,9,3,2

37、8,17,4,1,23,2022/12/25,142,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,2022/12/25,143,v1,v7,v4,v3,v2,v5,v6,9,3,17,4,1,23,2022/12/25,144,v6,v5,v2,v3,v4,图a,v1,6,2,7,5,3,5,4,4,v3,v2,v1,v4,v6,v5,5,1,3,1,4,2,图b,某六个城市之间的道路网如图a所示，要求沿着已知长度的道路联结六个城市的电话线网，使得电话线的总长度最短。,2022/12/25,145,解：这个问题的解决就是要求所示赋权图a中的最小支撑树。用破圈法求

38、解。任取一个圈，例如（ v1,v2,v3,v1 ），去掉这个圈中权最大的边v1,v3。再取一个圈（ v3,v5,v2,v3），去掉边v2,v5。再取一个圈（ v3,v5,v4,v2,v3），去掉边v3,v5。再取一个圈（v5,v6,v4,v5），这个圈中，有两条权最大的边v5,v6和v4,v6。任意去掉其中的一条，例如v5,v6。这时得到一个不含圈的图，如图b所示，即是最小支撑树。,2022/12/25,146,破圈法的另一种解法：,1.从剩余图中找到权最大的一条边，如果将其删除后图仍然是连通的，则删除此边，否则不再考虑此边； 2.重复上述步骤，直到剩余边数为 n-1 为止。,特点：从最大权的

39、边开始,用此法求解上述问题：,2022/12/25,147,注意：,1.一个图的最小部分树不唯一，该题中用几种解法得到的结果都是相同的，是特殊情况；,2.不同解法得到的最小部分树所包含的边虽然可能不相同，但是，每个最小部分树中所有边权的总和一定都是相同的，即都达到了最小。,2022/12/25,148,课堂练习：,Min C(T)=12,Min C(T)=15,答案：,2022/12/25,149,3,4,1,2,2,3,2,3,2,4,2,Min C(T)=12,Min C(T)=18,2022/12/25,150,6.4、做一道，熟悉一下各种方法6.5、最小部分树避圈法破圈法6.6、树是边

40、数比顶点少1，而且无圈的连通图,2022/12/25,151,3最短路问题,如何用最短的线路将三部电话连起来？此问题可抽象为设ABC为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如ABAC）。,A,B,C,2022/12/25,152,最短路问题,A,B,C,P,但若增加一个周转站（新点P），连接4点的新网络的最短路线为PAPBPC。最短新路径之长N比原来只连三点的最短路径O要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。,2022/12/25,153,最短路问题是指从给定的网络图中找出任意两点之间距离最短（权值和最小）的一条路。 最短路

41、问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本工具，可以解决生产实际中的许多问题，比如城市中的管道铺设、线路安排、工厂布局、设备更新、投资、某些整数规划和动态规划等等。,2022/12/25,154,最短路的求法：1.从某一点至其它各点之间最短距离的狄克斯屈拉( Dijksrta )算法；2.求网络图中任意两点之间的最短距离的矩阵算法。,2022/12/25,155,Dijkstra算法（重点内容） 在一个赋权无向图中寻求最短路的方法Dijkstra算法，它是在1959年提出来的。目前公认，在所有的权wij0时，这个算法是寻求最短路问题最好的算法。并且，这个算法实际上也给出了

42、寻求从一个始点vs到任意一个点vj的最短路。,学习方法：第一次完整看一下方法，以后不用这么多理论了，直接在图上算就可以了。,2022/12/25,156,一. Dijkstra 算法,1.设 dij 表示图中两相邻点 i 与 j 的距离，若 i 与 j 不相邻，令 dij =，显然 dii =0。,Dijkstra 算法假设：,基本思路：如果 v1 v2 v3 v4 是 v1 v4 的最短路径，则 v1 v2 v3 一定是 v1 v3 的最短路径。 v2 v3 v4 一定是 v2 v4 的最短路径。,设Lsi 表示从 s 点到 i 点的最短距离。,2022/12/25,157,Dijkstra

43、 算法步骤：,1.对起始点s，因Lss=0，将0标注在s旁的小方框内，表示s点已标号；,2.从点 s 出发，找出与 s 相邻的点中距离最小的一个，设为 r ，将 Lsr = Lss+ dsr 的值标注在 r 旁的小方框内（也即将起点与该点距离标在该点处），表明点 r 也已标号；,3.从已标号的点出发，找出与这些点相邻的所有未标号点p，若有Lsp=minLss+dsp ,Lsr+drp（注意：s、r为已经标号的点，p为未标号点）, 则对p点标号，并将Lsp的值标注在p点旁的小方框内。此步骤也即从所有已经标号的点的所有相邻点中找出Lsp（方框中的值加相邻边的值）最小的一个（注：如果有两个或两个以上

44、相等同为最小的，都标）；,4.重复第 3 步，直到 t 点得到标号为止。,求从起始点 s 到终止点 t 的最短路径。,2022/12/25,158,例. 求下图中从 v1 到 v7 的最短路。,解： (1) 从 v1 点出发，对 v1 点标号，将 L11=0 标注在 旁的小方框内，令 v1V，其余点属于 ；,2022/12/25,159,L1r = min 0+d12 , 0+ d13 =min5,2=2= L13,(2) 同 v1 相邻的未标号点有v2 、 v3 ，,2022/12/25,160,对 v3 标号，将 L13 的值标注在v3 旁的小方框内；,将( v1, v3) 加粗，并令 V

45、v3 V，,。,2022/12/25,161,L1p = min L11+d12 , L13+d34, L13+d36 =min0+5,2+7,2+4 = 5 = L12,(3) 同 v1 , v3 相邻的未标号点有v2 、 v4 、 v6 ，,2022/12/25,162,对 v2 标号，将 L12 的值标注在 v2 旁的小方框内；,将( v1, v2) 加粗，并令 Vv2 V，,2022/12/25,163,L1p = min L12+d25 , L12+d24, L13+d34 ,L13+d36 =min5+7,5+2,2+7,2+4 = 6 = L16,。,(4) 同 v1 , v2

46、,v3 相邻的未标号点有v4 、 v5、 v6 ，,2022/12/25,164,对 v6 标号，将 L16 的值标注在 v6 旁的小方框内；将( v3, v6) 加粗，并令 Vv6 V，,2022/12/25,165,L1p = min L12+d25 , L12+d24, L13+d34 , L16+d64 , L16+d65 , L16+d67 =min5+7, 5+2, 2+7, 6+2, 6+1, 6+6 = 7 = L14 = L15,(5) 同 v1 , v2 ,v3 , v6 相邻的未标号点有v4 、 v5、 v7 ，,2022/12/25,166,对 v4 , v5 同时标号

47、，将 L14 = L15 的值标注在 v4, v5 旁的小方框内；将( v2, v4), ( v6, v5) 加粗，并令Vv4v5V，,2022/12/25,167,L1p = min L15+d57 , L16+d67 =min7+3,6+6=10= L17,(6) 同 v1 , v2 ,v3 , v4, v5, v6 相邻的未标号点只有 v7 ，,2022/12/25,168,对 v7 标号，将 L17 的值标注在 v7 旁的小方框内；将( v5, v7) 加粗。图中绿色线表明从点 v1 到网络中其它各点的最短路，各点旁的数字就是点 v1 到各点的最短距离。,2022/12/25,169,

48、例：求下图v1到各点的最短距离及最短路线。,0,4,5,2,2,3,10,3,9,6,12,6,4,11,6,6,18,8,12,24,8,24,18,2022/12/25,170,v1到各点的最短距离及最短路线如图所示：,0,2,6,18,所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。,2022/12/25,171,例：求v1到v8的最短路,2022/12/25,172,最短路问题,算法适用条件：Dijkstra算法只适用于全部权为非负情况，如果某边上权为负的，算法失效。此时可采用逐次逼近算法。,例：如右图所示中按dijkstra算法可得P(v1)=5为从vsv1

49、的最短路长显然是错误的，从vsv2v1路长只有3。,v2,vs,v1,5,-5,8,2022/12/25,173,二. 求任意两点间最短距离的矩阵算法,用 Dijkstra 算法只能计算从图中某一点到其他点的最短距离，如果要计算各点之间的最短距离就需要对每个点分别计算，而用矩阵算法则可以同时求出所有各点间的最短距离。,思路：vi到vj的最短路可能中间要经过若干个点（若干步）。基本思想是在最短路线上任意两点间路线也是最短路线。利用vi到vj的一步距离求出vi到vj的两步距离，再求出 vi到vj的四步距离、八步距离经有限次迭代可求出vi到vj的最短距离。,2022/12/25,174,解. 设 d

50、ij 表示图中两相邻点 i 与 j 的距离，若 i 与 j 不相邻，令 dij =，显然 dii =0。建立距离矩阵：,例. 利用矩阵算法求上述网络图中各点间的最短距离。,=D（0）,2022/12/25,175,从上述距离矩阵可以看出从 i 点到 j 点的直接距离，但从 i 到 j 的最短距离不一定就是从 i 点直接到 j 点。,如上述问题中，从 v1 v2 的最短距离应该是mind11+d12 , d12+d22 , d13+d32 , d14+d42 , d15+d52 , d16+d62 , d17+d72 ,即 mind1r+dr2。,因此可以构造一个新的矩阵 D(1) ，令 D(1