图与网络模型-图论-数学建模ppt课件.ppt

《图与网络模型-图论-数学建模ppt课件.ppt》由会员分享，可在线阅读，更多相关《图与网络模型-图论-数学建模ppt课件.ppt（136页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 图与网络模型图与网络模型 瑞士数学家欧拉在1736年发表了一篇题 为“依据几何位置的解决方法”的论文，有 效地解决了哥尼哥尼斯堡“七桥问题”，这 是有史以来的第一篇图论论文，欧拉被公 认为图论的创始人。18世纪的哥尼斯堡城中流过一条河。河上游七座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样的游戏：一个游者怎样才能一次连续走过这七座桥而每座桥只走一次，回到原出发点。没有人想出这种走法，又无法说明走法不存在，这就是著名的“七桥”难题。欧拉将这个问题归结图论的问题。他用A,B,C,D四点表示河的两岸和小岛，用两点间的连线表示桥。七桥问题变为：从A,B,C,D任意点出发，能否通过每条边

2、一次且 仅一次，再回到原点？欧拉证明了这样的走法不存在，并给出了这类问题的一般结论。 1857年，英国数学家哈密顿发明了一种游戏，他用一个实心正12面体象征地球，正12面体的20个定点分别表示世界上20座名城，要求游戏者从任一城市出发，寻找一条可经由每个城市一次切仅一次再回到原出发点的路，这就是“环球旅行”问题。如图5-3所示。 他与七桥问题不同，前者要在图中找一条经过每边且仅一次的路统称欧拉回路，而后者是要在图中找一条经过每个点一次且仅一次的路，能成为哈密尔顿回路。哈密顿根据这个问题的特点，给出了一种解法如图5-4所示。 在这一时间，还有许多诸如迷宫问题、博弈问题以及棋盘上马的行走路线之类的

3、游戏难题，吸引了许多学者。这些看起来似乎无足轻重的游戏却引出了许多有实用意义的新问题，开辟了新学科。 运筹学中的“中国邮路问题”：一个邮递员从邮局出发要走遍他所负责的每一条街道去送信，蚊蝇如何选怎适当的路线可是所走的总路程最短。这个问题就与欧拉回路有密切的关系。而著名的“货郎担问题”则是一个带权的哈密尔顿回路。而著名的“货郎担问题”则是一个带权的哈密尔顿回路问题。 图论的第一本专著是匈牙利数学家O Koing 写的“有限图与无限图的理论”，发表于1936年。从1736年欧拉的第一篇论文到这本专著，前后经历了200年之久，总的来讲这一时期图论的发展是缓慢的。直到20世纪中期，电子计算机的发展以及

4、离散数学问题具有越来越重要的地位，使得作为提供离散数学模型的图论得以迅速发展，成为运筹学中十分活跃的重要分支。目前图论被广泛地应用于管理科学、计算机科学、信息论、控制论、物理、化学、生物、心理学等各个领域，并取得了丰硕的成果。第一节第一节 图与网络的基本知识图与网络的基本知识 一、图与网络的基本概念一、图与网络的基本概念 1. 图及其分类 自然界和人类社会中，大量的实物以及事物之间的关系，常可以用图形来描述。例如，为了反映5个队参加的球类比赛请况，可以用点表示球队，用点间连线表示两个队已经比赛过，如图5-5所示。又例如工作分配问题，我们可以用点表示工人与需要完成的工作，点间连线表示每个人可以胜

5、任那些工作，如图5-6所示。 这样的例子很多，物质结构、电路网络、城市规划、交通运输、物资调配等也都可以用点和线连接起来的图进行模拟。 由上面的例子可以看出，这里所研究的图 与平面几何中的图不同，这里只关心图中 有多少个点，点与点之间又无连线，至于 连线的方式 是直线还是曲线，点与点的 相对位置如何，都是无关紧要的。总之，这里所讲的图是反映对象之间关系的一种工具。图的理论和方法，就是从形形色色的具体的图以及与他们相关的实际问题中，抽象出共同性的东西，找出其归律、性质、方法，在应用到解决实际问题中去 定义定义1 1. 一个图是由点集V = 和V 中元素的无序对的一个集合E= 所构成的二元组，记为

6、G=(V,E),V中元素叫做顶点，E中的元素叫做边。当V,E为有限集合时，G成为有限图，否则，成为无限图。本章只讨论有限图。ivke例5.1 在图5-7中：V=v1，v2，v3，v4，v5 E= e1，e2，e3，e4 ,e5.其中： e1=（v1，v2） e2=（v1，v2） e3=（v1, v3） e4=（v2，v3） e5=（v2，v3） e6=（v3, v4）两个点u，v属于V，如果边（u，v）属于E，则称u，v两点相邻。u，v 成为边（u，v）的端点。两边ei, ej属于E，如果他们有一个公共端点u，则称ei, ej相邻。边ei, ej 成为点u的关连边。用m（G）=|E|表示图G中

7、的边数，用年（G）=|V|表示图G的定点个数。在不引起混淆情况下简记为m,n。 对于任一条边（vi, vj）属于E，如果边（vi, vj）端点无序，则他是无向边，此时图G成为无向图。图5-7时无向图。如果边（vi, vj）的端点有序，即他表示以vi为试点，vj为终点的有向边（或称弧），这时图G称为有向图。 一条边的两个端点如果相同，称此边为环。如图5-7中的 e1。 两个点之间多余一条边的，称为多重边。如图5-7中的 e4， e5。 定义定义2 2 不含环和多重边的图称为简单图，含有多重边的图成为多重图。以后我们讨论的图，如不加特别说明，都是简单图。 有向图中两点之间有不同方向的两条边，不是多

8、重边。如图5-8种的（a)，（b）为简单图，（C），(d)为多重图。 定义定义3 3 每一对顶点间都有边相连的无向简单图称为完全图。有n个顶点的五项完全图及做Kn。 有向图完全图则是指每一对顶点间有且仅有一条有向边的简单图。 定义定义4 4 图G=（V，E）的点集V可以分为两个非空子集X，Y，即 ， ，使得E中每条边的两个端点必有一个端点属于X，另一个端点属于Y，则称G为二部图（偶图），又是记作G=（X，Y，E）。 例如图5-9种的（a）是明显的二部图，点集X: v1，v2，v5。（b）也是二部图，但是不象（a）那样明显，改画为（c）时也可以看清楚。YX VYX 2.顶点的次 定义定义5 以点

9、v为端点的边数叫做点v的次，记作deg(v)，简记d(v)。 如图57中点v的次d(v)=4，因为边e1要计算两次。点v的次d(v3)=4，点v4的次d(v4)=1。 次为1的点称为悬挂点，连接悬挂点的边成为悬挂边。如图57中v4,v6。次为0的点称为孤立点。如图57中点v5。次为奇数的点称为奇点。次为偶数的点称为偶点。 定理定理1 1 任何图形中，顶点次数的和等于边数的二倍。 证明证明 由于每条边必须与两个顶点关联，在计算点的次时，每条边都被计算了两次，所以顶点数的总和是边数的两倍。 定理定理2 2 任何图形中，次为奇数的顶点必为偶数个。 证明证明 设V1和V2分别为图G中奇点与偶点的集合(

10、V1V2=V)。由定理1知 由于2m为偶数，而 为若干偶数之和也是 偶数。所以 也比为偶数，即|V1|是偶数。 定义6 有向图中，以vi为始点的边数成为点的vi的初次，用d+（vi）表示，以vi为终点的边数为点vi的仁次，用d-（vi）表示。vi点的初次与人次之和就是该点的次，容易证明由此向图中，所有顶点的入次之和等于所有顶点的初次之和。 122v vv vv Vd vd vd vm 2v vd v 1v vd v 3. 子图 定义定义7 7 图G=（V，E），若E1是E的子集，V1是V的子集，且E1中的边仅与V1中的顶点相关联，则称G1=（V1，E1）是G的一个子图。特别的，若V1=V，则G

11、1成为G的生成子（支撑子图）。 如图5-10中（b）为（a）的子图，（e）为（a）生成子图。 子图在描述图的性质和局部结构中有重要作用。 4.网络 在实际问题中，往往只用图来描述所研究对象之间的关系还不行，与图联系在一起的， 通常还有与点或边有关的某些参数指标，我们称之为“权”，权可以代表如距离、费用、通过能力（容量）等等。这种点或边带有某种数量指标的图成为网络。 与无向图和有向图相对应，网络又分为无向网络和有向网络，图5-11（a），（b）是常见的网络例子。（a）给出了物资供应站vs与用户（v1，v2， v7）之间的公路网络图，的权表示个点间的距离，从优化角度出发存在一个寻求到各点的最短路问

12、题。 （b）是个从的管道运输网络，边上的权表示物流的最大容量，我们要求从德客运的最大流方案。这些网络模型将在各节中讨论。 二、连通图连通图 定义8 无向图G=（V，E），若图G中某些与变得交替序列可以排成 的形式，且 ,则称这个点便序列为联接 的一条链，链长为K。 点边列中只有重复的点而无重复边者为简单链。点边列中没有重复的边者为初等链。图5-12中，01121(,)iiiiikikikvevevev1(,)(1, )ititiievvtk0iikvv与6657185719443631665718554431665443 , , ,sv e v e v e v e v e v e vv vsv

13、 e v e v e v e v e vsv e v v e v为一条连接的链。 定义定义9 9 无向图G中，连结 的一条链，当 是同一个点时，称此链为圈。圈中只有重复点而无重复边者为简单圈，即无重复点也无重复边者为初等全。 图5-12中 为一个圈。 对于有向图可以类似于无向图定义链和圈，初等链、圈、简单链、圈，此时不考虑边的方向。而当链上的边方向相同时，称为道路。 图5-13中， 对于无向图来说，道路与链、回路与圈意义相同。ioikvv与ioikvv与1758191021 , v e v e v e vv v665819410233166571944311221145581 , , , sv

14、 e v e v e v ev e v esv e v e v e v e vsv e v ev e v e v为一条链。为一条道路。为一个圈。 定义定义1010 一个图中任意两点间至少有一条链相连，则称此图为连通图。任何一个不连通图都可以分为若干个连通子图，每一个称为原图的一个分图。 三、三、图的矩阵表示图的矩阵表示 用矩阵表示图对研究图的性质及应用常常是比较方便的，图的矩阵表示方法有权矩阵、邻接矩阵、关联矩阵、回路矩阵、割集矩阵等，这里只介绍其中两种常用矩阵。 定义定义11 11 网络G=（V，E），其边 ，其中： 则称矩阵A为网络G的权矩阵。(),()ijijijn nvvwAa有权构造

15、矩阵(,)0ijjjijwv vEa其他例5.2 图5-14所示的图，其矩阵为 定义定义12 12 对于图G=（V，E），构造一个矩阵A= ，其中： 则称矩阵A为图G的邻接矩阵。0924790340230854480670560A()ijann1( ,)0ijijv vEa其他例5.3 对图5-15所示的图可以构造邻接矩阵A 如下： 当G为无向图时，邻接矩阵为对称矩阵。010000001000010010010001010101000010A 四、四、欧拉回路与中国邮路的问题欧拉回路与中国邮路的问题。 1、欧拉回路与道路 定义定义1313 连通图G中，若存在一条道路，经过每边一次且仅一次，则称

16、这条路为欧 拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路（欧拉环游）。 含有欧拉回路的连通图称为欧拉图（E图）。在引言中提到哥尼斯堡七桥问题就是要在图中寻找一条欧拉回路。 定理定理3 3 无向连通图G是欧拉图，当且仅当G中无奇点。 证明(必要性) 因为G是欧拉图，则存在一条回路，经过G中所有的边，在这条回路上，定点可能重复出现，但边不重复。对于图中的任意顶点，只要在回路中出现一次，必关联两条边，即这条回路沿一条边进入这点，再沿另一边离开这点。所以点虽然可以在回路中出现，但deg(vi) 必为偶数。所以G中没有基点。 (充分性) 由于G中没有基点，从任意点出发，如从点出发

17、，经关联边如此进行下去，每边仅取一次。由于G图中点数有限，所以这条路不能无休止地走下去，必可走回V，得到一条回路C。 (1)若回路C1经过G的所有边，则C1就是欧拉回路。 (2)从G中去掉C1后得到子图，则中每个定点的次数仍为偶数。因为G图时连同图，所以C1与 至少有一个定点重合，在中从出发，重复前面C1的方法，得到回路C2。 推论推论1 1 无向连通图G为欧拉图，当且仅当G的边集可划分为若干个初等回路。 推论推论2 2 无向连通图G有欧拉道路，当且仅当G中恰有两个奇点。 根据定理来检查哥尼斯堡七桥问题，从图5-2中可以看到deg(A)=3,deg(B)=3,deg(C)=5,deg(D)=3

18、有四个基点，所以不是欧拉图。即给出了哥尼斯堡七桥问题的否定回答。 与七桥问题类似的还有一笔画问题。给出一个图形，要求判定是否可以一笔画出。一种是经过每边一次且仅一次到另一点停止。另一种是经每边一次且仅一次回到原开始点。这两种情况可分别用关于欧拉道路和欧拉回路的判定条件加以解决。 定理3的证明方法实际上给出了构造欧拉回路的一种算法，从图G中任一点出发，找一个初等回路，再从图中去掉，在剩余的图中再找出等回路，一直做到图中所有的边都被包含在这些初等回路中，再把这些回路连续起来既得这个图这个图的欧拉回路。 关于无向图的定理3，可以直接推广到有向图。 定理定理4 4 连通有向图G是欧拉图，当且仅当它没个

19、顶点的初次等于入次。 连通有向图G有欧拉道路，当且仅当这个图中除去两个顶点外，其余每一个顶点的初次等于入次，且这两个顶点中，一个顶点的入次比初次多1，令一个顶点的入次比初次少于1。 2、中国邮路问题 一个邮递员，负责某一地区的信件投递。他每天要从邮局出发，走遍该地区所有街道再返回邮局，问应如何安排送信的路线可以使所走的总路程最短？这个问题是我国管梅谷同志在1962年首先提出的。因此国际上统称为中国邮路问题。用图论的语言描述：给定一个连通图G，每遍有非负权L（e），要求一条回路过每边至少一次，且满足总劝最小。 如果G中有奇点，要求连续走过每边至少一次，必然有些便不止一次走过，这相当于在图G中对某

20、些怎加一些重复边，时所得到的新图 没有奇点且满足总路程最短。由于总路程的长短完全取决于所增加的重复边的长度，所以中国邮路问题也可以转为如下问题： 在连通图G=（V，E）中，求一个边集 的边均变为二重边得到图 ，使其满足G*无奇点，且 最小。11,GEEE把 中属于*1GGE11()( )e EL El e*G 定理5 已知图 无奇点，则 最小的从份必要条件为： (1)每条边最多重复一次。 (2)对图G中每个初等圈来讲，重复边的长度和不超过圈长的一半。 证明证明 ( (必要性必要性) ) 假如 中有某条边重复次数n（n2），而 是欧拉图，那么把这条边上的重复边去掉两条，则与此便关联的两个顶点的次

21、都减2，仍为偶点故仍为欧拉图，所以重复边次数最多为一次即可。*1GGE11()( )e EL El e*G*G 其次，把土的一个初等圈上原来重复的边都不重复，而原来不重复的重复一次，则圈上没个顶点的次改变0或2，也不改变欧拉图的性质。因此，如果图G中存在某个圈，其重复边的长度超过圈长的一半，我们就可以使从复边的长度减少，这与 最小矛盾。 (充分性) 只需证明凡满足定理中条件（1），（2）的重复边集，其总长度均相等即可。设1()L E12,12E E12都满足定理中条件（），（），下面来证明L(E )=L(E ) 作边集 ，则 中的边或属于或属于 ，二者必居且仅据其一。观察由边集 中边和与之相关

22、联的点组成的图 ， 可能不连通，但其每个分图必为欧拉图（因为图G的每个顶点v与 中相关联的重复边的数目与V与E2相关联的变数的奇偶性相同，都取决于v原来的次数为奇或为偶，重复变数也必为奇或偶，所以图 的点必为欧点），所以每个分图可分为若干个初等圈。根据定理条件，对每个初等圈上均有 的重复变长不超过周长的一半和 的重复边长不超过周长的一半，故只能相等。则在 中属于E1的边总长等于属于 的边总长，于是有 定理给出了中国邮路问题的一种算法，成为“奇偶点图上作业法”，下面举例说明这个算法。01212()()EEEEE0E1E2E0E0G0G0G1E2E0E1E2E12()()L EL E 例5.4求解

23、图5-16所示网络的中国邮路问题。 第一步：确定初始可行方案。 先检查途中是否有奇点，如无奇点则已是欧拉图，利用Fleury算法找出欧拉回路即可。如有奇点，由前知奇点个数比为偶数个，所以可以两两配对。每队点间选择一条路，使这条路上均为二重边。 图5-16中有十个奇点 将 ， 配对，连接 的路有好几条，任取一条，如 ，类似地，对 得到图5-17，已是欧拉图。对应这个可行方案，从复边的总长为：2468,v v v v24vv与6v8与v24vv与2369874 ,v v v v v v v686321478 ,vvv v v v v v v与 取2336699887744112222251llll

24、llll 第二步：调整可行方案，是重复边最多为一次。 去掉 各两条，得到图5-18，重复边总长度下降为： 第三步：检查图中每个初等圈是否满足定理条件（2）。如不满足则进行调整，直至满足为止。 检查图5-18，发现圈 总长度的长为24，而重复边的长为14,大于该圈总长度的一半，可以做一次调整，以 得到图5-19，重复边总长度下降为； 23364778(,),( ,),(,),(,)v vv vv vv v1214699821llll1 2 5 4 1v v v v v25541214(,),(,)( ,),( ,)v vv vv vv v代替2545699817llll 在检查图5-19，圈 总

25、长度为24，而重复边长为13。再次调整得图5-20,重复边总长度为15。 检查图5-20，条件（1），（2）均满足，得到最优方案。途中任意欧拉回路即为最优邮递路线。 这种方法虽然比较容易，但要检查每个初等圈，当G的点数获边数较多时，运算量极大。Edmods和Johnson与1973年给出了一种比较有效的算法，即化为最短路即最优匹配问题求解。2 3 6 9 8 5 2v v v v v v v第二节第二节 树树 一、树的概念和性质一、树的概念和性质 树是图论种结构最简单但又十分重要的图，在自然科学和社会的许多领域都有广泛的应用。 例例5.55.5 乒乓球单打比赛抽签后，可用图来表示项羽情况，如图

26、5-21。 例例5.6 5.6 某企业的组织结构可用图5-22所示。 定义定义14 14 连通且不含圈的物象图称为树，树中次为1的点称为树叶，次大于1的点称为支点。 下面研究树的性质。树的性质的用下面定理标出。 定理定理6 6 图T=(V，E), V =n, E=m,则下列关于书的说法是等价的。 （1）T是一个树。 （2）T无圈，且m=n-1。 （3）T连通，且m=n-1。 （4）T无圈，但每加一新边即唯一一个圈。 （5）T连通，但每舍去一边就不连通。 （6）T中任意两点，有唯一链相连。 证明 : (1) (2) 由于T是树，由定义知T是连通的并且没有圈。只需证明T中的边数m等于顶点个数1，即

27、m=n-1. 用归纳法。当n=2时，由于T是树，所以两点间显然有且仅有一条边，满足m=n-1. 归纳假设n=k-1匙命题成立，即有k-1个顶点是T有k-2条边。当n=k时，因为T连通无圈，k个顶点中至少有一个点次为1。设此点为1。设此点为u，即u为悬挂点，设连接u点的悬挂边为（v，u）。从T中去掉（v，u）边及u点不会影响T的连通性，得图，为树只有k-1个顶点，所以有k-2条边，再把（v，u），u加上去，得知当T有k个顶点时有k-1条边。 (2) (3) 只需证明T是连通图。 反证法。设T不连通，可以分为l个连通图 个顶点， 。因为第i个分图是树，所以 条边，L个分图共有边数为 与已知矛盾。所

28、以T为连通图。(2),ilin设第 个分图有1tiinn1in 1(1)1tiinnln (3) (4) 若T中有圈，设为C。可以去掉C中一条边，并不影响T的连通性。如果剩余途中仍有图，可如前那样继续拿去一条边。像这样去掉P条边后得到一个没有权的连通图，显然有n-1-p条边。但既然是树，定点个数又与T相同为n个，所以中应有n-1条边。矛盾，即T中无圈。 设T中u，v两点间无边直接相连，由于T是连通图，所以经由其他点必有一条链连结u，v，且此联是连结着两点的唯一链，则T+（u,v）后，出现唯一一个圈。 (4) (5) 先证明T连通。若T不连通，由定义至少存在两点u，v之间无路可通。那么加上一边（

29、u，v）也不会形成圈，与已知矛盾。 在证每舍去一边遍布连通。若T中有一边（u，v），舍去(u,v)后图T-（u，v）仍然连通，与（4）中树妹家一新边壁出现唯一圈相矛盾。 (5) (6),(6) (1)，均显然，故定理证毕。 定理6中每一个命题均可作为书的定义，他们对判断和构造树将极为方便。 二、图的生成树二、图的生成树 定义15 若图G的生成子图是一棵树，则称该树为G的生成树。或简称为图G的树。 如图5-23中（b）为（a）图的生成树，边 为树枝， 为弦。 定理定理7 7 图G=（V，E）有生成树的充分必要条件为G是连通图。 证明 必要性显然。456,e e e123789,e e e e e

30、 e 充分性 任取 ，这时生成树T的边集合 为空集。因为G是连通图，点集 之间必有变相连，设 为这样的边， 则得 重复上述步骤，对于 仍能找到 边满足其一端在点集 ,另一端 在点集 有一端在Vi之外，所以 中的边不构成圈。当i=n时得到( ) iiteE与iV.iiV Ve由于ie( )12121 , ,iiiTnVv vvEe eein(2)2121 , iTVv vvEe111vVV V2而v112( ,)ev v11/vV V与(1)TE111, vVVv令集合 即图T=（V）,有n-1条边且无圈，由定理6知，这是一棵树，且为图G的一棵生成树。 定理7证明是构造型的证明，给除了寻求的生成

31、树的方法。这种方法就是在以给出的图G中，每步选出一条边使它与已选边为构成圈，直到选够n-1条边为止。这种方法可为“避圈法”，或“加边法”。 按照边的悬法不同，找图中生成树的方法可分为两种：( )12121 , ,nnnTnVv vvVEe ee（1）深探法。 步骤如下：（用标号法） 1、在点集V中任取一点v，给v已标号0。 2、若某点u已得标号i，检查一端点为u的各边，另一端点是否均已标号。 若有（u，w）边之w未标号，则给w以标号为i-1的r点，以r代u，重复2。直到全部点得到标号为止。 下图5-24的（a）为标号过程，粗线边即为生成树，图5-24（b）即是生成树，也显示了标号过程。（2）广

32、探法。 步骤如下： 1、在点集V中任取一点给v，给v以标号0。 2、令所有标号为i的点集为中的边端点是否均以标号。对所有为标号之点均标以i+1，记下这些边。 3 、对标号i+1的点重复步骤2,直到全部点得到标号为止. 如图5-25（a）中粗线边就是用广探法生成的树，也可表示为图5-25（b）。 显然，图的生成树不唯一。 相对于避圈法，还有一种求生成树的方法。这种方法是在图G中任一曲一个圈，从圈上任意舍弃一条边，将这个圈破掉。重复这个步骤直到图G中没有圈为止。 例例5.75.7 一个乡有9个自然村，其间道路如图5-26（a）所示，要以 村为中心建有线广播网络，如要求沿道路架设广播线，应如何架设？

33、 解 本问题用上述破解法，任取一圈 从中去掉边 ，再选圈 ，去掉边 ，以同样方法进行，直到无圈。图5-26（b）就是一种方案. 18( ,)v v1801 , v v v v12( ,)v v1021 , ,v v v v0v 三、最小生成树问题最小生成树问题 定义16 连通图G=（V，E），每条边上有非负权 。一棵生成树所有树枝上权的总合，成为这个生成树的权。具有最小权的生成树成为最小生成树，简称最小树。 许多网络问题都可以归结为最小树问题。例如，设计长度最小的公路网把若干城市联系起来：设计用料最省的电话线网把有关单位联系起来等等。 下面介绍最小树的两种算法。 算法1（Kruskal）算法

34、这个方法类似于生成树的“避圈法”，基本步骤如下： 每步从未选的边中选取边e，使它与已选边不构成圈，且e是位选边中的最小权边，直到选够n-1条边为止。( )L e 例5.8 仍用上节例7，若已知各条道路长度如图5-27（a）所示，各边上的数字表示距离，问如何拉线才能使用线最短。这就是一个最小生成树问题，用Kruskal算法。 先将（a）中边按大小顺序由小至大排列：02233418010656036704050812077845(,)1(,)1( ,)1( ,)1(,)2(,)2(,)2(,)3(,)3(,)4(,)4(,)4( ,)4(,)5(,)5(,)5v vv vv vv vv vv vv

35、 vv vv vv vv vv vv vv vv vv v 然后按照边的排列顺序，取定 由于下一个未选中的最小权边 构成圈，所以排除。选 。得到（b）就是图G的一颗最小树，它的权是13。867(,)ev v0312(,),v ve e与已选边102223334418501606756(,)(,)( ,)( ,)(,)(,)(,)ev vev vev vev vev vev vev v 定理定理8 8 用Kruskal算法得到的子图 是一棵生最小树 证明 由算法所构造的子图 无回路且n个点有n-1条边，则由定理6知 是图G的生成树。 下面证明生成树 一定是最小树。 若 不是最小树，而T ，T为最

36、小树。把T中的边也按权由小到大排列 然后与中的边相比较，若 即 也是树。11,iefTT则/112211,iiiiee eeeeee而/121,neee*T*T*T*T*T*T*T121( ,)ne ee 因为T是最小树，所以权 即有： 由Kruskal算法知 ，没有权的位选边中最小权边，所以权 只能有权 (f)。所以也是最小树且与 的公公边比T多一条，以 取代T,继续讨论ei+1 与ei+1是否相同，同前进行，易证T*是最小树。 *T1T( )ie 权( )( ),ief不大于权ie12i-1i是使e ,e , ,e,e ( )( )0ief权权1()( )TT1( )( )( )( )iT

37、Tef权权权权 算法2（破圈法） 基本步骤： （1）从图G中任选一棵树 。 （2）加上一条弦 中立即生成一个圈。去掉此圈中最大权边，得到新树 ，重复（2）在检查剩余的弦，直到全部弦检查完毕为止。 仍用例8，先求出图G的一棵生成树如图5-28的（a），加以弦 ,去掉最大权边 ：再加上弦 ,得圈 ,去掉最大权边 直到全部弦均以试过，图5-28（b）即为所求。 算法2的根据为下述定理 定理定理9 9 图G的生成树T为最小树，当且仅当对任一弦e来说，e是T+e中与之对应的圈。中的最大权边。证明从略。03(,),v v2 3 02v v v v23(,)v v12( ,)v v121 2 0 1( ,)

38、v vv v v v，得圈221TTT。以代111,e Tee1T 四、根树及其应用 前面几节我们讨论的树都是无向树，本届讨论有向树。有向树的根树在计算机科学、决策论中有重要应用。 定义定义1717 若一个有向图在不考虑边的方向时是一棵树，则这个有向图为有向树。 定义定义1818 有向树T，恰有一个结点入次为0，其余各点入次均为1，则称T为根树（又称外向树）。 根树中入次为0的点称为根。根树中出次为0的点称为叶,其他顶点称为分枝点.由根到某一顶点Vi的道路长度（设每边长度为1），称为Vi点的层次。 如图5-29所示的数十根树，其中 为分枝点，其余各点为叶，顶点 的层次为1，顶点 的层次为3等等

39、。 根树有广泛的应用，如用来表示一个系统的传递关系，指挥系统的上、下级关系，机关中各领导与被领导关系以及社会中一个家族胳臂之间的关系等等。在计算机科学中应用根树时，还常借用家族中的各种称呼，如图5-29中，称 的儿子，而 互为兄弟等等。234,v v v2341562,v v vvv vv为 的儿子为11v234,v v v112348,vv v v v v为根 定义定义1919 在根树中，若某个顶点的次小于或等于m，称这棵树为m叉树。若没个顶点的出次恰好等于m或零，则称这棵树为完全m叉树。当m=2时，称为二叉树、完全二叉树。 例如图5-30中（a）为完全二叉树、（b）为四叉树。 在实际问题中

40、常讨论叶子上的距离（层次）为 ，这样二叉树T的总权数 满足总权最小的二叉树成为最有二叉树。霍夫曼（D A Huffman）给出了一个求最有二叉树的算法，所以又称霍夫曼树。1( )si iim Tpl(1, )il is 算法步骤为： （1）将s个叶子节点按权由大排列，不失一般性，设 （2）将二个具有最小权的叶子合并成一个分枝点，其权为 ，将新的分枝点作为一个叶子。令 若s=1停止，否则转（1）。 例5.9 s=6，其权分别为4，3，3，2，2，1，求最有二叉树。 解 该树构造过程见图5-31。总权为 14+24+23+32+32+42=38 可以证明此算法得到的数位最优二叉树，直观意义：叶子的

41、距离是依权的递减而增加，所以总权最小。 最优二叉树有广泛的应用。1,ss12pp12sppp 例5.10 最优检索问题。使用计算机进行图书分类。现在五类图书共100万册，其中有A类50万册，有B类20万册，C类5万册，D类10万册，E类15万册。问如何安排分检过程，可是总的运算（比较）次数最小？ 解 构造一棵具有5个叶子的最优二叉树，其叶子的权分别为50，20，5，10，15，见图5-32（a）所示，按（b）进行分类。总权为： 分拣过程是先把A类50万册从总数中检出来，其次将B类20万册分检出来，然后再将E类15万册分检出来，最后再将D，C分检。( )5 410415 320250 1195m

42、 T 例5.11 某厂购进一批原件。欲进行检验后按质量分为六等。已知一等品的概率为0.45，二等品的概率为0.25，三等品0.12，四等品0.08，五等品0.05，等外品0.05。假设分等测试一次只能分辩出一种等级，而每次测试的时间皆为t。问如何安排测试过程，是期望的时间达到最短？ 解 构造一棵具有6个叶子的最优二叉树 的总权。经计算得( ) (5 0.05 5 0.05 4 0.08 3 0.12 2 0.25 1 0.45)2.13mTtt 课堂练习： 在通讯中，已知字母A,B,C,D,E,F出现的频率如下：A:30%,B:25%,C:20%,D:10%, E:10%,F:5% 求传送他们

43、的最优前缀码。 （1）首先构造Huffman树 （2）然后再构造最优前缀码第三节第三节 最短路问题最短路问题 最短路问题是网络理论中应用最广的问题之一。许多优化问题可以使这个模型，如设备更新、管道铺设、线路安排、厂区布局等。图论方法比较有效。 最短路问题的一般提法如下：设G=（V，E）为连通图，图中各边 为图中任意两点，求一条道路 ，使他是从 的所有道路中总权最小的道路。即： 最小.(,)( )ijijv vLlstvv到,stv v( ,)(,)ijijijijv vl lv v 有权表示 有些最短问题也可以使球网络中某指定点到其余所有结点的最短路，过求网络中任意两点间的最短路。下面我们介绍

44、三种算法，可分别用于求解这几种最短路问题。 一、一、DijkstraDijkstra算法算法 本算法由Dijkstra于1959年提出，可用于求解指定两点 间的最短路，或从指定点 到其余各点的最短路，目前被认为是求无负权网络最短路问题的最好方法。算法的基本思想基于以下原理：若序列 是从 的最短路，则序列 必为从 的最短路。svn-1到v11( ,)snv vvsnvv到11 ,snnv vvvsv,stv v 基本步骤：?),(),(, 0),()(,)(010的长度到其余各顶点的最短路求规定有是连通赋权简单图，vvvwGEvvvvwGEvvvvvGVGjijijijin次迭代即得结果经过且代

45、替用对任意的其中取）置（nniuSSvLvuwuLvLuSGVvSGVvvLvLniSGVvuSnjvLvLiiiiiiiijiiij), 2 , 1(,),(),()(),(min,)()()(min)(), 2 , 1( ,)()2(), 2 , 1()(, 0)(1111100azbcde4251081263 解：0次迭代（初始化） L(a)=0,L(b)=L(c)=L(d)=L(e)=L(e)= ,S0= ; 一次迭代：取u1=a,S1=a L(a)+w(a,b)=0+4=4L(b) L(a)+w(a,c)=0+2=2L(c) L(a)+w(a,d)=0+ = L(a)+w(a,e)=

46、L(a)+w(a,z)=0+ = ; L(b)=4,L(c)=2,L(d)=L(e)=L(z)= 二次迭代：取u2=c, S2=a,c L(c)+w(c,b)=2+1=3L(b) L(c)+w(c,d)=2+8=10L(d) L(c)+w(c,e)=2+10=12L(e) L(c)+w(c,z)=2+ = L(b)=3,L(d)=10,L(e)=12,L(z)= 三次迭代：取u3=b, S3=a,c,b L(b)+w(b,d)=3+5=8L(d) L(b)+w(b,e)=3+ = L(b)+w(b,z)=3+ = L(d)=8, L(e)=12, L(z)= 四次迭代：取u4=d, S4=a,

47、c,b,d L(d)+w(d,e)=8+2=10L(e) L(d)+w(d,z)=8+6=14L(z) L(e)=10, L(z)=14; 五次迭代：取u5=e, S5=a,c,b,d,e L(e)+w(e,z)=10+3=13L(z) L(z)=13 结束：u6=z, S6=a,c,b,d,e,z 从a到z 的最短路的长度为13,最短路经为a,c,b,d,e,z 同样可以利用Dijkstra算法计算有向网络中最短有向路的长度，基本步骤如下：)2(,min,33,min,)2(), 3 , 2(, 1, 0, 3 , 2,1) 1 (,),(; 0,),(, 2 , 1)(),(,1再转置中每

48、一个顶点）对（）终止，否则转（若置使得中寻找一个点在且置有有有向网络jkwSSSjTTkTTkPPSSkTnjjwSSnTPjiwDAijjiwDAijnDVAVDkjjjTjkj 求出点1到其余各顶点的最短有向路的长度？321455318274 Dijkstra算法:9, 3, 8, 5,0:918 ,11min5 , 3,min5,3 ,2,4, 1, 3115 ,11min5 ,2,min835 ,10min3 ,2,min5 , 3,2,4, 1,21183 ,min5 ,4,min1073 ,min3 ,4,min53 , 5min2,4,min5 , 3 ,2,4, 1,45 ,

49、1, 34, 1,3 , 152, 1,0,5 ,4, 3 ,2,15432135525523345543342254321SSSSSwSSSTPkwSSSwSSSTPkwSSSwSSSwSSSTPkwSwSwSwSSTP显然且 课堂练习1：利用Dijkstra算法，算出图中，v1到v5的最短路的长度？v1V2V3V4V5431027815 选址问题：已知某地区的交通网络如图5-39所示，其中点代表居民区，边表示公路， 为小区间公路距离，问区中心医院建在哪个小区，可使距离医院最远的小区居民就诊时所走的路程最近?ijlV1V3V4V6V7V2V5602030251520183015解：实际是要求

50、出图的中心，可以化为一系列求最短路问题。先求出 v1 到其他各顶点的最短路长dj,令D(v1)=maxd1,d2,d7,表示若医院建在v1, 则离医院最远的小区距离为D(v1),再依次计算v2,v3,v7到其余各点的最短路，类似求出D(v2),D(v3),D(v7), D(vi)(i=1,2,7)中最小者即为所求，计算结果见表5-3。由于 D(v6)=48最小，所以医院健在v6，此时离医院最远的小区 v5距离为48。由于 D(v6)=48最小，所以医院健在v6，此时离医院最远的小区 v5距离为48。v1v2v3v4v5v6v7D(vi)V1030506393456093V23002033631