九章节图.ppt
第九章 图,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(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(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已知，已找出t1, 使 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再到 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中的每一个顶点 ，计算它关于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日在荷兰家中与世长辞。他在欧洲和美国曾从事首次航空和结构计算机模拟的工作。曾是开发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 平面图与平面图的着色,
