南大面试课程离散课件二24图

哈密尔顿图离散数学第24讲上一讲内容的回顾欧拉回路与欧拉图欧拉通路与半欧拉图欧拉图的充分必要条件半欧拉图的充分必要条件构造欧拉回路的Fleury算法随机欧拉图哈密尔顿图哈密尔顿回路与哈密尔顿图哈密尔顿通路与半哈密尔顿图哈密尔顿图的必要条件哈密尔顿图的充分条件寻找哈密尔顿回路旅行推销员问题(TSP)周游世界的游戏1859年英国数学家哈密尔顿提出了一种名为

“周游世界”的游戏：用一个正十二面体的二十个顶点代表二十个大城市，要求沿着棱，从一个城市出发，经过每个城市恰好一次，然后回到出发点。哈密尔顿回路和哈密尔顿通路定义：经过图G中所有顶点的初级回路称为哈密尔顿回路，若G中含哈密尔顿回路，则称G为哈密尔顿图。

定义：经过图G中所有顶点的初级通路称为哈密尔顿通路，若G中含哈密尔顿通路，但不含哈密尔顿回路，则称G为半哈密尔顿图。哈密尔顿图的必要条件注意：任何一个哈密尔顿图都可以看成是一个初级回路再加上连接该回路上顶点对的若干条边。哈密尔顿图的必要条件任何一个哈密尔顿图都可以看成是一个初级回路再加上连接该回路上顶点对的若干条边从初级回路上删除k个顶点，最多形成k个连通分支从一个哈密尔顿图中删除K个顶点，最多形成k个连通分支哈密尔顿图的必要条件任何一个哈密尔顿图都可以看成是一个初级回路再加上连接该回路上顶点对的若干条边从初级回路上删除k个顶点，最多形成k个连通分支从一个哈密尔顿图中删除K个顶点，最多形成k个连通分支向一个图中已有的顶点之间加边不会增加连通分支。因此：若G是哈密尔顿图，则对VG的任意非空真子集V1，图G-V1的连通分支数不大于V1中的元素个数。哈密尔顿图的必要条件若G是哈密尔顿图，则对VG的任意非空真子集V1，图G-V1的连通分支数不大于V1中的元素个数。证明要点：假设G-V1的连通分支数为k；模拟哈密尔顿回路C：每次离开某个连通分支，必定进入某个V1中节点每次进入的V1节点均不相同至少进入K个V1节点连通K个分支的C含有K个V1节点必要条件的应用必要条件的局限性必要条件一般只能判定一个图不是哈密尔顿图右图(Petersen图)满足上述必要条件。Petersen图不是哈密尔顿图。如何使得一个非哈密尔顿图变成哈图？边越多，越容易！所有的点的度越大越容易！也许平均度达到一定程度？也许最小度达到一定程度？顶点对度数和与图的连通只要任意顶点对的度数和足够大，图一定连通。设G是阶不小于2的无向简单图，若G中任意不相邻的顶点对u,v均满足：(条件*)d(u)+d(v)‡n-1

(n是G中顶点个数)则G是连通图。证明：假设G不连通，则至少含2个连通分支，设为G1,G2。取x˛VG1,y˛VG2,则：d(x)+d(y)£(n1-1)+(n2-1)£n-2(其中ni是Gi的顶点个数)，矛盾。将极大路径改造成回路v1v2vivkVi+1vj若图G满足条件(*),设G=v1v2…vk-1vk是G中不含所有顶点的极大路径(k<n),

则G中所有顶点可构成初级回路。若v1,vk相邻，结论成立。若v1,vk不相邻，令S={vi|v1与vi+1相邻},T={vj|vj与vk相邻}注意：|S|=d(v1)，|T|=d(vk)极大路径使然|S|+|T|=

d(v1)+d(vk)

‡n-1意味着什么？|S|+|T|=

d(v1)+d(vk)‡n-1若图G满足条件(*),设G=v1v2…vk-1vk是G中不含所有顶点的极大路径(k<n),则G中所有顶点可构成初级回路。v1vivi+1vkv2vkˇS T,

\|S

T|£k-1<n-1,而根据容斥原理|S

T|=|S|+|T|-|S T|>0,

即S T非空令vi˛S

T,

则vi+1与v1相邻，vi与vk相邻。于是C=v1…vivkvk-1…vi+1v1是包含G中所有顶点的初级回路。半哈密尔顿图的充分条件v1vivi+1vkvj-1

vj条件*是半哈密尔顿图的充分条件。可以证明：若条件*成立，图中的最大路径一定是哈密尔顿通路。假设G=v1v2…vk-1vk是一条最大路径，但k<n,则可以将它改造为一初级回路C。设vk+1是C以外的顶点。因为G是连通图，vk+1与C中的顶点必有通路，设其中最短路径与G的交点是vj(显然异于v1,vk)。则

G

‘=vk+1…vj…vivk

vk-1…vi+1v1…vj-1是通路G的扩大。矛盾。vk+1哈密尔顿图的充分条件G是阶不小于3的无向简单图，若G中任意不相邻的顶点对u,v均满足：d(u)+d(v)‡n

(n是G中顶点个数)，则G是哈密尔顿图证明：G是半哈密尔顿图，设G=v1v2…vn-1vn是G中的哈密尔顿通路。若v1,vk

相邻，结论成立。否则，令S={vi|v1

与vi+1

相邻}，T={vj|vj与vk相邻}；注意：|S|+|T|=d(v1)+d(vn)‡n,vnˇS T,

\

|S

T|£k-1<n,

\

|S

T|=|S|+|T|-|S T|>0,

即S

T非空，令vi˛S T,

则vi+1与v1相邻，vi与vn相邻。于是C=v1…vivnvn-1…vi+1v1是哈密尔顿回路。v1vivi+1vnv2有关哈密尔顿图充分条件的讨论为什么前提条件中必须包括n‡3，而对半哈密尔顿图只需要n‡2不相邻节点显然：d(v)‡n/2是d(u)+d(v)‡n的充分条件，因此，也是哈密尔顿图的充分条件加边总可以使非哈密尔顿图变成哈密尔顿图，(而且，这过程中一定存在一个临界状态)。但是：如果只在满足d(u)+d(v)‡n

的u,v之间加边，图的哈密尔顿性质不会改变。棋盘上的哈密尔顿回路问题在4·4或5·5的缩小了的国际象棋棋盘上，马

(Knight)不可能从某一格开始，跳过每个格子一次，并返回起点。安排考试日程问题:在6天里安排6门课–A,B,C,D,E,F-的考试，每

天考1门。假设每人选修课的情况有如下的4类：DCA，BCF，EB，AB。如何安排日程，使得没有人必须连续两天有考试？ABCDEFABCDEF再安排考试七天内安排七门课的考试，要求同一个老师教授的课程不要连续安排。试证明：如果没有教师同时教授4门及以上课程，这种安排是能实现的。点代表什么？线代表什么？问题是什么？旅行推销员(TSP)问题问题：n个城市间均有道路，但距离不等，旅行推销员从某地出发，走过其它n-1个城市，且只经过一次，如何选择最短路线？数学模型：构造无向带权图G，VG中的元素对应于每个城市，EG中每个元素对应于城市之间的道路，道路长度用相应边的权表示。则问题的解对应于G中包含所有边的权最小的哈密尔顿回路。G是带权完全图，总共有n!/2条哈密尔顿回路。因此，问题是如何从这n!/2条中找出最短的一条。(给你一点感觉：含20个顶点的完全图中不同的哈密尔顿回路有约

6000万亿条-(1.21645·1017)/2，若机械地检查，每秒处理10万条，需2万年。)TSP:

一个并非最佳的近似算法过程找“较好的”哈密尔顿回路(总选关联的最小权边)改进：如果在已有回路中W(vi,vj)+W(vi+1,vj+1)<W(vi,vi+1)+ W(vj,vj+1),则分别用边vivi+1和vjvj+1替代vivj和vi+1vj+1。abce1412967851311d10从a

出发的“较好的”回路，长度：8aa40dceb7

6591410aadceb765910经改进的回路

，长度：37作业pp.303-8-111420Sir

WilliamHamilton(1805-65)爱尔兰历史上最伟大的科学家。关于哈密尔顿早期的才能的传说，读起来象一篇拙劣的虚构的故事，但它是真实的。(例如，在十岁时，他差不多掌握了大多数主要东方语言)哈密尔顿在进大学以前从未上过学…(他)轻而易举地取得第一名，进入三一学院。…大学生涯的结束，比它开始还要更令人惊奇；…都柏林大学理事会一致选举当时22岁的大学生哈密尔顿为教授。在23岁时，他发表了他还是一个17岁的孩子时作出的“奇怪的发现”，…即《光线系统理论》第一部分，这是一篇伟大的杰作，它对于光学，就象拉格郎日的《分析力学》之于力学。哈密尔顿最深刻的悲剧既不是酒精，也不是他的婚姻，而是他顽固地相信，四元数是解决物质宇宙的数学关键。…从来没有一个伟大的数学家这样毫无希望地错误过。摘自贝尔：《数学精英》“我长期以来欣赏托勒密对他伟大的天文学大师希巴克斯的描绘：‘一个热爱劳动和热爱真理的人’。但愿我的墓志铭也如此。”-威廉•哈密尔顿闭合图定义：图G中任意不相邻u,v˛VG,d(u)+d(v)‡|VG|。令

G’=G+e(u,v).不断重复该动作，直至找不到u,v节点。则最终结果称为G的闭合图，记为C(G)。注意：可以认为C(G)是在G的基础上不断在满足d(u)+d(v)‡|VG|的顶点对之间加边所得。图G的闭合图是唯一的设G1,G2

均为G的闭合图，其构造过程中加的边依次为e1,e2,…em和f1,f2,…fn。假设ek+1=uv是第一个不在G2中的边，则H=G+{e1,e2,…ek}同为G1,G2的子图。在构造G1时加ek+1说明在H中u,v不相邻，且d(u)+d(v)‡|VG|,显然该条件在G2中也成立，矛盾。闭合图与哈密尔顿图的判定图G是哈密尔顿图当且仅当C(G)是哈密尔顿图。只须证明在构造闭合图(加边)过程中的每一步，图的哈密尔顿性质均双向保持若u,v˛VG,u,v不相邻，且d(u)+d(v)‡|VG|，则G是哈密尔顿图当且仅当G+e(u,v)是哈密尔顿图。必要性显然。反之，若G+{uv}是哈密尔顿图，但G不是，则G是半哈密尔顿图，且uv-路径是哈密尔顿通路，由

d(u)+d(v)‡|VG|，可以将uv-路径改造成哈密尔顿回路，