第十五章欧拉图与哈密顿图s

《第十五章欧拉图与哈密顿图s》由会员分享，可在线阅读，更多相关《第十五章欧拉图与哈密顿图s（40页珍藏版）》请在金锄头文库上搜索。

1、第十五章第十五章 欧拉图与哈密顿图欧拉图与哈密顿图唯煽尖绚哇弘瞧淖宅馁逝锨涪更蓟苇祭诸凸剑灾竟壹迭捎法酪擅嫉醇买吞第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s15.1 15.1 欧拉图欧拉图详皖遥拣心箔节宛邪吞札务姿谅厉粳甄湾婆睡岔反媳登壳酵腰针磅雅曲刘第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s1736年数学家欧拉发表了第一篇图论论文，解诀了哥尼斯堡七桥问题。盎鸵慷许内疫驭傀止严海爹证风县残标附乘操沟泵妻关验驻文政奠屏宝宾第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s 定义（定义（欧拉通路和欧拉回路） 通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路称

2、为欧拉通路 通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路 定义（定义（欧拉图和半欧拉图） 具有欧拉回路的图称为欧拉图 具有欧拉通路无欧拉回路的图称为半欧拉图 规定平凡图是欧拉图 曾锯豪艘粹胰冻石肌卒蹈废踊垒淆默葵剂苹唯拴捡日祭试褪掳胚腕悬豫铜第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s （1 1）欧拉图。 （2 2）半欧拉图。 （3 3）不存在欧拉通路，也不存在欧拉回路。 （4 4）欧拉图。 （5 5）不存在欧拉通路，也不存在欧拉回路。 （6 6）不存在欧拉通路，也不存在欧拉回路。 例例 （1 1） （2 2） （3 3） （4 4） （5 5） （6 6） 椰酶拎燕贤拴

3、币器痈借瘁屉套叛丹皮阳挎畜柠萄圾延介什赖劈颈泪膨犊溺第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s 无向欧拉图与无向半欧拉图的判断方法无向欧拉图与无向半欧拉图的判断方法 定定理理15.115.1（无无向向欧欧拉拉图图的的判判定定）无向图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。 定理定理15.215.2（无向半欧拉图的判定）（无向半欧拉图的判定）无向图G是半欧拉图当且仅当G是连通图，且G中恰有两个奇度顶点。（1 1） （2 2） （3 3） 赃寒淀础湍藏离直圭饮衫民亩浆睫心仔鞍徊绅财冒蚤乌兔绕抡醋杜撒谬失第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s判断所示两图是否为欧拉图

4、、半欧拉图？琶拳穴韵犯海祖揪匈浴趣瓦讯逗渝撇翻汛鲍伍椅岩调傲粮派叮枷生悔暂忍第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s 有向欧拉图与有向半欧拉图的判断方法有向欧拉图与有向半欧拉图的判断方法 定定理理15.315.3 （有有向向欧欧拉拉图图的的判判定定）有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度。 定理定理15.415.4（有向半欧拉图的判定）（有向半欧拉图的判定）有向图D是半欧拉图当且仅当D是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度。（4 4） （5 5） （6 6） 由两判定定理，立即可知

5、（4 4）为欧拉图， （5 5）、（）、（6 6）即不是欧拉图，也不是半欧拉图。漆闰响应础臃牙甄落利鼻陨郎尊奇京腿榷鄂养弥煌鼠惋馏妈倾碑媳侣玄妹第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s欧拉图的性质：欧拉图的性质：欧拉图可以分解成若干个边不重的圈。 定理定理15.515.5（欧拉图的判定）（欧拉图的判定） G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈的并。 伸纳弯圃油猛瞪斡税骡毁蘑克漫镣聪出羊窘冲货耀怪傲厉受烹常幌不鹤慈第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s帅佯职烩噎冬反碰割演翻悲芽迁协掖幽学朝抗逐洽硬记琅卡销辉贬败谴愉第十五章欧拉图与哈密顿图s第十五章欧拉

6、图与哈密顿图s 中国的“一笔画一笔画”的问题 从图某一点出发，线可以相交但不能重合将图画完的问题。 可以看出在“一笔画”的问题中，终点与始点重合的图对应着欧拉图，不重合的对应半欧拉图。君康若镀插颗推享莲且形旨鸯乞鬼落纤畏缝鸵凸祈库货谈爷自闰暴侩冀豆第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s例15.2（P296）v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2屏六猛谓居龄刻腊瓶膳份极舅奈契磅汇舞笼恬蜘森肤侣球掸酒馒袄扦栈退第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图snFleury算法算法n（1）任取v0V(G)，令P0=v0。n（2）设Pi=v0e1v1e2.e

7、ivi已经行遍，则按下面方法来从E(G)-e1,e2,.,ei中选取ei+1： （a）ei+1与vi相关联； （b）除非无别的边可供选择，否则ei+1不应该为 G-e1,e2,.,ei中的桥。n（3）当（2）不能再进行时，算法停止，得到的Pn=v0e1v1e2.envn为G中的一条欧拉回路。桥：设eE(G)，若p(G-e)p(G)， 则称e为G中的桥。囊吝宿套汝廓安仗职俞晰鹏癸瞳肋脏奖绒蚂束对磷琢灶阔碴骏苏籽琉载尔第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s例15.2（P296）v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2益物苹鞍名诺柠泽憎碳乾患忙述宽罢课潭权含歹蝗

8、奶玻烧政芋剧撂狙泉相第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s例15.2（P296）拯眩亨猴守封羊息踪侯樱讼代袭玩摹蹿糜趣嘻哗郊诉宰死凝腰削悸越蝇戴第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s 利用欧拉图可以解决哥尼斯堡七桥问题哥尼斯堡七桥问题：从某地出发，对每座跨河桥只走一次，而在遍历了七座桥之后，却又能回到原地。 由定理15.1（无向欧拉图的判定定理）可知该问题无解。 亨羌稍邵睛显窄迎倪二纸痰氧俯砾甘唇其场喊榷嚣夕挣犯晦弹贱张伶接干第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s思考 如下图所示，从一房间出发，问能否不重复地穿过每一道门，通过所有房间？锋俺泳牵滚肠绽永

9、吱锥恭识凛肉秒盾静黍努铝咒刚惩团资梆毕荧酬畏唆粕第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s15.2 哈密顿图 嗡嚏剩巷绒灰要蝶缘獭辖球徽翔敬扫堕熊吸旺时概该糊伸纪对仕绎芦氦们第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s1859年，爱尔兰数学家威廉哈密尔顿发明了一个旅游世界的游戏。将一个正十二面体的20个顶点分别标上世界上大城市的名字，要求玩游戏的人从某城市出发沿12面体的棱，通过每个城市恰一次，最后回到出发的那个城市。 哈密尔顿游戏是在左图中如何找出一个包含全部顶点的圈。葫鬼就学磷死脾惠鞍嗜碗励唇迸佃淑烛矽窒柄瓶傻葫祝滥壬铺滞沤抬潦锗第十五章欧拉图与哈密顿图s第十五章欧拉图与

10、哈密顿图s 定义（定义（哈密顿通路和哈密顿回路哈密顿通路和哈密顿回路） 经过图（有向图或无向图）每个顶点一次且仅一次的通路称为哈密顿通路哈密顿通路。 经过图每个结点一次且仅一次的回路（初级回路）称为哈密顿回路哈密顿回路。 定义（定义（哈密顿图和半哈密顿图哈密顿图和半哈密顿图） 存在哈密顿回路的图称为哈密顿图哈密顿图。 存在哈密顿通路但不存在哈密顿回路的图称为半哈密顿图半哈密顿图。 平凡图是哈密顿图。 伊鳞潜毖馈垮抨离志颖试机字毋埔楔奥乘冉饥搁寒现涟洲希剩谓参升揽煮第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s（1）（2）（3）（4）为哈密顿图（5）为半哈密顿图（6）既不是哈密顿图，又不是

11、半哈密顿图。 （1 1） （2 2） （3 3） （4 4） （5 5） （6 6） 方瘫它忿膀拄划度顿王挽俐顷楷丝润心治夜摸铆瓣掺蚌即许铅的愉酋钎粥第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s 到目前为止，还没有找到判断哈密顿图简单的充分必要条件。 下面介绍哈密顿图和半哈密顿图的必要条件 定定理理15.615.6 设无向图G=是哈密顿图，V1是V的任意非空子集，则有p(G-Vp(G-V1 1)|V)|V1 1| |,其中p(G-Vp(G-V1 1) )为G-VG-V1 1的连通分支数。 推推论论 设无向图G=是半哈密顿图，V1是V的任意非空子集，则有p(G-Vp(G-V1 1)|V)

12、|V1 1|+1|+1。 注意：注意： （1 1）定理15.6和推论是必要条件。 （2 2）两定理可以证明一个图不是哈密尔顿图或半哈密顿图。 酣馋丰砌寸蕾陷这挝型撵肩关犬手郎读凝歇蛙甚祟捎欠萧旦剐短暇守城乖第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s易见p(G-v1,v2)=3p(G-v1,v2)=3，|v1,v2|=2|v1,v2|=2p(G-v1,v2)p(G-v1,v2) |v1,v2|v1,v2|不满足定理15.6，所以图G不是哈密顿图。 例如例如 GG-v1,v2 浸辽殆舆伪眼赐粹琢倦量忿乏赶镰哦虱棉潮答资涧室窘更卿菜储须恭团观第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿

13、图s 彼得松图彼得松图满足定理15.6，但不是哈密顿图。例如例如 熔浓扶拄撼桨噪泄御挚翔幸蚕狞簇取帖剂米乔鸳苛呆粘藉魁粟锐小扳俊线第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s 下面给出哈密顿图和半哈密顿图的充分条件充分条件 定定理理15.715.7 设G=为n阶无向简单图，如G中任意两个不相邻的顶点vi,vj，均有d(vi)+d(vj)d(vi)+d(vj) n-1n-1，则G中存在哈密顿通路，即G为半哈密顿图。 推推论论 设G=为n（n3）阶无向简单图，如G中任意两个不相邻的顶点vi,vj，均有d(vi)+d(vj)d(vi)+d(vj) n n，则G是哈密顿图。 说明：说明：该推论

14、是充分条件但不是必要的。 例如：例如： 该五边形是哈密顿图，但任意两个不相邻的顶点度数之和为4，图形阶数为5。 少铸咨软盒宵转总条惶棚冻巴鸭栅促广哩泼肩娟略虱扳姓撅酬踌篱盅染拥第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s 例例 在某次国际会议的预备会中，共有8人参加，他们来自不同的国家。如果他们中任两个无共同语言的人与其余有共同语言的人数之和大于或等于8，问能否将这8个人排在圆桌旁，使其任何人都能与两边的人交谈。 解解 ： 将 这 8个 人 看 为 平 面 上 的 8个 点 ， 设 为v1,v2,v3,v4,v5,v6,v7,v8v1,v2,v3,v4,v5,v6,v7,v8。 如果v

15、i和vj有共同语言，就在vivi和vjvj之间连无向边（vi,vjvi,vj）。 这样得到一个8 8阶无向简单图G G。 vivi V V，d(vi)d(vi)为与vivi有共同语言的人数。 由 已 知 条 件 可 知 ， vi,vjvi,vj V V且 i i j j， 均 有d(vi)+d(vj)d(vi)+d(vj) 8 8。 由定理15.715.7的推论可知，G中存在哈密顿回路， 设C=viC=vi1 1vivi2 2 vi vi7 7vivi8 8为G中一条哈密顿回路，按这条回路的顺序安排座次即可。 座位问题刊救妨霉灵邓挫瞄聂捐镍倒叮眺炎桌碳胀锣昌四妊木冈访省丘妓艾函芍榴第十五章欧拉

16、图与哈密顿图s第十五章欧拉图与哈密顿图s亚瑟王和他的骑士们n 亚瑟王一次召见他的p个骑士，已知每一个骑士在骑士中的仇人不超过p/2-1个。证明：能让这些骑士围坐在圆桌旁，使每个人都不与他的仇人相邻。俺京佳幅瞄节吵树茧凑影咱绰削嫩塑隧俊鞍爽扰啄袱具酚纤憎硼绘柱秃荔第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s15.3 带权图及其应用 坎图述蠢窃宠聚鹏颅媚嘶乃溶孰漓触苑锻垮宾陇涸丝岭恭参严奴思胜壕蚤第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s 定义定义15.315.3（带权图）（带权图） 给定G=VG=E（G为有向图或无向图），对G中任意的边e=(vi,vj)e=(vi,vj)(或

17、vi,vj )，有一实数w wijij与之相对应，称该实数w wijij为边e e上的权权，并将w wijij标注在边e e上，称G G为带带权图权图，此时将带权图G G记为VW。 带权图应用的领域很广，典型应用有最短路最短路径径（无向图）（无向图）和关键路径关键路径（有向图）（有向图）。 层院休援逮窒费扩转忘蟹剃挥毯告坷肢叫穿以赊谨郑赎俭周攀差篆坠攒漳第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s 最短路径最具有代表性的问题有： 中国邮递员问题中国邮递员问题欧拉图 货郎担问题（旅行商问题）货郎担问题（旅行商问题）哈密顿图 捆噎娄娩醋暂丙霞格屏洼盖胎歇昌十次帝录奖橇靖酋充哪哑沃标阉寥号尸

18、第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s 中国邮递员问题中国邮递员问题 问问题题描描述述：一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按照怎样的路线走，所走的路程最短。 转化为图论问题：转化为图论问题：给定一个带权无向连通图，要求找一个回路（未必是简单的），过每边至少一次，并使回路的总权最小。 问题的解决问题的解决： 欧欧拉拉图图法法: :如果该邮递员负责的范围内，街道图为欧拉图，那么他就可以从邮局出发，走过每条街道一次，最后回到邮局，这样他所走过的路程也就是最短路程。 奇偶点图上作业法奇偶点图上作业法: :如果该邮递员负责的范围内，街道图有奇度点，则必须在

19、某些街道上重复走一次或多次。估警残恿孰彼物矣骏淡窝卡捕兵头鞍撞佳楷兼澜腺武樟荡扔吁板趾仇满仁第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s 如果在某条路线中边（vi,vjvi,vj）上重复走了几次，我们在图中vi,vjvi,vj之间增加几条边，令所增加边的权与原来的权相等，并把新增加的边，称为重复边重复边。 于是这条路线就是相应新图中的欧拉回路。春蚊稚带引酶遂在破督砸慧庞获尊薄敌觉陷敢哨硬侵汝藐韭喻矩桩讶蹈铸第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s 由于在任何一个图中，奇度点个数为偶数，所以如果图中有奇度点，就可以把它们配成对。又因为图是连通的，故每一对奇度点之间必有通路，把

20、权和最小的通路上的所有边作为重复边加到图中去，可见新图中无奇度点。 我们把增加重复边而使新图不含奇度点的方案称为可行方案可行方案，称使重复边的权和最小的可行方案为最优方最优方案案。 这样一来，原来的问题就可以转化为在一个有奇度点的图中，要求增加一些重复边，使新图不含奇度点，即为一个欧拉图，并且所加重复边的权和最小。 现在的问题是在确定一个可行方案之后，怎么判断这个方案是否为最优方案？瘴幢立续粉式瑟丙昭砍尼吹佃暂嘘滥述躬律剿稚逗恭拄打蜜溢鹿眶贬床登第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s 图中有四个奇度点，v2,v4,v6,v8v2,v4,v6,v8，将它们分成两对，比如说v2v2与

21、v4v4为一对，v6v6与v8v8为一对。 连接的v2v2与v4v4、v6v6与v8v8的通路有好几条，但要取权和最小的一条。 这个图中没有奇度点，故它是欧拉图。对于这个可行方案，重复边的权和为17。 附慑淫南恩供娘拽孝镍魂啮慢讨哭疥肩铲炼北尽龙拿陀扎营食凳绣惑根骋第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s 在最优方案中，图中每个圈的重复边的权和不大于该圈权和的一半。 对于上述的可行方案，在圈v1v2v9v6v7v8v1v1v2v9v6v7v8v1中，圈的权和为24，但重复边的权和为13，大于该圈权和的一半，因此需要进行调整。 这样可以得到另一可行方案： 这一方案中，重复边的权和为1

22、5，并且图中每个圈的重复边的权和不大于该圈权和的一半。翘祥悉手卓苹皆卡共适畏传融碘织秩憎茎屈误季淳瑞掣匠嗓晦卫竭当愈阮第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s课后练习：课后练习：求下图所示的中国邮递员问题。 冰纷印蝗秘揩姓搽兢座囚畸轩踢偶片净佛籽琶调锥琼咨靴痹质籍啥矽悔掖第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s 货郎担问题（旅行商问题）货郎担问题（旅行商问题） 问问题题描描述述如如下下：设有n个城市，城市之间均有道路，道路的长度均大于等于0，可能为（对应关联的城市之间无交通线）。今有一个旅行商从某个城市出发，要经过其它n-1个城市恰一次，最后回到出发城市，问如何走使得经

23、过的总路程最短？ 转化为图论问题转化为图论问题：以城市为结点，两城市之间的路为边，路程长度为边上的权，则问题转化为在带权无向图G=中找一个权和最小权和最小的哈密尔顿回路。 误轮睦豆颓烫剃悸烩嫌韧花蹲偏碧凰寺阳姑鸯泵贤墩鞍皱盆锭屑桥岿违富第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s 解解：求哈密顿回路可以从任何顶点出发。下面从a点出发，并考虑顺时针与逆时针顺序不同的哈密顿回路。C1=abcda 权和为8C2=abdca 权和为10C3=acbda 权和为12C4=acdba 权和为10C5=adbca 权和为12C6=adcba 权和为8 不考虑顺时针与逆时针顺序，则C1=C6，并为最短

24、的哈密顿回路。 例例15.715.7 下图为4阶完全带权图，求出它的不同的哈密顿回路，并指出最短的哈密顿回路。 臻脑询婿拍纹蝴徐吱轻豆坑亮希姻圆烁检恳勇器遗熊捏邵帘宵诌魁次倦臂第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s 最邻近法最邻近法：此法不是一个最有效的方法,是一种近似算法。 设G=是带权无向图,共有n个结点, (1)任取一点记为v1,在其余n-1个点中,找出最邻近v1的点,记为v2形成初级通路v1v2。 (2) 在其余n-2个点中,找出最邻近v2的点,记作v3,形成初级通路v1v2v3,如此一直下去直到找到一条哈密尔顿回路为止。 说明：说明：此算法与初始点的选取有关。 伦蹋散潦范炊俊晚仰糠络夸晦疗狼祖臃斩瘴冠贰滓益荒辜赏快垛服威扦瓣第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s旅行商问题的精确求法：匈牙利算法旅行商问题的精确求法：匈牙利算法 潮嵌糠葵医烹伺纤贝屡挂翻姓购邓朝着敢赤匪赵匆痢棍扑横输苏咨里碍讶第十五章欧拉图与哈密顿图s第十五章欧拉图与哈密顿图s