高中奥数专题图论课件

例1最短路问题（SPP－shortestpathproblem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。例2公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？例3运输问题(transportationproblem)某种原材料有N个产地，现在需要将原材料从产地运往M个使用这些原材料的工厂。假定N个产地的产量和M家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？例4中国邮递员问题（CPP－Chinesepostmanproblem）一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。例5旅行商问题（TSP－travelingsalesmanproblem）一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商问题。上述问题有两个共同的特点： 一、它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（optimization）问题； 二、它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（network）。与图和网络相关的最优化问题就是网络最优化或称网络优化（networkoptimization）问题。上面例子中介绍的问题都是网络优化问题。多数网络优化问题是以网络上的流（flow）为研究对象，因此网络优化又常常被称为网络流（networkflows）或网络流规划等。

98年全国大学生数学建模竞赛B题“最佳灾今年(1998年)夏天某县遭受水灾.为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视.巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.情巡视路线”中的前两个问题是这样的：

1）若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线.

2）假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时.要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.公路边的数字为该路段的公里数.

2008年北京奥运会的建设工作已经进入全面设计和实施阶段。奥运会期间，在比赛主场馆的周边地区需要建设由小型商亭构建的临时商业网点，称为迷你超市（MiniSupermarket,以下记做MS）网，以满足观众、游客、工作人员等在奥运会期间的购物需求，主要经营食品、奥运纪念品、旅游用品、文体用品和小日用品等。在比赛主场馆周边地区设置的这种MS，在地点、大小类型和总量方面有三个基本要求：满足奥运会期间的购物需求、分布基本均衡和商业上赢利。2004年A题奥运会临时超市网点设计2004A：奥运会临时超市网点的设计问题题型：属于社会事业问题,主要包括观众的出行、用餐和购物的规律,各商区人流分布规律,以及各商区的大小超市的设计数量等问题。特点：海量数据、数据冗余、结构复杂，即时性、综合性、实用性和开放性强。方法：主题方法数据的处理、统计分析、数据挖掘、数学规划等。结果：不唯一，对结果没有明确要求。1.问题引入与分析2.图论的基本概念3.最短路问题及算法图论模型4.最小生成树及算法5.旅行售货员问题6.模型建立与求解

18世纪东普鲁士哥尼斯堡被普列戈尔河分为四块,它们通过七座桥相互连接,如下图.当时该城的市民热衷于这样一个游戏:“一个散步者怎样才能从某块陆地出发，经每座桥一次且仅一次回到出发点？”ABCD哥尼斯堡七桥示意图七桥问题的分析七桥问题看起来不难，很多人都想试一试，但没有人找到答案。后来有人写信告诉了当时的著名数学家欧拉。千百人的失败使欧拉猜想，也许那样的走法根本不可能。1876年，他证明了自己的猜想。Euler把南北两岸和两个岛抽象成四个点，将连接这些陆地的桥用连接相应两点的一条线来表示，就得到如下一个简图:ABDC欧拉的结论欧拉指出:一个线图中存在通过每边一次仅一次回到出发点的路线的充要条件是:1)图是连通的,即任意两点可由图中的一些边连接起来;2)与图中每一顶点相连的边必须是偶数.由此得出结论:七桥问题无解.

欧拉由七桥问题所引发的研究论文是图论的开篇之作,因此称欧拉为图论之父.ABCDABDC欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地。七桥问题答案的是否定的因为图中没有偶度顶点一笔画问题：欧拉通路或欧拉回路。欧拉图定义

在无向连通简单图中，通过图中每边一次且仅一次并行遍每个结点的一条通路(回路)，称为该图的一条欧拉通路(回路)。存在欧拉回路的图称为欧拉图。无欧拉通路或欧拉回路欧拉通路欧拉回路例下列图是否可以一笔画出来.AB×√√

问题2:哈密顿圈（环球旅行游戏）

十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？哈密顿圈（环球旅行游戏）问题2:哈密顿圈（环球旅行游戏）

十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？哈密顿图定义

经过图中每个结点一次且仅一次的通路(回路)，称为哈密顿通路(回路)。存在哈密顿回路的图称为哈密顿图。哈密顿图哈密顿图无哈密顿通路存在哈密顿通路问题3(关键路径问题):

一项工程任务，大到建造一座大坝，一座体育中心,小至组装一台机床,一架电视机,都要包括许多工序.这些工序相互约束，只有在某些工序完成之后,一个工序才能开始.即它们之间存在完成的先后次序关系，一般认为这些关系是预知的,而且也能够预计完成每个工序所需要的时间.

这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进度的要害工序是哪几个？图的作用图是一种表示工具，改变问题的描述方式,往往是创造性的启发式解决问题的手段.一种描述方式就好比我们站在一个位置和角度观察目标,有的东西被遮挡住了,但如果换一个位置和角度,原来隐藏着的东西就可能被发现.采用一种新的描述方式,可能会产生新思想.图论中的图提供了一种直观,清晰表达已知信息的方式.它有时就像小学数学应用题中的线段图一样,能使我们用语言描述时未显示的或不易观察到的特征、关系,直观地呈现在我们面前,帮助我们分析和思考问题,激发我们的灵感.图的广泛应用图的应用是非常广泛的,在工农业生产、交通运输、通讯和电力领域经常都能看到许多网络,如河道网、灌溉网、管道网、公路网、铁路网、电话线网、计算机通讯网、输电线网等等。还有许多看不见的网络,如各种关系网,像状态转移关系、事物的相互冲突关系、工序的时间先后次序关系等等,这些网络都可以归结为图论的研究对象----图.其中存在大量的网络优化问题需要我们解决.还有象生产计划、投资计划、设备更新等问题也可以转化为网络优化的问题.基本的网络优化问题基本的网络优化问题有:最短路径问题、最小生成树问题、最大流问题和最小费用问题.图论作为数学的一个分支,已经有有效的算法来解决这些问题.当然这当中的有些问题也可以建立线性规划的模型,但有时若变量特别多,约束也特别多,用线性规划的方法求解效率不高甚至不能在可忍受的时间内解决.而根据这些问题的特点,采用网络分析的方法去求解可能会非常有效.例如,在1978年,美国财政部的税务分析部门在对卡特尔税制改革做评估的过程中,就有一个100,000个约束以上,25,000,000个变量的问题,若用普通的线性规划求解,预计要花7个月的时间.他们利用网络分析的方法,将其分解成6个子问题,利用特殊的网络计算机程序,花了大约7个小时问题就得到了解决.

2.图论的基本概念1)图的概念2)赋权图与子图3)图的矩阵表示4)图的顶点度5)路和连通1)图的概念

定义一个图G是指一个二元组(V(G),E(G))，其中:其中元素称为图G的顶点.组成的集合，即称为边集,其中元素称为边.定义图G的阶是指图的顶点数|V(G)|,用来表示；图的边的数目|E(G)|用来表示.也用来表示边是非空有限集，称为顶点集，1)2)E(G)是顶点集V(G)中的无序或有序的元素偶对表示图，简记用

定义

若图G中的边均为有序偶对,称G为有向边为无向边，称e连接和，顶点和称图.称边为有向边或弧,称是从连接的弧若图G中的边均为无序偶对，称G为无向图.称为e的端点.

既有无向边又有有向边的图称为混合图.，称为e的尾，称为e的头.无向图有向图有向图实例─道路图对于一个图G=(V,E),人们常用图形来表示它,称其为图解.凡是有向边,在图解上都用箭头标明其方向.例如,设V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4},则G=(V,E)是一个有4个顶点和6条边的图,G的图解如下图所示.一个图会有许多外形不同的图解,下面两个图表示同一个图G=(V,E)的图解.其中V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4}.今后将不计较这种外形上的差别,而用一个容易理解的、确定的图解去表示一个图.常用术语1)边和它的两端点称为互相关联.2)与同一条边关联的两个端点称为相邻的顶点，与同一个顶点点关联的两条边称为相邻的边.3)端点重合为一点的边称为环，4)若一对顶点之间有两条以上的边联结，则这些边称为重边．5)既没有环也没有重边的图，称为简单图．2)图的顶点度定义

1)在无向图G中，与顶点v关联的边的数目(环算两次),称为顶点v的度或次数，记为d(v)或dG(v).称度为奇数的顶点为奇点，度为偶数的顶点为偶点.2)在有向图中，从顶点v引出的边的数目称为顶点

v的出度，记为d+(v)，从顶点v引入的边的数目称为

v的入度，记为d-(v).称d(v)=d+(v)+d-(v)为顶点v的

度或次数．2)图的顶点度定义

1)在无向图G中，与顶点v关联的边的数目(环算两次),称为顶点v的度或次数，记为d(v)或dG(v).称度为奇数的顶点为奇点，度为偶数的顶点为偶点.2)在有向图中，从顶点v引出的边的数目称为顶点

v的出度，记为d+(v)，从顶点v引入的边的数目称为

v的入度，记为d-(v).称d(v)=d+(v)+d-(v)为顶点v的

度或次数．d(v1)=d(v3)=d(v4)=4,d(v2)=2.2)图的顶点度定义

1)在无向图G中，与顶点v关联的边的数目(环算两次),称为顶点v的度或次数，记为d(v)或dG(v).称度为奇数的顶点为奇点，度为偶数的顶点为偶点.定理推论

任何图中奇点的个数为偶数．图中各点度数之和是边数的2倍

握手定理

2)在有向图中，从顶点v引出的边的数目称为顶点

v的出度，记为d+(v)，从顶点v引入的边的数目称为

v的入度，记为d-(v).称d(v)=d+(v)+d-(v)为顶点v的

度或次数．定理图中各点度数之和是边数的2倍

握手定理

推论

任何图中奇点的个数为偶数．由于所有偶数点的度数之和必然为偶数，所以所有奇点度数之和为偶数，而每个奇点的度数为奇数，所以奇点的个数必然为偶数。

图中的每条边均有两个端点，所以在计算中所有顶点度数之和时，每条边提供度数为2。我们今后只讨论有限简单图：

(1)顶点个数是有限的;(2)任意一条边有且只有两个不同的点与它相互关联;(3)若是无向图，则任意两个顶点最多只有一条边与之相联结;(4)若是有向图，则任意两个顶点最多只有两条边与之相联结。当两个顶点有两条边与之相联结时，这两条边的方向相反。

如果某个有限图不满足(2)(3)(4)，可在某条边上增设顶点使之满足。定理2

连通有向图G含有欧拉回路的充分必要条件是G中每个结点的入度等于出度；连通有向图G含有欧拉通路的充分必要条件是除两个结点外，其余每个结点的入度等于出度，这两个结点中一个结点的入度比其出度多1，另一个结点的入度比其出度少1。3)赋权图与子图

定义若图的每一条边e

都赋以一个实数w(e)，称w(e)为边e的权，G连同边上的权称为赋权图.

定义设和是两个图.若,称是的一个子图,记若，，则称是的生成子图.若，且，以为顶点集，以两端点均在中的边的全体为边集的图的子图，称为的由

导出的子图，记为.若，且，以为边集，以的端点集为顶点集的图的子图，称为的由

导出的

边导出的子图，记为.

3)若，且，以为顶点集，以两端点均在中的边的全体为边集的图的子图，称4)若，且，以为边集，以的端点集为顶点集的图的子图，称为的由导出的边导出的子图，记为.为的由导出的子图，记为.4)图的矩阵表示邻接矩阵:1)对无向图，其邻接矩阵，其中：(以下均假设图为简单图).2)对有向图

,其邻接矩阵,其中：2)对有向图

,其邻接矩阵,其中：其中：3)对有向赋权图

,其邻接矩阵,其中：3)对有向赋权图,其邻接矩阵,对于无向赋权图的邻接矩阵可类似定义.关联矩阵1)对无向图，其关联矩阵,其中：关联关联1)对无向图，其关联矩阵,其中：关联关联无向图的关联矩阵每列的元素中有且仅有两个1.2)对有向图，其关联矩阵,其中：头头2)对有向图，其关联矩阵,其中：头头有向图的关联矩阵每列元素中有且仅有一个1,有且仅有一个-1.5)路和连通定义1)无向图G的一条途径（或通道或链）是指一个有限非空序列，它的项交替地为顶点和边，使得对，的端点是和,称W是从到的一条途径，或一条途径.整数k称为W的长.顶点和分别称为的起点和终点

,而称为W的内部顶点.

2)若途径W的边互不相同但顶点可重复，则称W为迹或简单链.

3)若途径W的顶点和边均互不相同，则称W为路或路径.一条起点为,终点为的路称为路记为定义

1)途径中由相继项构成子序列称为途径W的节.

2)起点与终点重合的途径称为闭途径.

3)起点与终点重合的的路称为圈(或回路)，长为k的圈称为k阶圈，记为Ck.

4)若在图G中存在(u,v)路，则称顶点u和v在图G中连通.

5)若在图G中顶点u和v是连通的，则顶点u和v之之间的距离d(u,v)是指图G中最短(u,v)路的长；若没没有路连接u和v，则定义为无穷大.

6)图G中任意两点皆连通的图称为连通图．

7)对于有向图G，若，且有类似地，可定义有向迹，有向路和有向圈.头和尾，则称W为有向途径.例在右图中：途径或链：迹或简单链：路或路径：圈或回路：用图论思想求解以下各题例、一摆渡人欲将一只狼，一头羊，一篮菜从河西渡过河到河东，由于船小，一次只能带一物过河，并且，狼与羊，羊与菜不能独处，给出渡河方法。解：用四维0-1向量表示（人，狼，羊，菜）的在西岸状态，（在西岸则分量取1，否则取0）共24

=

16种状态，由题设，状态（0,1,1,0）,(0,0,1,1),(0,1,1,1)是不允许的，从而对应状态（1,0,0,1），(1,1,0,0),(1,0,0,0)也是不允许的，例、一摆渡人欲将一只狼，一头羊，一篮菜从河西渡过河到河东，由于船小，一次只能带一物过河，并且，狼与羊，羊与菜不能独处，给出渡河方法。人在河西：（1,1,1,1）（1,1,1,0）（1,1,0,1）（1,0,1,1）（1,0,1,0）（0,1,0,1）（0,1,0,0）（0,0,1,0）（0,0,0,1）（0,0,0,0）人在河东：以十个向量作为顶点，将可能互相转移的状态连线，则得10个顶点的偶图。问题：如何从状态（1,1,1,1）转移到（0,0,0,0）？方法：从（1,1,1,1）开始，沿关联边到达没有到达的相邻顶点，到（0,0,0,0）终止，得到有向图即是。将10个顶点分别记为A1,A2,…,A10,则渡河问题化为在该图中求一条从A1到A10的路.

从图中易得到两条路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10.3．最短路问题及算法最短路问题是图论应用的基本问题，很多实际问题，如线路的布设、运输安排、运输网络最小费用流等问题，都可通过建立最短路问题模型来求解。最短路的定义最短路问题的两种方法：Dijkstra和Floyd算法.求赋权图中从给定点到其余顶点的最短路.求赋权图中任意两点间的最短路.结构程序设计之父第七位图灵奖(1972年)获得者。E.W.Dijkstra1930年5月11日出身于theNetherlands(荷兰)Rotterdam.去世于2002年8月6日于Nuenen,theNetherlands.年轻时代，Dijkstra在UniversityofLeiden,theNetherlands.Leiden大学是荷兰最古老的大学。学习理论物理，但很快他就意识到其兴趣不在于理论物理虽然获得了其数学和理论物理的学位。后来，Dijkstra获得了其博士学位从

UniversityofAmsterdam.1952年-1962年，E.W.Dijkstra是

MaterematischCentrum,Amsterdam的一个程序员。

1962年-1984年，作为一个数学教授任职于

EindhovenUnviersityofTechnology.1984年至1999年，作为计算机系系主任任职与美国UTAustin分校，并于1999年退休。2002年8月6日在荷兰Nuenen自己的家中与世长辞

Dijkstra最短路径算法被广泛的应用在网络协议方面，如OSPF。

EdsgerDijkstra是1950年代ALGOL语言的一个主要贡献者。ALGOL高级编程语言已经成为结构清晰，数学基础严谨的一个典范。E.W.Dijkstra是现代编程语言的主要贡献者之一，为我们理解程序语言的结构，表示方法与实现做出了巨大的贡献。E.W.Dijkstra15年的学术著作覆盖了图论的理论工作，教育手册，解释文章和编程语言领域的哲学思考。在现代编程语言方面，E.W.Dijkstra也以他著名的反对(过分)使用GOTO语句的文章而著名。1968年，E.W.Dijkstra撰写了其“GoToStatementConsideredHarmful”一文。这篇文章被认为是现代编程语言逐渐不鼓励使用GOTO语句，而使用编程控制结构，如whileloop等等的一个分水岭

2)在赋权图G中，从顶点u到顶点v的具有最小权定义1)若H是赋权图G的一个子图，则称H的各边的权和为H的权.类似地，称为路P的权．若P(u,v)是赋权图G中从u到v的路,称的路P*(u,v)，称为u到v的最短路．

3)把赋权图G中一条路的权称为它的长，把(u,v)路的最小权称为u和v之间的距离，并记作d(u,v).

如图所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在一个人要从v1出发，经过这个交通网到达v8，要寻求是总路程最短的线路。1)赋权图中从给定点到其余顶点的最短路636234102312624101v3从v1到v8的路线是很多的。比如从v1出发，经过v2,v5到达v8或者从v1出发，经过v4，v6，v7到达v8等。但不同的路线，经过的总长度是不同的。例如，按照第一个线路，总长度是6+1+6=13单位，按照第二个路线，总长度是1+10+2+4=17单位。v4v2v8v7v6v5v963623410231262410v11v3

一般意义下的最短路问题：设一个赋权有向图D=（V，A），对于每一个弧a=（vi,vj），相应地有一个权wij。vs

，vt

是

D

中的两个顶点，P是D中从vs

到vt

的任意一条路，定义路的权是P中所有弧的权的和，记作S(p)。最短路问题就是要在所有从vs

到

vt的路P

中，寻找一个权最小的路P0，亦即S(P0)

=

min

S(p)。P0叫做从

vs到

vt

的最短路。P0的权S(P0)叫做从vs到vt的距离，记作d（vs，vt）。由于D是有向图，很明显

d（vs，vt）与d（vt，vs）一般不相等。Dijkstra算法

下面介绍在一个赋权有向图中寻求最短路的方法—Dijkstra算法，它是1959年提出来的。目前公认，在所有的权wij

≥0时，这个算法是寻求最短路问题最好的算法。并且，这个算法实际上给出了寻求从一个始定点vs到任意一个点vj的最短路。寻求从一固定起点u0

到其余各点的最短路的最有效算法之一是Dijkstra算法,1959年由Dijkstra提出。这个算法是一种迭代算法,它依据的是一个重要而明显的性质：最短路是一条路，最短路上的任一子段也是最短路。Dijkstra算法的基本思想是：按距v0

从近到远为顺序，依次求得v0

到图G

的各顶点的最短路和距离，直至顶点v0（或直至图G

的所有顶点）。Dijkstra算法的基本思想:

从vs出发，逐步向外寻找最短路。在运算过程中，与每个点对应，记录一个数，叫做一个点的标号。它或者表示从vs到该点的最短路权（叫做P标号），或者表示从vs到该点最短路权的上界（叫做T标号）。算法的每一步是去修改T标号，把某一个具有T标号的点改变为具有P标号的点，使图D中具有P标号的顶点多一个。这样，至多经过P-1步，就可求出从vs到各点vj的最短路。

P(v1)636234102312624101v4v2v6v7v8v9v5v3以例1为例说明这个基本思想。在例1中，S=1。因为wij

≥0，d（v1,v1）=0。这时，v1是具有P标号的点。现在看从v1出发的三条弧（v1,v2）,（v1,v3）,（v1,v4）。如果一个人从

v1

出发沿（v1,v2）到达

v2，路程：d（v1,v1）+w12=6单位。v1如果从v1出发，沿（v1,v3）到达v3，则是d（v1,v1）+w13=3单位。同理，沿（v1,v4）到达v4，是d（v1,v1）+

w14

=

1单位。故他从v1出发到达v4的最短路必是（v1,v4），d（v1,v4）=

1。这是因为从v1到达v4的任一条路，假如是（v1,v4），则必先沿（v1,v2）到达

v2，或者沿（v1,v3）到达

v3，而这时路程已是6或者3单位。P(v1)636234102312624101v4v2v6v7v8v9v5v3v1看从v1出发的三条弧（v1,v2），（v1,v3）,（v1,v4），min{d(v1,v1)+w12,d(v1,v1)+w13,d(v1,v1)+w14}=d（v1,v4）=1。P(v1)63623410231262410v11v4v2v6v7v8v9v5v3由于所有的权

wij

≥0,因此,不论他如何再从v2或者v3

到达

v4，所经过的总路程都不会比1少，于是就有d（v1,v4）=1。这样就使v4变成具有P标号的点。P(v1)636234102312624101v4v6v7v8v9v3v1P(v4)现在看从

v1

和

v4

指向其余点的弧.如上所述，从v1出发，分别沿（v1,v2）,（v1,v3）到达v2,v3，经过的路程是6或者3单位.从v4出发沿（v4,v6）到达v6，经过的路程是d（v1,v4）+w46=1+10=11单位。而min{d（v1,v1）+w12，d（v1,v1）+w13，

d（v1,v4）+w46}=d（v1,v1）+w13=3单位。P(v1)636234102312624101v4v6v7v8v9v3v1P(v4)根据同样的理由，可以断定，从v1到达v3的最短路是（v1,v3），d（v1,v3）=3。这样，又使点v3变为具有P

标号的点，不断重复以上过程，就可以求出从vs到达任一点vj的最短路。P(v1)636234102312624101v4v6v7v8v9v3v1P(v4)P(v3)v4v2v8v7v6v5v963623410231262410P(V6)=10P(V7)=9(V1)=0P(V1)=0P(V4)=1(V4)=1(V6)=5(V5)=2P(V2)=5P(V5)=6P(V8)=12(V7)=5(V2)=3(V8)=5T(V9)=+(V9)=MP(V3)=3(V3)=11最短路：V1-(V4-)V3-V2-V5-(V6-V7-)V8算法步骤：1.给始点vs

以P标号，这表示从vs到vs的最短距离为0，其余节点均给T标号，2.设节点vi

为刚得到P标号的点，考虑点vj，其中，且vj

为T标号。对vj的T标号进行如下修改3.比较所有具有T标号的节点，把最小者改为P标号，即：当存在两个以上最小者时，可同时改为P标号。若全部节点均为P标号，则停止，否则用vk代替vi，返回步骤（2）。237184566134105275934682求从1到8的最短路径237184566134105275934682X={1},w1=

0min{d12,d14,d16}

=

min{0+2,0+1,0+3}=

min{2,1,3}

=

1

X={1,4},p4=1p4=1p1=0237184566134105275934682X={1,4}min{d12,d16,d42,d47}

=

min{0+2,0+3,1+10,1+2}=

min{2,3,11,3}

=

2

X={1,2,4},p2=2p1=0p4=1p2=2237184566134105275934682X={1,2,4}min{d13,d23,d25,d47}=

min{0+3,2+6,2+5,1+2}=

min{3,8,7,3}=3

X={1,2,4,6},p6=3p2=2p4=1p1=0p6=3237184566134105275934682X={1,2,4,6}min{d23,d25,d47,d67}=

min{2+6,2+5,1+2,3+4}=

min{8,7,3,7}=3

X={1,2,4,6,7},p7=3p2=2p4=1p1=0p6=3p7=3237184566134105275934682X={1,2,4,6,7}min{d23,dc25,d75,d78}=

min{2+6,2+5,3+3,3+8}=

min{8,7,6,11}=

6

X={1,2,4,5,6,7},p5=6p2=2p4=1p1=0p6=3p7=3p5=6237184566134105275934682X={1,2,4,6,7}min{d23,d53,d58,d78}=

min{2+6,6+9,6+4,3+8}=

min{8,15,10,11}=

8

X={1,2,3,4,5,6,7},p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8237184566134105275934682X={1,2,3,4,6,7}min{d38,d58,d78}=

min{8+6,6+4,3+7}=

min{14,10,11}

=

10

X={1,2,3,4,5,6,7,8},p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10237184566134105275934682X={1,2,3,4,6,7,8}1到8的最短路径为{1，4，7，5，8}，长度为10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10求从V1

到V8

的最短路线。V1V2V3V4V5V6V7V8①P=0T=+∞T=+∞T=+∞T=+∞T=+∞T=+∞T=+∞②P=T=3T=+∞T=7T=+∞T=+∞T=+∞T=+∞

③T=6T=7P=T=5T=+∞T=+∞T=+∞

④P=T=6T=6

T=8T=+∞T=+∞

⑤P=T=6

T=8T=9T=12

⑥P=T=8T=10T=10

⑦P=T=9T=11再无其它T标号，所以T(V8)=P(V8)=10;minL(μ)=10⑧P=T=10由此看到，此方法不仅求出了从V1

到V8

的最短路长，同时也求出了从V1

到任意一点的最短路长。将从V1

到任一点的最短路权标在图上，即可求出从V1

到任一点的最短路线。本例中V1

到V8

的最短路线是：

v1→v2→v5→v6→v8

∞243523512246421用Dijkstra算法求下图从v1到v6的最短路。

v1v2v3v4v6v5352242421

解

（1）首先给v1以P标号，给其余所有点T标号。（2）（3）（4）v1v2v3v4v6v5352242421（5）（6）（7）（8）（9）（10）反向追踪得v1到v6的最短路为：求下面赋权图中顶点u0到其余顶点的最短路．算法步骤：求所示的图G

中v1

到其余各顶点的最短路及其距离。解：(1)初始标号。i=0。S0={v1}，v1=u0，参见图(a)。(a)(2)用u0=v1

对各顶点的标号进行更新。i=1。={v2,v3,v4,v5,v6}，v，由算法有： l(v2)=min{,0+7}=7， l(v3)=min{,0+4}=4， l(v4)=min{,0+}=， l(v5)=min{,0+}=， l(v6)=min{,0+2}=2。由于v2，v3，v6的标号被v1更新，故这三个顶点的父节点为v1，即z(v2)=z(v3)=z(v6)=v1，参见图(b)，数字边方框中的符号表示父节点。又由于=l(v6)=2，故u1=v6，S1={v1,v6}。参见图(c)。

(b)(c)(3)用u1=v6

对各顶点的标号进行更新。i=2。={v2,v3,v4,v5}，v，由算法有： l(v2)=min{7,2+}=7， l(v3)=min{4,2+1}=3， l(v4)=min{,2+5}=7， l(v5)=min{,2+5}=7。

在此次迭代中，v2的标号不变，v3，v4，v5的标号被v6更新，故v2

的父节点不变，v3，v4，v5的父节点为v6，即z(v2)=v1，z(v3)=z(v4)=z(v5)=v6。参见图(d)。又由于=l(v3)=3，故u2=v3，S2={v1,v6,v3}。参见图(e)。(d)(e)

(4)用u2=v3

对各顶点的标号进行更新。i=3。={v2,v4,v5}，v，由算法有： l(v2)=min{7,3+3}=6， l(v4)=min{7,3+1}=4， l(v5)=min{7,3+}=7。

在此次迭代中，v5

的标号不变，v2

和v4

的标号被v3

更新，故v5

的父节点不变，v2

和v4

的父节点为v3，即z(v5)=v6，z(v2)=z(v4)=v3。参见图(f)。又由于=l(v4)=4，故u3=v4，S3={v1,v6,v3,v4}。参见图(g)。(f)(g)(5)用u3=v4

对各顶点的标号进行更新。i=4。={v2,v5}，v，由算法有： l(v2)=min{6,4+}=6， l(v5)=min{7,4+2}=6。

在此次迭代中，v2

的标号不变，v5标号被v4更新，故v2

的父节点不变，v5

的父节点为v4，即z(v2)=v3，z(v5)=v4。参见图(h)。又由于=l(v5)=6，故u4=v5，S4={v1,v6,v3,v4,v5}。参见图(i)。(h)(i)

(6)用u4=v5

对各顶点的标号进行更新。i=5。={v2}，v={v2}，由算法有：l(v2)=min{6,6+}=6。在此次迭代中，v2

的标号不变，故v2

的父节点不变，即z(v2)=v3。参见图(i)。又由于=l(v2)=6，故u5=v2，S5={v1,v6,v3,v4,v5,v2}。(h)(i)(7)由于i=5=n

1，停止。注：①迭代的终止条件也可使用Sn1={v1,…,vn}，或者=。②若寻找v1

到某点v的最短路的路由，则由v开始追溯父节点直至v1。例如，寻找v1

到v5

的最短路的路由，根据图(i)，从v5

开始追溯父节点：v5

的父节点为v4，v4的父节点为v3，v3

的父节点为v6，v6

的父节点为v1。于是v1

到v5

的最短路为：v1v6v3v4v5。再如，v1

到v2

的最短路为：v1v6v3v2。③若求v1到某点v的距离，则直接由l(v)的终值确定。例如，根据图(i)，由于l(v5)=6，故v1

到v5的距离为6。再如，由于l(v2)=6，故v1

到v2

的距离也为6。

TOMATLAB(road1)

1

2

34

5

6

7

8寻求赋权图中各对顶点之间最短路，显然可以调用Dijkstra算法。具体方法是：每次以不同的顶点作为起点，用Dijkstra算法求出从该起点到其余顶点的最短路径，反复执行次这样的操作，就可得到每对顶点之间的最短路。但这样做需要大量重复计算，效率不高。R.W.Floyd（弗洛伊德）另辟蹊径，提出了比这更好的算法，操作方式与Dijkstra算法截然不同。2)求赋权图中任意两顶点间的最短路算法的基本思想（I）求距离矩阵的方法.（II）求路径矩阵的方法.（III）查找最短路路径的方法

Floyd算法：求任意两顶点间的最短路.举例说明

算法的基本思想

（I）求距离矩阵的方法.D(0)=[dij(0)]nn=A：是带权邻接矩阵，dij(0)

表示从vi

到vj

的、中间不插入任何点的路径，即边vivj

的权值；D(1)=[dij(1)]nn，其中dij(1)=min{dij(0)，di1(0)

d1j(0)}：dij(1)

表示从vi

到vj

的、中间最多只允许v1

作为插入点的路径中最短路的长度；D(2)=[dij(2)]nn，其中dij(2)=min{dij(1)，di2(1)d2j(1)}：dij(2)

表示从vi

到vj

的、中间最多只允许v1

和v2

作为插入点的路径中最短路的长度；…………D(n)=[dij(n)]nn，其中dij(n)=min{dij(n1)，di,n1(n1)

dn1,j(n1)}：dij(n)

表示从vi

到vj

的、中间最多只允许v1,v2,…,vn1

作为插入点的路径中最短路的长度，即vi

和vj

之间的距离。（II）求路径矩阵的方法.在建立距离矩阵的同时可建立路径矩阵R．（III）查找最短路路径的方法.然后用同样的方法再分头查找．若：（IV）Floyd算法：求任意两顶点间的最短路.例求下图中加权图的任意两点间的距离与路径.插入点v1，得：矩阵中带“=”的项为经迭代比较以后有变化的元素.插入点v2，得：矩阵中带“=”的项为经迭代比较以后有变化的元素.插入点v3，得：插入点v4，得：插入点v5，得：插入点v6，得：故从v5到v2的最短路为8由v5向v6追溯:由v6向v2追溯:所以从到的最短路径为：二、选址问题一、可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题例1设备更新问题：企业使用一台设备，每年年初，企业领导就要确定是购置新的，还是继续使用旧的.若购置新设备，就要支付一定的购置费用；若继续使用，则需支付一定的维修费用.现要制定一个五年之内的设备更新计划，使得五年内总的支付费用最少.分析：可行的购置方案（更新计划）是很多的，如：1）每年购置一台新的，则对应的费用为：

11+11+12+12+13+5+5+5+5+5=842)第一年购置新的，一直用到第五年年底，则总费用为：11+5+6+8+11+18=59

显然不同的方案对应不同的费用。第i年度12345购置费1111121213设备役龄0-11-22-33-44-5维修费用5681118这样上述设备更新问题就变为：在有向赋权图G=(V,E,F)(图解如下)中求v1到v6的最短路问题.（2）方法：将此问题用一个赋权有向图来描述，然后求这个赋权有向图的最短路。求解步骤：1）画赋权有向图：设Vi

表示第i年初，(Vi,Vj)表示第i

年初购买新设备用到第j年初（j-1年底），而Wij

表示相应费用，则5年的一个更新计划相当于从V1

到V6的一条路。2）求解（标号法）由实际问题可知，设备使用三年后应当更新，因此删除该图中v1到v5，v1到v6，v2到v6的连线；又设备使用一年后就更新则不划算，因此再删除该图中v1v2，v2v3，v3v4，v4v5，v5v6五条连线后得到从上图中容易得到v1到v6只有两条路：v1v3v6

和v1v4v6.而这两条路都是v1到v6的最短路.

选址问题--中心问题S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故应将消防站设在v3处。

选址问题--重心问题最小生成树及算法1)树的定义与树的特征定义连通且不含圈的无向图称为树．常用T表示.树中的边称为树枝.树中度为1的顶点称为树叶.孤立顶点称为平凡树.平凡树定理2设G是具有n个顶点的图，则下述命题等价：1)G是树（G无圈且连通）；2)G无圈，且有n-1条边；3)G连通，且有n-1条边；4)G无圈，但添加任一条新边恰好产生一个圈;5)G连通，且删去一条边就不连通了（即G为最小连通图）；6)G中任意两顶点间有唯一一条路.2）图的生成树定义若T是包含图G的全部顶点的子图,它又是树,则称T是G的生成树.图G中不在生成树的边叫做弦.定理3

图G=(V,E)有生成树的充要条件是图G是连通的.（II）找图中生成树的方法可分为两种：避圈法和破圈法A避圈法:深探法和广探法

B破圈法A避圈法

定理3的充分性的证明提供了一种构造图的生成树的方法.这种方法就是在已给的图G中，每步选出一条边使它与已选边不构成圈，直到选够n-1条边为止.这种方法可称为“避圈法”或“加边法”在避圈法中，按照边的选法不同，找图中生成树的方法可分为两种：深探法和广探法.a)深探法若这样的边的另一端均已有标号，就退到标号为步骤如下：i)在点集V中任取一点u,ii)若某点v已得标号，检端是否均已标号.若有边vw之w未标号,则给w代v，重复ii).i-1的r点,以r代v,重复ii),直到全部点得到标号为止.给以标号0.查一端点为v的各边，另一w以标号i+1，记下边vw.令例用深探法求出下图10的一棵生成树

图1001234567891011121313a)深探法图100123456789101112步骤如下：若这样的边的另一端均已有标号，就退到标号为i)在点集V中任取一点u,ii)若某点v已得标号，检端是否均已标号.若有边vw之w未标号,则给w代v，重复ii).i-1的r点,以r代v,重复ii),直到全部点得到标号为止.给u以标号0.查一端点为v的各边，另一w以标号i+1，记下边vw.令例用深探法求出下图10的一棵生成树

3b)广探法步骤如下：i)在点集V中任取一点u,ii)令所有标号i的点集为是否均已标号.对所有未标号之点均标以i+1,记下这些

iii)对标号i+1的点重复步步骤ii)，直到全部点得到给u以标号0.Vi,检查[Vi,V\Vi]中的边端点边.例用广探法求出下图10的一棵生成树

图101012213212234标号为止.图103b)广探法步骤如下：i)在点集V中任取一点u,ii)令所有标号i的点集为是否均已标号.对所有未标号之点均标以i+1,记下这些

iii)对标号i+1的点重复步步骤ii)，直到全部点得到给u以标号0.Vi,检查[Vi,V\Vi]中的边端点边.例用广探法求出下图10的一棵生成树

图101012213212234标号为止.显然图10的生成树不唯一.B破圈法相对于避圈法，还有一种求生成树的方法叫做“破圈法”.这种方法就是在图G中任取一个圈，任意舍弃一条边，将这个圈破掉，重复这个步骤直到图G中没有圈为止.例用破圈法求出下图的一棵生成树.B破圈法例用破圈法求出下图的另一棵生成树.不难发现，图的生成树不是唯一的.3)最小生成树与算法介绍最小树的两种算法：Kruskal算法（或避圈法）和破圈法.AKruskal算法（或避圈法）步骤如下：

1)选择边e1，使得w(e1)尽可能小；2)若已选定边，则从中选取，使得:i)为无圈图，

ii)是满足i)的尽可能小的权，

3)当第2)步不能继续执行时，则停止.定理4由Kruskal算法构作的任何生成树都是最小树.例10用Kruskal算法求下图的最小树.在左图中权值最小的边有任取一条在中选取权值最小的边中权值最小边有,从中选任取一条边会与已选边构成圈,故停止,得中选取在中选取中选取.但与都B破圈法算法2

步骤如下：1)从图G中任选一棵树T1.2)加上一条弦e1，T1+e1中立即生成一个圈.去掉此圈中最大权边，得到新树T2,以T2代T1,重复2)再检查剩余的弦，直到全部弦检查完毕为止.例11用破圈法求下图的最小树.先求出上图的一棵生成树.

加以弦e2,得到的圈v1v3v2v1,去掉最大的权边e2,得到一棵新树仍是原来的树；

再加上弦e7，得到圈v4v5v2v4,去掉最大的