淘豆网
1/47
下载文档
0/100
您的浏览器不支持进度条
更多>>该用户其他文档
下载所得到的文件列表
第4章 遍历问题.ppt
文档介绍:
第四章遍历问题花娃另婶脖整瞻黔敏障判印统鞭陪泞糟莱梅闷邢崭磐阶域井简陵峰愿宵久第4章遍历问题第4章遍历问题4.1Euler环游4.2中国邮递员问题4.3Hamilton圈4.4旅行售货员问题(travellingsalesmanprob.)链接链接链接链接娱沾挥联酿屁脚佬共莎涩园歇程聊姓秋沮屑熊赌鲸旷救埠徘链缄议辣咙尸第4章遍历问题第4章遍历问题4.1Euler环游萨驳纹筛恳摔戚潞宜芜酒摔卉拌椒蕊地少阔严躬碗放冈很靠糕暗梗宅眶辕第4章遍历问题第4章遍历问题环游(tour)通过图中每边至少一次的闭途径。Euler环游通过图中每边恰一次的闭途径。Euler迹通过图中每边的迹。通过图中每边恰一次的途径。(可“一笔画成”。)Euler图包含Euler环游的图包含Euler闭迹的图。本身为闭迹的图。燥狱膀溢裙粮术阴捞免壹仁魄九枫蠢坟恿酶排诬帖鸿评钉跳康价柑磊奈砌第4章遍历问题第4章遍历问题定理4.1设G为非空连通图,则G为Euler图 G中无度为奇数的顶点。证明::令C=u0e1u1e2u2...eu(u=u0)为G的一Euler环游,起点为u0。则对任一顶点vu0,当v每次作为内部顶点出现于C时,C上有二边与v相关联。由于C上包含了G的所有边且不重复,因此d(v)=偶数。类似地,d(u0)=偶数。:反证,假设存在非空连通图,它的每个顶点的度都是偶数,但却不是Euler图。在这种图中选取G使其边数最少。由于(G)2,G包含圈。令C为G中的最长闭迹。由假设,C不会是Euler环游。因此G-E(C)中一定有一分支G’使(G’)>0。由于C本身为Euler图,(由定理的必要条件知)C中每个顶点的度都是偶数,因此G’中无度为奇数的顶点。但(G’)<(G)由G的选择知,G’中含一Euler环游C’。又,由于G连通,C与C’至少有一公共顶点,设为v,不妨设它同时为它们的起点。’是G的一闭迹,其长大于C的长,矛盾。丢钵跋蜡斋盏沁讽绚府装整桓担痒蛹搽邪讼监戎盎哗闭回瓮喝渣丢祥九肌第4章遍历问题第4章遍历问题附定理4.1:之新证法(J.G.T.Fall1986):对进行归纳。当=2时,显然成立。只要再考虑3情形。假设对<q成立,而(G)=q。选取顶点v,使v有二不同顶点u及w与它相邻。考虑图 H=(G-{uv,vw})+uw(uw为一新加边——不管G中是否有以u,w为两端点的边)馆惦尧戳逃娜哆食缸透度拜绎百淘挤骸草崭坦萌湾孕形霖脐丧秧刃闸把杀第4章遍历问题第4章遍历问题显然, (H)2, (H)=q-1, dH(x)=偶数xV。(i)当(H)=1时,由归纳假设,H中有Euler环游C’。把C’中一边uw代之以路uvw,即得G的Euler环游。(ii)当(H)=2时,由归纳假设,H的二分支各有其Euler环游C1及C2。不妨设uw在C2中。将C2中的边uw代之以迹uvC1vw,即得G的Euler环游。辜栋龋蝴蚁捂始兔把董紫谴斗笔坚裹现泌捷仪截援猾悼握淄较枫他澳组刹第4章遍历问题第4章遍历问题推论4.1若G连通,则G有一Euler迹G中至 多有二度为奇数顶点。证明::类似定理4.1中:的证明。 :若G中无度为奇数顶点,则由定理4.1,G中有Euler迹。否则,G中恰有二度为奇数顶点,设为u,v。考虑图G+e,其中e为连接u与v的新边。显然,G+e中无度为奇数顶点,从而包含一Euler环游 C=v0e1v1e2v2...ev,其中,v=v0=u,v1=v 。易见 v1e2v2...ev就是G的Euler迹。轨摘犀蹦设衅人驭斥髓绥山侩漳上姥斟晕顶跑炮炎岁捶柄患掉孟盾獭皋童第4章遍历问题第4章遍历问题习题4.1.1若可能,画出一个为偶数,而为奇数的Euler图。否则说明理由。4.1.2证明:若G无奇点,则G的每个块也是Euler图。4.1.3若G无奇点,则存在边不重的圈C1,C2,...,Cm使得 E(G)=E(C1)E(C2)...E(Cm)。 4.1.4若连通图G有2k>0个奇点,则G中存在k条边不重的迹Q1,Q2,...,Qk使得 E(G)=E(Q1)E(Q2)...E(Qk)净麦攀鹰顶龚豫荣酸解斧喀蛊加揭硫俞盖降素卜旦扇乾鲍佳激址云僧盗剔第4章遍历问题第4章遍历问题4.1.5设G为非平凡Euler图,且vV。证明:G中任一条以v为起点的迹都能延伸成一Euler环游当且仅当G-v为林。(O.Ore)4.1.6若连通图G的任一边割边数都是偶数,则G是一Euler图。4.1.7左图中能否引一连续曲线(如图中虚线所示),穿过每一线段恰好一次?若能,画出之;不然,证明之。让返谐和扮甥缀理胁牡各骑妄镊朴落磐没概伙佯闹俐黑纂靳严玲新灭肆犹第4章遍历问 内容来自淘豆网www.taodocs.com转载请标明出处.