欧拉图及哈密顿课件

《欧拉图及哈密顿课件》由会员分享，可在线阅读，更多相关《欧拉图及哈密顿课件（65页珍藏版）》请在金锄头文库上搜索。

1、第二章第二章 第一节第一节 欧拉图欧拉图(1)定义1 给定无孤立结点的无向图G,经过图G的每边一次且仅一次的迹为一条欧拉路.经过图G的每边一次且仅一次的回为一条欧拉回路.说明:(1)由定义,含有欧拉路(回)的图显然是连通的;(2)欧拉路是迹(边互不重复),但不是严格意义上的路.定理1连通图G具有欧拉回路当且仅当其每个顶点的度数为偶数.欧拉图及哈密顿欧拉路欧拉路(2)证明:必要性:不妨设C是从顶点x1开始的无向图G的一条欧拉回路.对该回路中的任何一个内部点xi而言,每出现一次,其度数必增加2,对x1来讲,回路最后在该点结束,当然其度数也为偶数.充分性:若G是连通无向图,作G的一条最长回C,并假设

2、C不是欧拉回路.这样,在C中必存在xkV(C)及关联xk的边e=xk,x1 C;又deg( x1)为偶数,所以存在e1=x1,x2 ,e2=x2,x3, en=xn,xk,这样在G中又找到一条回C,若G=CUC,则结论成立,反之,继续寻找,总可以找到符合条件的回.欧拉图及哈密顿第二章 欧拉图与哈密顿图(2)定理定理2 2 连通图连通图G G具有欧拉路而无欧拉回路具有欧拉路而无欧拉回路, ,当且仅当当且仅当G G恰有两个奇数度顶点恰有两个奇数度顶点. .证证: :必要性必要性: :设连通图设连通图G G从顶点从顶点a a到顶点到顶点b b有有欧拉路欧拉路C,C,但不是欧拉回路但不是欧拉回路. .

3、在欧拉路在欧拉路C C中中, ,除第一边和最后一边外除第一边和最后一边外,每经过每经过G G中顶点中顶点x xi i( (包括包括a a和和b),b),都为顶点都为顶点x xi i贡献贡献2 2度度, ,而而C C的的第一边为第一边为a a贡献贡献1 1度度,C,C的最后一条边为的最后一条边为b b贡贡献献1 1度度. .因此因此,a,a和和b b的度数均为奇数的度数均为奇数, ,其余其余结点度数均为偶数结点度数均为偶数. . 欧拉图及哈密顿充分性充分性: :设连通图设连通图G G恰有两个奇数度结点恰有两个奇数度结点, ,不妨设为不妨设为a a和和b,b,在图在图G G中添加一条边中添加一条边

4、e=a,be=a,b得得G,G,则则GG的每个结点的度数均为偶数的每个结点的度数均为偶数, ,因因而而GG中存在欧拉回路中存在欧拉回路, ,故故G G中必存在欧拉路中必存在欧拉路. .定义定义2 2 给定有向图给定有向图D,D,经过经过D D中每边中每边一次且仅一次且仅一次一次的的有向迹有向迹称为称为D D的的有向欧拉路有向欧拉路. .经过经过D D中中每边一次且仅一次的每边一次且仅一次的有向闭迹有向闭迹( (回回),),称为有称为有向欧拉回路向欧拉回路. .欧拉图及哈密顿第二章 欧拉图与哈密顿图(3)定理定理3 具有弱连通性的有向图具有弱连通性的有向图G具有有向欧拉具有有向欧拉回路回路,当且

5、仅当当且仅当G的每个结点的入度等于出度的每个结点的入度等于出度. 具有弱连通性的有向图具有弱连通性的有向图G具有有向欧拉路具有有向欧拉路,当当且仅当在且仅当在G中中,一个结点的入度比出度大一个结点的入度比出度大1,另另一个结点的入度比出度小一个结点的入度比出度小1,而其余每个结点而其余每个结点的入度等于出度的入度等于出度.定义定义3 含有含有欧拉回路的无向连通图欧拉回路的无向连通图与与含有向欧含有向欧拉回路的弱连通有向图拉回路的弱连通有向图,统称为欧拉图统称为欧拉图.欧拉图及哈密顿求Euler图的Euler回路的Fleury算法.(1)(1)任意选取一个顶点任意选取一个顶点v v0 0, ,置

6、置W W0 0=v=v0 0; ;(2)(2)假定迹假定迹( (若是有向图若是有向图, ,则是有迹则是有迹) )W Wi i=v=v0 0e e1 1v v1 1eei iv vi i已经选出已经选出, ,则则用下列方法从用下列方法从E(G)-eE(G)-e1 1,e,e2 2,e,ei i 中取中取e ei+1i+1; ;(a)e(a)ei+1i+1与与v vi i关联关联( (若是有向图若是有向图, e, ei+1 i+1 以以v vi i为起点为起点) )(b)(b)除非没有别的边可选择除非没有别的边可选择, e, ei+1i+1不是不是 G Gi i=G- e=G- e1 1,e,e2

7、 2,e,ei i 的割边的割边. .(3)(3)当当(2)(2)不能执行时不能执行时, ,停止停止. .否则让否则让i+1 i,i+1 i,转转(2).(2).欧拉图及哈密顿定理定理4 4若若G G是是EulerEuler图图, ,则则FleuryFleury算法终止时得到的迹算法终止时得到的迹是是EulerEuler回路。回路。定义1 给定无向图G,若存在一条路经过图G的每个结点一次且仅一次,这条路称为哈密顿路.若存在一条闭路经过图G的每个结点一次且仅一次,这条闭路称为哈密顿回路.定义2给定有向图D,若存在一条路经过图G的每个结点一次且仅一次,这条路称为哈密顿有向路.若存在一条闭路经过图G

8、的每个结点一次且仅一次,这条有向闭路称为哈密顿有向回路.第二节 哈密顿图(1)欧拉图及哈密顿第二节 哈密顿图(1)定义3 具有哈密顿回路的无向图与具有哈密顿有向回路的有向图,统称为哈密顿图.例1对于完全图Kn(n3),由于Kn中任意两个顶点之间都有边,从Kn的某一顶点开始,总可以遍历其余节点后,再回到该结点,因而Kn(n3)是哈密顿图.说明:判断一个给定的图是否为哈密顿图,是图论中尚未解决的难题之一,下面介绍若干必要条件和充分条件.欧拉图及哈密顿第二节第二节 哈密顿图哈密顿图(2)(2)定理1设任意n(n3)阶图G,对所有不同非邻接顶点x和y,若deg(x)+deg(y) n,则G是哈密顿图.

9、证明:仅就G是无向图加以证明.假设定理不成立.则存在一个阶为n(n3),满足定理条件且边数最多的非哈密顿图,即G是一个非哈密顿图且对G的任何两个非邻接点x1和x2,图G+边x1,x2是哈密顿图.欧拉图及哈密顿 因为n3,所以G不是完全图.设u和v是G的两个顶点.因此G+边u,v是哈密顿图.且G+边u,v是哈密顿回路一定包含边u,v.故在G中存在一条uv路T=u1u2un(u=u1,v=un)包含G中每个顶点.若u1,uiE(G)(2in),则ui-1,unE(G).否则u1uiui+1unui-1ui-2u1是G的一个哈密顿回路,故对u2,u3,un-1中每一个邻接到u1的顶点存在一个u1,u

10、3,un-1中与un不邻接的顶点,故deg(un) n-1-deg(u1),所以deg(u)+deg(v) n-1矛盾.欧拉图及哈密顿第二节 (3)定理2 设u和v是n阶图G的不同非邻接点,且deg(u) +deg(v)n,则G+边u,v是哈密顿图当且仅当哈密顿图.定义4 给定n阶图G,若将图G度数之和至少是n的非邻接点用一条边连接起来得图G,对图G重复上述过程,直到不再有这样的结点对存在为止,所得到的图,称为是原图G的闭包,记作C(G).定理3 一个图是哈密顿图当且仅当它的闭包是哈密顿图.欧拉图及哈密顿定理4 设G是阶至少为3的图,如果G的闭包是完全图,则G是哈密顿图.定理5如果G是一个n阶

11、(n3)任意图,且对G的每个顶点x,都有deg(x) n/2,则G是哈密顿图.说明:由哈密顿图的定义可知,哈密顿图有向图必是强连通的,哈密顿无向图必无割点.欧拉图及哈密顿8.哈密顿图(4)定理5 若G是一个哈密顿图,则对于V(G)的每个非空真子集S, 其中W(G-S)为G-S的分支数.证明:设C是G的一个哈密顿回路,则对于V(G)的任意一个非空真子集S,均成立 由于C-S为G-S的一个生成子图,因而W(G-S)W(C-S),故 欧拉图及哈密顿9.9.哈密顿图哈密顿图(5)(5)说明:定理6只是一个必要条件,如下的皮特森图,尽管有 但它不是哈密顿图. 欧拉图及哈密顿10.10.哈密顿图哈密顿图(

12、6)(6)应用应用定理定理5.5.若若G G是一个是一个n(nn(n 3)3)阶任意图阶任意图, ,且对且对G G的的每个顶点每个顶点x,x,都有都有deg(x) deg(x) n/2,n/2,则则G G是哈密顿图是哈密顿图. .例例1.111.11个学生要共进晚餐个学生要共进晚餐, ,他们将坐成一个圆桌他们将坐成一个圆桌, ,计划要求每次晚餐上计划要求每次晚餐上, ,每个学生有完全不同的每个学生有完全不同的邻座邻座. .这样能共进晚餐几次这样能共进晚餐几次. .分析分析: :如何将该问题转化成图论中的相关问题如何将该问题转化成图论中的相关问题. .实实际上际上, ,可以这样来构造一个图可以这

13、样来构造一个图, ,即以每个学生看即以每个学生看作图的顶点作图的顶点, ,以学生的邻座关系作为图的以学生的邻座关系作为图的的边的边,欧拉图及哈密顿11.11.哈密顿图哈密顿图(7)(7)这样学生每次进餐的就坐方式就对应一个哈密顿这样学生每次进餐的就坐方式就对应一个哈密顿回路回路.两次进餐中两次进餐中,每个学生有完全不同的邻座对应着每个学生有完全不同的邻座对应着两个没有公共边的哈密顿回路两个没有公共边的哈密顿回路.因为每个学生都可以因为每个学生都可以与与其余学生邻座其余学生邻座,故问题转化为在图故问题转化为在图K11中找出所有没有中找出所有没有公共边的哈密顿回路的个数公共边的哈密顿回路的个数.

14、K11中共有中共有 条边条边,而而K11中每条哈密顿回路的中每条哈密顿回路的长度为长度为11,因此因此K11中最多有中最多有55/11=5条没有公共边的哈条没有公共边的哈密顿回路密顿回路,构造方法为构造方法为:设第一条哈密顿回路为设第一条哈密顿回路为(1,2,3,11,1),将将1固定在圆心固定在圆心,其余固定在圆周上其余固定在圆周上,如图如图(1)所示所示,然后将图的顶点旋转然后将图的顶点旋转i 3600/10(i=1,2,3,4),从从而就得到另外而就得到另外4个哈密顿回路个哈密顿回路.欧拉图及哈密顿12.12.哈密顿图哈密顿图(8)(8) 1 (3,2,4,6)5 7(5,3,2,4)

15、(2,4,6,8 )3 9(7,5,3,2) (4,6,8,10)2 11(9,7,5,3) ( 6,8,10,11)4 10 (11,9,7,5) (8,10,11,9)6 8(10,11,9,7)图图1 1欧拉图及哈密顿例2.有n个人,任意两个人合起来认识其余的n-2个人,证明:当n4时,这n个人能站成一圈,使每一个人的两旁站着自己认识的人.证明:构造简单无向图G=,其中V中的n个结点表示这n个人,G中的边表示他们间的认识关系. 对u,vV(G),显然d(u)+d(v)n-2,即其余n-2个结点必与u或v邻接.(1)若u,v相邻,则d(u)+d(v)2+n-2=n;欧拉图及哈密顿(2)若u

16、与v不相邻,如果d(u)+d(v)=n-2,则V-u,v中恰有n-2个结点(n4,故V-u,v),其中每个结点只能与u,v中的一个结点相邻.不妨设aV-u,v,且a与u相邻,a与v不相邻,此时对于结点a与u来说,都不与v相邻,这与已知矛盾,所以 d(u)+d(v)n-2,即d(u)+d(v)n-1.欧拉图及哈密顿若d(u)+d(v)=n-1,由于n4,在结点集V-u,v中至少有两个结点a和b,其中a与u和v都相邻,而b只与u和v中的一个相邻,不妨设b与u相邻,此时v与b和u都不相邻,显然与已知矛盾,因此d(u)+d(v)n-1,即 d(u)+d(v)n 综上所述,对u,vV(G),都有d(u)

17、+d(v)n,因此G中存在一条哈密顿回路,从而这n个人能站成一圈,使得每一个人的两旁站着自己认识的人.欧拉图及哈密顿 第三节第三节 并行运算图论模型与格雷码并行运算图论模型与格雷码 串行计算机串行计算机: :传统的计算机一般称为串行传统的计算机一般称为串行计算机计算机, ,即执行程序是一次完成一个操作即执行程序是一次完成一个操作. .实际实际上上, ,为解决问题而写的算法都设计成一次执行为解决问题而写的算法都设计成一次执行一步一步, ,这样的算法称为串行的这样的算法称为串行的. .到目前为止到目前为止, ,几几乎所有书本描述的算法都是串行的乎所有书本描述的算法都是串行的. . 然而在有些问题上

18、然而在有些问题上, ,如气象模拟如气象模拟, ,医学图像医学图像及密码分析等许多高强度计算问题及密码分析等许多高强度计算问题, ,即使在超即使在超计算机上计算机上, ,也不能通过串行操作在合理时间范也不能通过串行操作在合理时间范围内解决围内解决; ;而且对计算机的运行速度来讲而且对计算机的运行速度来讲, ,还还欧拉图及哈密顿存在着物理上的限制,即总有问题不能用串行操作在合理长度的时间之内解决.另外,随着硬件价格的下降,使得制造并行计算机成为可能. 并行计算机就是使用多个处理器实现在同一时间执行多条指令. 并行算法就是把问题分成可同时解决的若干子问题,其单个指令流控制着算法的执行,包括把子问题送

19、到不同的处理器,以及把子问题的输入和输出定向到适当的处理器.欧拉图及哈密顿 采用并行处理,一个处理器需要另一个处理器产生的输出.因此.处理器需要互联.用图来描述带有多重处理器的计算机里处理器的互联网络,是一种十分便利的方法,即所谓的并行运算图论模型.在第一章中介绍的n维立方体Qn中,有2n(n0)个处理器,每个处理器有自己的内存,在一个单位时间内,n维立方体中的每个处理器同时处理一条指令,然后与相邻的处理器通信.若一个处理器要与一个不相邻的处理器通信,第一个处理器要发送一些信息,这包括路径信息及接受者的最终目的地.当然这要花费数个时间段.欧拉图及哈密顿 许多计算机已经根据n维立方体Qn的模型制

20、造和运行.下面将证明n维立方体Qn中存在哈密顿回路,为此先介绍格雷码.格雷码是以弗兰克.格雷的名字命名的,在20世纪40年代,他为了把传送数字信号过程中的错误的影响降到最低而发现的.下面介绍格雷码的有关定义和构造定理.欧拉图及哈密顿l定义定义1 n 阶格雷码是序列阶格雷码是序列s1,s2,st,(t=2n),l其中每个其中每个si是是n位二进制串，满足位二进制串，满足l（1）每个）每个n位二进制串都出现在序列中；位二进制串都出现在序列中；l（2） si与与si+1只有一位不同；只有一位不同；l（3） st和和s1只有一位不同。只有一位不同。欧拉图及哈密顿定理1令G1表示序列，由Gn-1根据以规

21、则来定义Gn:（1）令 表示序列Gn-1的逆序；（2）令 表示在序列G的每个成员前加0所得的序列；（3）令 表示在序列 的每个成员前加1所得的序列；（4）令G为由 后加上 组成的序列。欧拉图及哈密顿例1从G1开始构造G3。 G 1 0 1 1 0 00 01 11 10G2 00 01 11 10 10 11 01 00 000 001 011 010 110 111 101 100G3 000 001 011 010 110 111 101 100欧拉图及哈密顿推论推论. .对于每个正整数对于每个正整数n n 2 2，n n维立方体都维立方体都包含一个哈密顿回路。包含一个哈密顿回路。0000

22、0001100110000010001110111010011001100111111111100100010111011100欧拉图及哈密顿例例2 2 证明任一个有限集合的全部子集可以这证明任一个有限集合的全部子集可以这样排列顺序使任何相邻的两个子集仅相差一样排列顺序使任何相邻的两个子集仅相差一个元素个元素. .证明证明: :设此有限集为设此有限集为A=aA=a1 1,a,a2 2,a,an n,用长为用长为n n的二进制数列对应它的的二进制数列对应它的2 2n n个子集个子集: :当且仅当当且仅当子集中含有子集中含有A A的第的第i i个元素时个元素时, ,数列的第二个数列的第二个数码为数

23、码为1,1,否则为否则为0.0.以这以这2 2n n个数列为顶点个数列为顶点, ,当且当且仅当数列仅一个同位数码相异时仅当数列仅一个同位数码相异时, ,该两顶点该两顶点间连一边间连一边, ,得到一个图得到一个图G.G.显然图显然图G G为为n n维立方维立方体体. .而而n n维立方体为哈密顿图维立方体为哈密顿图. .按照一条哈密按照一条哈密顿回路的顺序排列对应子集即可顿回路的顺序排列对应子集即可. .欧拉图及哈密顿第四节第四节 算法的时间复杂性算法的时间复杂性一个算法是有限指令的集合一个算法是有限指令的集合有限性有限性: :任何算法都会在有限条指令执行完任何算法都会在有限条指令执行完 后结束

24、。后结束。确定性确定性: :算法的每一步有精确的定义。算法的每一步有精确的定义。输入有零个或多个输入，且输入取自特定输入有零个或多个输入，且输入取自特定 的对象集合。的对象集合。欧拉图及哈密顿输出输出 : :有一个或多个输出与输入有某种特有一个或多个输出与输入有某种特定关系。定关系。唯一性唯一性 : :每一步执行后所得到的中间结果每一步执行后所得到的中间结果是唯一的，且仅依赖于输入和先前步骤的是唯一的，且仅依赖于输入和先前步骤的结果结果. .。通用性通用性: :算法适用于一类输入。算法适用于一类输入。问题是要求回答的提问通常有几个参数它问题是要求回答的提问通常有几个参数它们的值是特定的，取自定

25、义域。们的值是特定的，取自定义域。欧拉图及哈密顿问题的描述问题的描述: :是对参数进行描述，指出其解是对参数进行描述，指出其解是满足什么性质的命题。是满足什么性质的命题。实例实例 : :给问题的全体参数都指定了确定的给问题的全体参数都指定了确定的值便得到一个问题的实例。值便得到一个问题的实例。A A是问题是问题P P的算法，若算法的算法，若算法A A对问题对问题P P的每个的每个实例都给出正确答案。实例都给出正确答案。问题问题P P算法可解，若存在一个算法解答问题算法可解，若存在一个算法解答问题P P。欧拉图及哈密顿算法分析算法分析 是指通过分析得到算法所需的是指通过分析得到算法所需的时间和空

26、间的估计量。时间和空间的估计量。算法的复杂度是指执行算法所需的时间和算法的复杂度是指执行算法所需的时间和空间的量。空间的量。欧拉图及哈密顿定义定义1 1令令f f和和g g为从整数集合或实数集合到为从整数集合或实数集合到实数集合的函数，如果存在常数实数集合的函数，如果存在常数c c和和k k，使得只要使得只要x x k k就有就有 f(x)f(x) c c g(x)g(x) 则称则称f(x)f(x)是是O(g(x)O(g(x)记为记为f(x)=O(g(x)f(x)=O(g(x)读读作作f(x)f(x)是是O(g(x)O(g(x)欧拉图及哈密顿定理定理1: 1: 令令f(x)=af(x)=an

27、n x xn n +a +an-1n-1 x xn-1n-1 +a +a1 1 x+a x+a0 0其中其中a a0 0 、 a a1 1 、 a an-1n-1 、 a an n为实数，则为实数，则f(x)=Of(x)=O(x(xn n) )定理定理2 2 设设f f1 1 (x)=O(g (x)=O(g1 1 (x) (x)、 f f2 2 (x)=O(g (x)=O(g2 2 (x) (x) ，则，则f f1 1 (x) + f (x) + f2 2 (x) =O(max(g (x) =O(max(g1 1 (x) (x)、 g g2 2 (x) (x)）。）。欧拉图及哈密顿定理定理3

28、3 设设f f1 1 (x)=O(g (x)=O(g1 1 (x) (x)、 f f2 2 (x)=O(g (x)=O(g2 2 (x) (x)，则则f f1 1 (x) *f (x) *f2 2 (x) =O(g (x) =O(g1 1 (x)* g (x)* g2 2 (x) (x)。例例1 1对于正整数对于正整数n n，给出，给出n!n!和和logn!logn!的大的大O O估计估计. .解解:n!=1*2*3*n:n!=1*2*3*n n nn n, ,故故n!=O(nn!=O(nn n),),又又logn! logn! lognlognn n =nlogn, =nlogn,所以所以l

29、ogn! =O(nlogn).logn! =O(nlogn).欧拉图及哈密顿例例2 2 给出给出f(n)=3n*logn!+(nf(n)=3n*logn!+(n2 2+3)*logn+3)*logn的大的大O O估计估计, ,其中其中n n是正整数。是正整数。解解:logn!=O(nlogn),:logn!=O(nlogn),故故3n*logn!=O(n3n*logn!=O(n2 2logn)logn)所以所以f(n)= O(nf(n)= O(n2 2logn).logn).例例3 3 给出给出f(x)=(x+1)log(xf(x)=(x+1)log(x2 2+1)+3x+1)+3x2 2的大

30、的大O O估计。估计。解解: :当当x1x1时时,x,x2 2+1+1 2x2x2 2; ;当当x2x2时时,Log(x,Log(x2 2+1)+1) log(2xlog(2x2 2) ) 3logx,3logx,故故Log(xLog(x2 2+1)=O(logx),+1)=O(logx),所以所以(x+1)Log(x(x+1)Log(x2 2+1)=O(xlogx)+1)=O(xlogx)又又x1x1时时,xlogx ,xlogx x x2 2, ,所以所以f(x)=O(xf(x)=O(x2 2).).欧拉图及哈密顿复杂性复杂性术语术语复杂性复杂性术语术语O O（1 1）O(logn)O(l

31、ogn)O(n)O(n)O(nlogn)O(nlogn)常数复杂性常数复杂性对数复杂性对数复杂性线性复杂性线性复杂性nlognnlogn复杂性复杂性O O（n nk k）O(bO(bn n),b),b 1 1O(n!)O(n!)多项式复杂性多项式复杂性指数复杂性指数复杂性阶乘复杂性阶乘复杂性欧拉图及哈密顿易处理的，能用多项式最坏情况复杂性的算法解决易处理的，能用多项式最坏情况复杂性的算法解决的问题，否则称为的问题，否则称为不易处理的不易处理的. .P P问题问题: :易处理的问题易处理的问题. .NPNP问题：至今没有找到多项式算法，又不能证明它问题：至今没有找到多项式算法，又不能证明它不存在

32、多项式算法的一类问题不存在多项式算法的一类问题. .NPCNPC问题：其中任何一个问题能用一个多项式时间问题：其中任何一个问题能用一个多项式时间最坏情况算法解答的一类问题。最坏情况算法解答的一类问题。欧拉图及哈密顿例例4 4 冒泡排序冒泡排序 它把一个列表排列成升序；它把一个列表排列成升序；相继地比较相邻的元素，若它们顺序不对，相继地比较相邻的元素，若它们顺序不对，则交换它们。试分析冒泡排序则交换它们。试分析冒泡排序 的最坏时间的最坏时间复杂度。复杂度。O(nO(n2 2) )欧拉图及哈密顿 1 2 3 4 5 2 11 2 3 3 4 4 5 522 233 111 344 455 53 2

33、 2 2 2 3 3 3 4 4 4 11 1 1 4 5 5 5 54321欧拉图及哈密顿第五节 最短路路问题1.加权图:边上有数的图称为加权图;该数称为边的权。2.最短路问题:如何求两个结点之间的最短路.3.迪克斯曲拉算法:这是荷兰计算机科学教授Edsger W.Dijkstra(1930-)在1959年发现的一个算法.他在1972年获得计算机协会授予的图灵奖,这是计算机科学中最具声望的奖项. 迪克斯曲拉算法是求出一个连通加权简单图中从结点a到结点z的最短路.边i,j的权(i,j)0,且结点x的标号为L(x),结束时,L(z)是从x到z的最短路的长度.欧拉图及哈密顿4.迪克斯曲拉算法流程P

34、rocedure Dijkstra(G:所有权为正的加权连通简单图)G带有顶点a=v0,v1,vn=z和权w(vi,vj),若vi,vj不是G中的边,则w(vi,vj)=)For i:=1 to n L(vi):= L(a):=0 S:=初始化标记,a的标记为0,其余结点标记为,S是空集While zS beginu:=不属于S的L(u)最小的一个顶点 S:=SuFor 所有不属于S的顶点v If L(u)+w(u,v)L(v) then L(v):=L(u)+w(u,v)这样就给S中添加带最小标记的顶点并且更新不在S中的顶点的标记End L(z)=从a到z的最短路的长度.欧拉图及哈密顿例1.

35、用迪克斯曲拉算法求下图所示的加权图中顶点a与z之间最短路的长度.（见65页）a4b5d2110c8e263z欧拉图及哈密顿l定理1 迪克斯曲拉算法求出连通简单无向图的中两点之间的最短路的长度。l定理2 迪克斯曲拉算法使用O(n2)次运算（加法和比较）来求出n阶连通简单无向加权图中两个顶点之间的最短路的长度。l迪克斯曲拉算法可以推广到求加权有向图的最短路。（p68）l定理定理3 设有向图G中不含长度非正的有向圈，并且从点1到其余各点都有有限长的有向路，那么式（2）有唯一有限解。l定理4-5见p69.欧拉图及哈密顿Floyd算法 Dijkstra算法只求出一个特定顶点到其他各顶点的最短路.但在许多

36、实际问题中,需求出任意两点之间的最短路,如全国各城市之间最短的航线,选址问题等.Floyd算法可以比较好地解决这一问题. 为介绍Floyd算法,先定义矩阵的两种运算.定义1. 已知矩阵A=(aij)ml, B=(bij)ln,规定C=AB=(cij)mn,其中cij=min(ai1+b1j,ai2+b2j,ail+blj).欧拉图及哈密顿定义2.已知矩阵A=(aij)mn,B=(bij)mn,规定D=AB=(dij)mn,其中dij=min(aij,bij).可以利用上面定义的运算求任意两点间的最短距离.已知n阶加权简单图G,设D=(dij)nn是图G的边权矩阵即dij=w(i,j)(若G是有

37、向图,则dij=w), 若结点i到结点j无边相连时,则取dij=. 然后依次计算出矩阵D2,D3,Dn及S,其中欧拉图及哈密顿D2=DD=(dij2)nnD3=D2 D=(dij3)nn,Dn=Dn-1 D=(dijn)nnS=DD2D3Dn=(Sij)nn由定义可知,dijk表示从结点i到结点j经k边的路(在有向图中即为有向路)中的长度最短者.这就是Floyd算法. 请同学们分析一下Floyd算法的时间复杂度.欧拉图及哈密顿v121v27v6v41332v6例2.利用Floyd算法求下图中任意两点间最短有向路的长度.(p71-73) 欧拉图及哈密顿Warshall算法l实质上是考虑经过n次结

38、点转换每一次保留最短路的长度。见P74.欧拉图及哈密顿第六节旅行推销员问题和中国投递员问题（NPCNPC问题问题）一。旅行推销员问题欧拉图及哈密顿（最邻近算法最邻近算法给出旅行推销员问题的近似解）给出旅行推销员问题的近似解）步骤如下步骤如下（1 1）由任意选择的结点开始，找出于该结点邻近）由任意选择的结点开始，找出于该结点邻近的点，形成一条有边的初始路。的点，形成一条有边的初始路。（2 2）以表示最新加到这条路上的结点，从不在路）以表示最新加到这条路上的结点，从不在路上的所有结点中选一个和最靠近的结点，把连接与上的所有结点中选一个和最靠近的结点，把连接与这一结点的边加到这条路上，重复这一步骤直

39、到这这一结点的边加到这条路上，重复这一步骤直到这条路包含图中所有结点。条路包含图中所有结点。欧拉图及哈密顿例例1 1 用用“最邻近算法最邻近算法”给出下面加权图中给出下面加权图中有充分小权的哈密顿路有充分小权的哈密顿路P76.P76.AFBECD1669 7151312183513182119欧拉图及哈密顿说明: “最邻近插入方法”是“最邻近法”的一种改进方法.该方法是在每次迭代中都构成一个闭的旅行路线.求解时,在已经建立旅程以外的顶点中,寻找最临近于旅程中某个顶点的顶点,然后将其插入该旅程中,并使增加的距离尽可能小,当全部顶点收入这个旅程后,就找到了所求的最短哈密顿回路的近似解.例2用“最邻

40、近插入方法”找出上图中具有充分小权的哈密顿回路.欧拉图及哈密顿定理定理1 1 设设P P是加权连通图是加权连通图G G中一条包含中一条包含G G的所有边的所有边至少一次的闭链，则至少一次的闭链，则P P最优的充要条件（具有最小最优的充要条件（具有最小长度）是：长度）是：（1 1）P P中无二重以上的边；中无二重以上的边；（2 2）在）在G G的每个圈中的每个圈中C C中，重复边集中，重复边集E E的长度之和不的长度之和不超过这个圈的长度的一半，超过这个圈的长度的一半， 即即W W（E E） 1/2W1/2W（C C）. .二.中国邮路问题欧拉图及哈密顿奇偶点作业法奇偶点作业法（1 1）把）把G

41、 G中所有奇度顶点配成对，将每对奇中所有奇度顶点配成对，将每对奇度顶点之间的一条路上的每边改为二重边，度顶点之间的一条路上的每边改为二重边，得到一个新图得到一个新图G G1 1，新图，新图G G1 1中无奇度顶点，即中无奇度顶点，即G G1 1为多重欧拉图为多重欧拉图. .（2 2）若）若G G1 1中某对结点间有多于两条边连接，中某对结点间有多于两条边连接，则去掉其中偶数条边，留下一条或两条边连则去掉其中偶数条边，留下一条或两条边连接这两个结点，直到每对相邻结点至多由接这两个结点，直到每对相邻结点至多由2 2条边连接。得到图条边连接。得到图G G2 2. .欧拉图及哈密顿（3 3）检查）检查

42、G G2 2的每个圈的每个圈C C，若某个圈，若某个圈C C上重复边集上重复边集E E的的权和超过这个圈的权和的一半，则将权和超过这个圈的权和的一半，则将C C按定理按定理1 1必要必要性证明中的方法进行调整，直到对性证明中的方法进行调整，直到对G G2 2所有的圈其重所有的圈其重复边的权和不超过此圈权和的一半，得到图复边的权和不超过此圈权和的一半，得到图G G3 3. .（4 4）用）用FleuryFleury算法求算法求G G的的EulerEuler回路回路. .欧拉图及哈密顿例例3 3 求下图求下图G G的最优环游的最优环游p81.p81.v1v2v3v4v5v6v7v8v9v10v11

43、v122 4 5 5 3 6 4 6 4 65 4 4 7 9 3 8A欧拉图及哈密顿V1 2 v10 4 v9 5 v8 V2 6 v11 4 v12 6 v75 5 4 4 7 7V3 9 v4 3 v5 8 v6B欧拉图及哈密顿445 5 4 4 7 7993 84 8 6 4 63 6C欧拉图及哈密顿446 4 66 65 4 4 4 4 79 3 83 6D欧拉图及哈密顿444 4 3 32 4 525 3 6 466664欧拉图及哈密顿2欧拉图及哈密顿例4.设G是分划为X,Y的二分图,且则G一定不是哈密顿图.(利用分支数反证)例5.设简单图G=则G是哈密顿图.欧拉图及哈密顿证明：G中的任意两点u,v ，其度数分别为d(u),d(v)对于图G-u,v都有 m- d(u)-d(v)=Cn-12 +2 d(u)+d(v)=(n-1)(n-2)/2+2-(n-2)(n-3)/2 =n-2+2 =n由定理1 可得 G是哈密顿图。欧拉图及哈密顿