《九章节图.ppt》由会员分享，可在线阅读，更多相关《九章节图.ppt（19页珍藏版）》请在三一办公上搜索。
1、第九章 图,9.1 图的基本概念9.2 图中的通路、图的连通性和图的矩阵表示 9.3 带权图与带权图中的最短通路9.4 欧拉图9.5 哈密尔顿图 9.6 二部图 9.7 平面图与平面图的着色,例,假设有分布在不同建筑物中的5台计算机C1,C2,C3,C4,C5。计算机连接的可能方案以及每种连接方式的成本（单位：元）如右图所示。,成本最低的安装方案,带权图,一个带权图规定为 一个有序三元组(V，E，f)，或 一个有序三元组(V，E，g)，或 一个有序四元组(V，E，f，g)，其中，V是顶点集，E是边集，f是定义在V上的函数，g是定义在E上的函数，f和g我们可以称为权函数。对于每一个顶点或边x，f
2、(x)和g(x)可以是一个数字、符号或是某种量。,带权图中的最短通路,设G=(V,E,W)是一个带权图，其W是边集E 到R+=xRx0 的一个函数。通常称 W(e)为边e的长度，图G中一个通路的长度定义为通路中所经过的边的长度之和。设 v0,zV，要求从 v0到z的最短通路的长。,Dijkstra算法的基本思想,先把V分成两个子集，一个设为T,T=vVv0到v的最短通路的长已经求出，另一个是P=VT。显然T，因为至少v0T。要不断地扩大T，直到zT。,T PVT,v0,z,定理,对于任意的xP，设LT(x)表示从v0仅经过T中的顶点到x的最短通路的长。若不存在这样的通路，置LT(x)=。称LT
3、(x)为 x关于T的指标。令 LT(t1)=minLT(x)xP则 LT(t1)是从v0到t1的最短通路的长。,T PVT,v0,t1,注：LT(x)即为教材上的l(t),x,定理的证明,若存在从v0到t1的通路其长小于LT(t1)，这条路一定包含了P中的顶点（否则，LT(t1)最小）。设t2P，且t2是从v0到t1的其长度小于LT(t1)的通路中遇到的第一个P中的点。于是有一条从v0到t2仅经过T中的点的通路，其长度小于LT(t1)，而由LT(t2)的定义知，LT(t2)LT(t1),这与假设LT(t1)=minLT(x)xP矛盾。,T PVT,v0,t1,t2,命题,设T和P已知，已找出t
4、1,使 LT(t1)=min LT(x)xP。令 T=T t1 P=P t1，并设 LT(x)表示仅经过T中的点从v0到x的最短通路的长。则有 LT(x)=minLT(x),LT(t1)+W(t1,x)这里，若图中t1,x E,取W(t1,x)=。,命题的证明,从v0到x且不含P中顶点的任何一条最短通路，只有两种可能的情况：,一条既不包含P中的顶点也不包含t1的通路.此时，最短通路长仍然为 LT(x),命题的证明,(2)一条由v0到t1不包含P中的其它顶点，然后由t1经过t1,x到x的通路。此时，最短通路长为 LT(t1)+W(t1,x).,命题证明的说明：还有一种？,实际上，从v0到t1再到
5、 t的这条通路一定不短于从v0到t的最短通路，而由作法可知从v0 到t的最短路经过的点全在T中，所以即使有可能产生一条最短路，我们也可以用一条从 v0到t的仅经过T中点的最短通路取代，也就是说这种情况可以归化为第一种情况考虑。,从 v0到t1，再到 T中某一顶点t，由t到x中间不经P中点。,Dijkstra算法,设起点是v0，终点是z。具体程序如下：,开始，设 T=v0，P=VT，对P中的每一个顶点x,令 LT(x)=W(v0,x)。设t1是P中关于T有最小指标的顶点,即 LT(t1)=minLT(x)xP。若t1=z，则终止。否则，设 T=T t1，P=P t1。对于P中的每一个顶点，计算它
6、关于T的指标：LT(x)=minLT(x),LT(t1)+W(t1,x)。把T代为T,把P代为P,把LT(x)代为LT(x)，重复步骤(2)。,例 求图9.9中从a到z的最短通路的长,T=a,b 3 8 6,T=a,b,c 8 4,T=a,b,c,e 7 10,T=a,b,c,e,d 9,最短通路的长度为9，最短通路的路径为(a,b,c,e,d,z)。,例(在各顶点上标记了最短通路及长度),例 求顶点a至顶点f最短通路的长,狄克斯瑞（Edsger Wybe Dijkstra，1930-2002.08.02）,计算机编程艺术与科学创建人之一.1930年出生在荷兰鹿特丹市，于2002年8月6日在荷
7、兰家中与世长辞。他在欧洲和美国曾从事首次航空和结构计算机模拟的工作。曾是开发Algol的委员会成员。他编写了第一个Algol 60编译器。1972年，荣获美国计算机协会的图灵奖。,1962年，他担任Eindhoven Polytechnic大学数学教授。他不赞成将教授职位称作计算科学教授，因为计算专业的科学性还不够。他用了十年时间使编程被承认为一门真正的学科。他对Basic编程语言所鼓励的许多“罪恶”尤其不能容忍，他说Basic不可挽回地伤害了年轻的程序员，并写下了一篇著名的论文：Go To语句是有害的。,第九章 图,9.1 图的基本概念9.2 图中的通路、图的连通性和图的矩阵表示 9.3 带权图与带权图中的最短通路9.4 欧拉图9.5 哈密尔顿图 9.6 二部图 9.7 平面图与平面图的着色,
