北京大学：《离散数学》系列课程之一《集合论与图论》第18讲 哈密顿图

第18讲哈密顿图 1.周游世界,哈密顿通(回路哈密顿图 2.判定哈密顿图的必要条件 3.判定哈密顿图的充分条件 4.边不重的哈密顿回路 秦5.货郎问题,计算复杂性 《集合论与图论》第18讲

《集合论与图论》第18讲 1 第18讲 哈密顿图 1. 周游世界,哈密顿通(回)路,哈密顿图 2. 判定哈密顿图的必要条件 3. 判定哈密顿图的充分条件 4. 边不重的哈密顿回路 5. 货郎问题, 计算复杂性

周游世界 Sir William Rowan hamilton, 1857 Icosian game 《集合论与图论》第18讲

《集合论与图论》第18讲 2 周游世界 Sir William Rowan Hamilton, 1857, Icosian game:

Willam rowan hamilton +Willam Rowan Hamilton(1805-1865) 爱尔兰神童( ( child prodigy 学院( (Trinity College) 光学( optIcs) 《集合论与图论》第18讲

《集合论与图论》第18讲 3 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,复数公理化,abi,(a,b) 四元数 (quaternion):a+bcj+k,放弃乘法 交换律! 3 eiRe 943 2 ROWAN HAMILTON 《集合论与图论》第18讲

《集合论与图论》第18讲 4 Willam Rowan Hamilton Willam Rowan Hamilton(1805~1865): 1827, Astronomer Royal of Ireland. 1837, 复数公理化, a+bi, (a,b) 四元数(quaternion): a+bi+cj+dk, 放弃乘法 交换律!

马的周游路线 night's tour) Leonard euler,1759,棋盘上马的周游路 '(knight's tour on a chessboard) 《集合论与图论》第18讲

《集合论与图论》第18讲 5 马的周游路线(knight’s tour) Leohard Euler, 1759, 棋盘上马的周游路 线(knight’s tour on a chessboard)

马的周游路线 night's tour) Leonard euler,1759,详细分析 《集合论与图论》第18讲

《集合论与图论》第18讲 6 马的周游路线(knight’s tour) Leohard Euler, 1759, 详细分析

哈密顿图( Hamilton) 哈密顿通路( Hamilton path):经过图中所 有顶点的初级通路 哈密顿回路( Hamilton circuit/cycle):经过 图中所有顶点的初级回路 哈密顿图( Hamiltonian):有哈密顿回路的 图 半哈密顿图( (semi-Hamiltonian):有哈密 顿通路的图 《集合论与图论》第18讲

《集合论与图论》第18讲 7 哈密顿图(Hamilton) 哈密顿通路(Hamilton path): 经过图中所 有顶点的初级通路 哈密顿回路(Hamilton circuit/cycle): 经过 图中所有顶点的初级回路 哈密顿图(Hamiltonian): 有哈密顿回路的 图 半哈密顿图(semi- Hamiltonian): 有哈密 顿通路的图

无向哈密顿图的必要条件 定理6:设G=是无向哈密顿图,则对 V的任意非空真子集V有 p(GV)≤N1 证明:设C是G中任意哈密顿回路,当V中 顶点在C中都不相邻时,p(CV=V最大; 否则,p(CV)VC是G的生成子图,所 以p(GV)≤P(CV1)≤V.# 《集合论与图论》第18讲

《集合论与图论》第18讲 8 无向哈密顿图的必要条件 定理6: 设G=是无向哈密顿图,则对 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的任意非空真子集V1有 p(GV1)≤+1 证明:设P是G中任意哈密顿通路,当V中 顶点都在P内部且都不相邻时,p(PV V+1最大;否则,p(PV)V.P是G的 生成子图,所以pGV1)p(P∨V+1 # 《集合论与图论》第18讲

《集合论与图论》第18讲 9 无向半哈密顿图的必要条件 定理7: 设G=是无向半哈密顿图,则 对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的任意非空真子集V有 p(GV1)≤+1 证明二:设P是G中任意哈密顿通路,两个 端点是u与V.令G=GU(uV),由定理6有 p(GV1)≤p(G1V1)+1≤+1.# 《集合论与图论》第18讲

《集合论与图论》第18讲 10 定理7(证明二) 定理7: 设G=是无向半哈密顿图,则 对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. #