第18讲 哈密顿图 北京大学计算机系离散数学讲义(ppt版).pptVIP

《集合论与图论》第18讲 第18讲 哈密顿图 1. 周游世界,哈密顿通(回)路,哈密顿图 2. 判定哈密顿图的必要条件 3. 判定哈密顿图的充分条件 4. 边不重的哈密顿回路 5. 货郎问题, 计算复杂性 周游世界 Sir William Rowan Hamilton, 1857, Icosian game: Willam Rowan Hamilton Willam Rowan Hamilton(1805~1865): 爱尔兰神童(child prodigy) 三一学院(Trinity College) 光学(optics) Willam Rowan Hamilton Willam Rowan Hamilton(1805~1865): 1827, Astronomer Royal of Ireland. 1837, 复数公理化, a+bi, (a,b) 四元数(quaternion): a+bi+cj+dk, 放弃乘法交换律! 马的周游路线(knight’s tour) Leohard Euler, 1759, 棋盘上马的周游路线(knight’s tour on a chessboard) 马的周游路线(knight’s tour) Leohard Euler, 1759, 详细分析 哈密顿图(Hamilton) 哈密顿通路(Hamilton path): 经过图中所有顶点的初级通路 哈密顿回路(Hamilton circuit/cycle): 经过图中所有顶点的初级回路 哈密顿图(Hamiltonian): 有哈密顿回路的图 半哈密顿图(semi- Hamiltonian): 有哈密顿通路的图 无向哈密顿图的必要条件 定理6: 设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|. # 无向半哈密顿图的必要条件 定理7: 设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. # 定理7(证明二) 定理7: 设G=V,E是无向半哈密顿图,则对V的任意非空真子集V1有 p(G-V1)?|V1|+1 证明二: 设P是G中任意哈密顿通路, 两个端点是u与v. 令G1=G?(u,v), 由定理6有 p(G-V1) ? p(G1-V1)+1 ? |V1|+1. # 举例 举例(续) 反例: 非充分条件 上述条件只是必要条件,而不是充分条件 反例: Petersen图 Petersen图满足: ?V1??, p(G-V1)?|V1| Petersen图不是哈密顿图: 穷举 Petersen图是半哈密顿图 无向半哈密顿图的充分条件 定理7: 设G是n(?2)阶无向简单图,若对G中任意不相邻顶点u与v有 d(u)+d(v)?n-1 则G是半哈密顿图. 证明: (1) G连通 (2) 由极大路径得圈 (3) 由圈得更长路径 路径--极大路径--圈--更长路径 ---更长极大路径--更长圈--更长路径--……--哈密顿通路 定理7(证明(1)(3)) 证明: (1) G连通: ?u?v( (u,v)?E? ?w((u,w)?E?(w,v)?E ) (3) 由圈得更长路径: 连通 定理7(证明(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-1-(d(v0)-1)=k?n-2 (矛盾). 于是得圈C=v0…vivkvk-1…vi+1v0. # 无向哈密顿图的充分条件 推论1: 设G是n(?3)阶无向简单图,若对G中任意不相邻顶点u与v有 d(u)+d(v)?n 则G是哈密顿图. 证明: 由定理7知G连通且有哈密顿通路?=v0v1…vn. (1) 若(v0,vn)?E,则得哈密顿回路C=v0v1…vnv0. (2) 若(v0,vk)?E,则与定理7证明(2b)类似,也存在哈密顿回路. # 无向哈密顿图的充分条件 推论2: 设G是n(?3)阶无向