5汉密尔顿图

周游路线1123456782骑士周游路线(knight’stour)骑士周游路线(knight’stouronachessboard)3周游世界SirWilliamRowanHamilton,1857,Icosiangame:是否存在一条回路，使它含有图中的所有顶点一次且仅一次？4汉密尔顿图1.周游世界,汉密尔顿通(回)路,汉密尔顿图2.判定汉密尔顿图的必要条件3.判定汉密尔顿图的充分条件4.旅行商问题5WillamRowanHamiltonWillamRowanHamilton(1805~1865):爱尔兰神童(childprodigy),三一学院(TrinityCollege),光学(optics)1827,AstronomerRoyalofIreland.1837,复数公理化,a+bi,(a,b)四元数(quaternion):a+bi+cj+dk,放弃乘法交换律!6骑士周游路线(knight’stour)LeohardEuler,1759,详细分析7汉密尔顿图(Hamilton)汉密尔顿通路(Hamiltonpath):经过图中所有顶点的初级通路汉密尔顿回路(Hamiltoncircuit/cycle):经过图中所有顶点的初级回路汉密尔顿图(Hamiltonian):有汉密尔顿回路的图半汉密尔顿图(semi-Hamiltonian):有汉密尔顿通路但没有汉密尔顿回路的图8汉密尔顿图(Hamilton)的思考什么样的图是汉密尔顿图？K3,3K5n阶简单图是汉密尔顿图，要求m≥n——要有尽可能多的边9无向汉密尔顿图的性质G是汉密尔顿图，则存在汉密尔顿回路Cp(C-{v1})p(C-{v1,v2})p(C-{v1,v2,v3})10无向汉密尔顿图的必要条件定理3:设G=V,E是无向汉密尔顿图,则对V的任意非空真子集V1有p(G-V1)|V1|证明:设C是G中任意汉密尔顿回路,当V1中顶点在C中都不相邻时,p(C-V1)=|V1|最大;否则,p(C-V1)|V1|.C是G的生成子图,所以p(G-V1)P(C-V1)|V1|.#11无向半汉密尔顿图的必要条件推论:设G=V,E是无向半汉密尔顿图,则对V的任意非空真子集V1有p(G-V1)|V1|+1证明:设P是G中任意汉密尔顿通路,当V1中顶点都在P内部且都不相邻时,p(P-V1)=|V1|+1最大;否则,p(P-V1)|V1|.P是G的生成子图,所以p(G-V1)p(P-V1)|V1|+1.#12推论(证明二)推论:设G=V,E是无向半汉密尔顿图,则对V的任意非空真子集V1有p(G-V1)|V1|+1证明二:设P是G中任意汉密尔顿通路,两个端点是u与v.令G1=G(u,v),由定理3有p(G-V1)p(G1-V1)+1|V1|+1.#13反例:非充分条件定理3只是必要条件,而不是充分条件反例:Petersen图Petersen图满足:V1,p(G-V1)|V1|Petersen图不是汉密尔顿图:穷举Petersen图是半汉密尔顿图14二部图与汉密尔顿图-例1bafe二部图{a,f}和{b,c,d,e}dc15二部图与汉密尔顿图-例2bacdefghijk二部图{b,d,f,h,j}和{a,c,e,g,i,k}半汉密尔顿图16二部图与汉密尔顿图-例3bcdefghij二部图{a,c,g,i,e}和{b,d,f,h,j}汉密尔顿图a17二部图与汉密尔顿图设二部图G=V1,V2,E,|V1||V2|,|V1|2,|V2|2G是汉密尔顿图，则|V1|=|V2|；G是半汉密尔顿图，则|V1|=|V2|-1或|V1|=|V2|；|V2||V1|+2，则G不是半汉密尔顿图，也不是汉密尔顿图18无向半汉密尔顿图的充分条件定理4:设G是n(2)阶无向简单图,若对G中任意不相邻顶点u与v有d(u)+d(v)n-1则G是半汉密尔顿图.证明:(1)G连通(2)由极大路径得圈(3)由圈得更长路径路径--极大路径--圈--更长路径---更长极大路径--更长圈--更长路径--……--汉密尔顿通路（构造法）19极大路径是一条路径，如果的始点和终点都不与外的顶点相邻，则称是一条极大路径。极大：不能再向外延伸20定理4(证明(1)(3))证明:(1)G连通:uv((u,v)Ew((u,w)E(w,v)E)(3)由圈得更长路径:由连通性n-221定理4(证明(2))证明:(2)由极大路径得圈:设极大路径=v0v1…vk,kn-2.(2a)若(v0,vk)E,则得圈C=v0v1…vkv0.(2b)若(v0,vk)E,则i(1ik-1(vi,vk)E(v0,vi+1)E),否则,d(v0)+d(vk)d(v0)+k-d(v0)=kn-2(矛盾).于是得圈C=v0…vivkvk-1…vi+1v0.#v0vkvivi+1v0vk22无向汉密尔顿图的充分条件推论1:设G是n(3)阶无向简单图,若对G中任意不相邻顶点u与v有d(u)+d(v)n则G是汉密尔顿图.证明:由定理4知G连通且有汉密尔顿通路=v0v1…vn.(1)若(v0,vn)E,则得汉密尔顿回路C=v0v1…vnv0.(2)若(v0,vk)E,则与定理4证明(2b)类似,也存在汉密尔顿回路.#v0vnvivi+1v0vn23无向汉密尔顿图的充分条件推论2:设G是n(3)阶无向简单图,若对G中任意顶点u有d(u)n/2则G是汉密尔顿图.推论3:Kn(n2)为汉密尔顿图24图的闭包C(G)定义：给定简单图G=V,E，|V|=n，将图G中度数之和至少为n的非邻接顶点连接起来得到图G'，对G'重复上述步骤，直到不再有这样的顶点对为止，所得到的图称为G的闭包，记作C(G)。25定理5定理5:无向n阶简单图G是汉密尔顿图C(G)是汉密尔顿图.26引理引理:设u,v是无向n阶简单图G中两个不相邻顶点,且d(u)+d(v)n,则G是汉密尔顿图G(u,v)是汉密尔顿图.证明:()显然()设C是G(u,v)中的汉密尔顿回路.(1)C不经过(u,v):C是G中汉密尔顿回路.(2)C经过(u,v):C-(u,v)是G中汉密尔顿通路,与定理4证明(2b)类似,G中有汉密尔顿回路.#27应用举例例：七天内安排七门课的考试，使得同一位教师所担任的两门课程不在相邻的两天考试，若无教师担任多于四门课程，则可以合理安排。每个顶点对应一门考试课程，两个顶点之间有边当且仅当对应两课程由不同教师担任，每个顶点的度数至少是3，任两个顶点度数之和至少为6，因此一定存在一条汉密尔顿通路。28有向汉密尔顿图的充分条件n(n1)阶竞赛图中都有汉密尔顿通路。证明：归纳法v‘1v‘2v‘kv‘1v‘2v‘r-1v‘rvk+1vk+1v‘1v‘2v‘kvk+129旅行商问题(TSP)旅行商问题(TravlingSalesmanProblem):给定n个城市之间的所有距离,求推销员走遍所有城市的最短路线又名货郎担问题,巡回售货员问题,TSPTSP:给定带权完全图G=V,E,W,求最短汉密尔顿回路.30TSP的复杂性蛮力法(bruteforce):穷举所有的可能进行验证或比较,复杂性为2n以上.TSP:n!条H通路,(n-1)!/2条H回路目前还不知道TSP是否有多项式时间算法,大多数学者认为没有.证明?P=?NP问题:计算机科学的核心问题,奖金$1,000,000近似(approximation)算法31总结周游世界,汉密尔顿通(回)路,汉密尔顿图判定汉密尔顿图的必要条件判定汉密尔顿图的充分条件旅行商问题32作业1：1、画一个无向图，使它是：(1)既是欧拉图，又是汉密尔顿图；(2)是欧拉图，而不是汉密尔顿图；(3)是汉密尔顿图，而不是欧拉图；(4)既不是欧拉图，也不是汉密尔顿图。33作业2：2、今有a，b，c，d，e，f，g7个人，已知下列事实：a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲日语和汉语；e会讲德语和意大利语；f会讲法语、日语和俄语；g会讲法语和德语。试问这7个人应如何排座位，才能使每个人都能和他身边的人交谈？34作业3：15,17-20