《集合论与图论》第18讲1 第18讲哈密顿图 ?1. 周游世界,哈密顿通(回)路,哈密顿图 ?2. 判定哈密顿图的必要条件 ?3. 判定哈密顿图的充分条件 ?4. 边不重的哈密顿回路 ?5. 货郎问题, 计算复杂性 《集合论与图论》第18讲2 周游世界 ?Sir William Rowan Hamilton, 1857, Icosian game: 《集合论与图论》第18讲3 Willam Rowan Hamilton ?Willam Rowan Hamilton(1805~1865): ?爱尔兰神童(child prodigy) ?三一学院(Trinity College) ?光学(optics) 《集合论与图论》第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, 放弃乘法 交换律! 《集合论与图论》第18讲5 马的周游路线(knight’s tour) ?Leohard Euler, 1759, 棋盘上马的周游路 线(knight’s tour on a chessboard) 《集合论与图论》第18讲6 马的周游路线(knight’s tour) ?Leohard Euler, 1759, 详细分析 《集合论与图论》第18讲7 哈密顿图(Hamilton) ?哈密顿通路(Hamilton path): 经过图中所 有顶点的初级通路 ?哈密顿回路(Hamilton circuit/cycle): 经过 图中所有顶点的初级回路 ?哈密顿图(Hamiltonian): 有哈密顿回路的 图 ?半哈密顿图(semi- Hamiltonian): 有哈密 顿通路的图 《集合论与图论》第18讲8 无向哈密顿图的必要条件 ?定理6: 设G=<V,E>是无向哈密顿图,则对 V的任意非空真子集V 1 有 p(G-V 1 )≤|V 1 | ?证明: 设C是G中任意哈密顿回路, 当V 1 中 顶点在C中都不相邻时, p(C-V 1 )=|V 1 |最大; 否则, p(C-V 1 )<|V 1 |. C是G的生成子图, 所 以p(G-V 1 )≤P(C-V 1 )≤|V 1 |. # 《集合论与图论》第18讲9 无向半哈密顿图的必要条件 ?定理7: 设G=<V,E>是无向半哈密顿图,则 对V的任意非空真子集V 1 有 p(G-V 1 )≤|V 1 |+1 ?证明: 设P是G中任意哈密顿通路, 当V 1 中 顶点都在P内部且都不相邻时, p(P-V 1 )= |V 1 |+1最大; 否则, p(P-V 1 )≤|V 1 |. P是G的 生成子图, 所以p(G-V 1 )≤p(P-V 1 )≤|V 1 |+1. # 《集合论与图论》第18讲10 定理7(证明二) ?定理7: 设G=<V,E>是无向半哈密顿图,则 对V的任意非空真子集V 1 有 p(G-V 1 )≤|V 1 |+1 ?证明二: 设P是G中任意哈密顿通路, 两个 端点是u与v. 令G 1 =G∪(u,v), 由定理6有 p(G-V 1 ) ≤ p(G 1 -V 1 )+1 ≤ |V 1 |+1. # 《集合论与图论》第18讲11 举例 《集合论与图论》第18讲12 举例(续) 《集合论与图论》第18讲13 反例: 非充分条件 ?上述条件只是必要条件,而不是充分条件 ?反例: Petersen图 ?Petersen图满足: ?V 1 ≠?, p(G-V 1 )≤|V 1 | ?Petersen图不是哈密顿图: 穷举 ?Petersen图是半哈密顿图 《集合论与图论》第18讲14 无向半哈密顿图的充分条件 ?定理7: 设G是n(≥2)阶无向简单图,若对G 中任意不相邻顶点u与v有 d(u)+d(v)≥n-1 则G是半哈密顿图. ?证明: (1) G连通 (2) 由极大路径得圈 (3) 由圈得更长路径 路径--极大路径--圈--更长路径 ---更长极大路径--更长圈--更长路径--……--哈密顿通路 《集合论与图论》第18讲15 定理7(证明(1)(3)) ?证明: (1) G连通: ?u?v( (u,v)?E→ ?w((u,w)∈E∧(w,v)∈E ) (3) 由圈得更长路径: 连通 n-2 《集合论与图论》第18讲16 定理7(证明(2)) ?证明: (2) 由极大路径得圈: 设极大路径 Γ=v 0 v 1 …v k , k≤n-2. (2a) 若(v 0 ,v k )∈E,则得圈 C=v 0 v 1 …v k v 0 . (2b) 若(v 0 ,v k )?E,则 ?i( 1≤i≤k-1∧(v i ,v k )∈E∧(v 0 ,v i+1 )∈E ), 否则, d(v 0 )+d(v k )≤d(v 0 )+k-1-(d(v 0 )-1)=k≤n-2 (矛盾). 于是得圈C=v 0 …v i v k v k-1 …v i+1 v 0 . # v 0 v k v i v i+1 v 0 v k 《集合论与图论》第18讲17 无向哈密顿图的充分条件 ?推论1: 设G是n(≥3)阶无向简单图,若对G 中任意不相邻顶点u与v有 d(u)+d(v)≥n 则G是哈密顿图. ?证明: 由定理7知G连通且有哈密顿通路 Γ=v 0 v 1 …v n . (1) 若(v 0 ,v n )∈E,则得哈密顿 回路C=v 0 v 1 …v n v 0 . (2) 若(v 0 ,v k )?E,则与 定理7证明(2b)类似,也存在哈密顿回路. # 《集合论与图论》第18讲18 无向哈密顿图的充分条件 ?推论2: 设G是n(≥3)阶无向简单图,若对G 中任意顶点u有 d(u)≥n/2 则G是哈密顿图. ?证明: 由推论1. # 《集合论与图论》第18讲19 定理8 ?定理8: 设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中哈密顿通路, 与定理7证明(2b)类似, G中有哈密顿回路. # 《集合论与图论》第18讲20 有向半哈密顿图的充分条件 ?定理9: 设D是n(≥2)阶竞赛图,则D是半哈 密顿图. # ?推论:设D是n阶有向图, 若D含n阶竞赛图 作为子图,则D是半哈密顿图. # 《集合论与图论》第18讲21 有向哈密顿图的充分条件 ?定理10: 强连通的竞赛图是哈密顿图. ?证明: n=1时,平凡图是哈密顿图. n=2时,不可能强连通. 下面设n≥3. (1) D中存在长度为3的圈. (2) D中存在长度为k的圈? D中存在长度 为k+1的圈. 《集合论与图论》第18讲22 定理10(证明(1)) ?证明(续): (1) D中存在长度为3的圈. ?v∈V(D), 考虑v的前驱集 Γ D - (v) = { u∈V(D) | <u,v>∈E(D) }与后继集 Γ D + (v) = { u∈V(D) | <v,u>∈E(D) }. D强连通竞赛图, 所以Γ D - (v)≠?, Γ D + (v)≠?,Γ D - (v)∪Γ D + (v)=V(D)-{v}, ?s∈Γ D + (v), ?t∈Γ D - (v), <s,t>∈E(D). 于是C=vstv是长度为3的圈. v t s Γ D - (v) Γ D + (v) 《集合论与图论》第18讲23 定理10(证明(2)) ?证明(续): (2) D中存在长度为k的圈? D 中存在长度为k+1的圈: 设D中长度为k (3≤k≤n) 的圈C=v 1 v 2 …v k v 1 . (2a) ?v∈V(D-C), ?v s ∈V(C), ?v t ∈V(C), <v s v>∈E(D),<v,v t >∈E(D): 则?v i-1 ∈V(C), ?v j ∈V(C), <v i-1 ,v>∈E(D),<v,v j >∈E(D). v s v t v v i-1 v i v 《集合论与图论》第18讲24 定理10(证明(2a)) ?证明(续): (2a) ?v∈V(D-C), ?v i-1 ∈V(C), ?v i ∈V(C), <v i-1 ,v>∈E(D), <v,v i >∈E(D), 则C’=v 1 v 2 …v i-1 vv i …v k v 1 是长度为k+1的 圈. v i-1 v i v v i-1 v i v 《集合论与图论》第18讲25 定理10(证明(2b)) ?证明(续): (2b) ?v∈V(D-C), ( ?u∈V(C), <u,v>∈E(D) ) ∨ ( ?u∈V(C), <v,u>∈E(D) ): 则令 V 1 ={v∈V(D-C) | ?u∈V(C), <u,v>∈E(D) }, V 2 ={v∈V(D-C) | ?u∈V(C), <v,u>∈E(D) }, 则V 1 ≠?, V 2 ≠?, V 1 ∩V 2 =?. C V 1 V 2 《集合论与图论》第18讲26 定理10(证明(2b)) ?证明(续): (2b) 于是?s∈V 1 , ?t∈V 2 , <s,t>∈E(D). 在C上任取相邻3点v i-1 ,v i ,v i+1 , 则C’=v 1 v 2 …v i-1 stv i+1 …v k v 1 是长度为k+1 的圈.# C V 1 V 2 s t v i-1 v i v i+1 《集合论与图论》第18讲27 推论 ?推论:设D是n阶有向图, 若D含n阶强连通 竞赛图作为子图,则D是哈密顿图. # 《集合论与图论》第18讲28 边不重的哈密顿回路 ?边不重的哈密顿回路: 设C 1 与C 2 都是图G 的哈密顿回路, 若E(C 1 )∩E(C 2 )=?, 则称 它们为边不重的哈密顿回路. ?问题: K n (≥3)中同时存在多少条边不重的 哈密顿回路? 《集合论与图论》第18讲29 定理11 ?定理11: 完全图K 2k+1 (k≥1)中同时有k条边 不重的哈密顿回路,且这k条边不重的哈密 顿回路含K 2k+1 中所有边 ?推论: 完全图K 2k (k≥2)中同时有k-1条边不 重的哈密顿回路,并且删除这k-1条哈密顿 回路的所有边后, 剩下的是k条彼此不相 邻的边 《集合论与图论》第18讲30 定理11(证明) ?证明: 设V(K 2k+1 )={v 1 ,v 2 ,…,v 2k+1 }, 对 i=1,2,…,k, 令 P i =v i v i-1 v i+1 v i-2 v i+2 …v i-(k-1) v i+(k-1) v i-k , 把下标按mod(2k)转换到{1,2,…,2k+1}中, 0转换成2k, 令C i =v 2k+1 P i v 2k+1 . 可以证明: C i 都是哈密顿回路; E(C i )∩E(C i )=? (i≠j); U i=1 n E(C i )=E(K 2k+1 ). # 《集合论与图论》第18讲31 定理11(举例) ?K 7 : V(K 7 )={v 1 ,v 2 ,…,v 7 }, k=3, mod 6, P 1 =v 1 v 0 v 2 v -1 v 3 v -2 =v 1 v 6 v 2 v 5 v 3 v 4 , P 2 =v 2 v 1 v 3 v 0 v 4 v -1 =v 2 v 1 v 3 v 6 v 4 v 5 , P 3 =v 3 v 2 v 4 v 1 v 5 v 0 =v 3 v 2 v 4 v 1 v 5 v 6 , v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 1 v 2 v 3 v 4 v 5 v 6 v 7 《集合论与图论》第18讲32 推论(证明) ?证明: k=2时, K 4 显然. 下面设k≥3. K 2k = K 2(k-1)+1 + K 1 (联图) 设V(K 2(k-1)+1 )={v 1 ,v 2 ,…,v 2k-1 }, V(K 1 )={v 2k }, 《集合论与图论》第18讲33 推论(证明) ?证明: 由定理11, K 2k-1 中有k-1条边不重的 哈密顿回路,设为C’ 1 ,C’ 2 ,…,C’ k-1 , 依次把 v 2k “加入”C’ i ,得到满足要求的C i . # 《集合论与图论》第18讲34 货郎问题(TSP) ?货郎问题(Travling Salesman Problem): 给定n个城市之间的所有距离, 求推销员 走遍所有城市的最短路线 ?又名旅行商问题,巡回售货员问题,TSP ?TSP: 给定带权完全图G=<V,E,W>,求最 短哈密顿回路. 《集合论与图论》第18讲35 复杂性(complexity) ?复杂性(complexity): 算法工作时需要的 资源数量, 如时间,空间等 ?输入规模(input size): 反映输入大小的量, 如图的顶点数,图的边数等 ?最坏情形(worst-case)复杂性: 在所有规 模为n的输入上, 算法工作所需要的最大 资源量, 通常表示为n的函数, 如n 2 , 2 n 等 《集合论与图论》第18讲36 可行(efficient)算法 ?可行(efficient)算法: 复杂性是多项式函数 的算法, 如O(n 2 ), O(n), O(n 3 ), O(n 100 ). ?易解(tractable)问题: 存在多项式复杂性 算法的问题, 如欧拉图问题 ?P(polynomial time): 存在多项式时间复杂 性算法的问题, 如欧拉图问题 ?难解(intractable)问题: 不存在多项式复杂 性算法的问题, 如货郎问题(TSP) 《集合论与图论》第18讲37 TSP的复杂性 ?蛮力法(brute force): 穷举所有的可能性 来进行验证或比较, 复杂性为2 n 以上. ?TSP: n!条H通路, (n-1)!/2条H回路 ?启发式(Heuristic)方法: 分支限界,…… ?目前还不知道TSP是否有多项式时间算 法, 大多数学者认为没有. 证明? ?P=?NP问题:计算机科学的核心问题, 奖 金$1,000,000 ?近似(approximation)算法 《集合论与图论》第18讲38 总结 ?周游世界,哈密顿通(回)路,哈密顿图 ?判定哈密顿图的必要条件 ?判定哈密顿图的充分条件 ?边不重的哈密顿回路 ?货郎问题, 计算复杂性 《集合论与图论》第18讲39 作业(#14) ? p234, 习题八, 7,9,13 ?今天交作业#11, #12, #13 《集合论与图论》第18讲40 习题讲解(#10) ?p213, 习题七, 1,2,3,4,5,7 ?1. 解: 设G中顶点数为n,由握手定理: 32=2m=Σd(v)≤3*4+4*3+2(n-7), 解得n≥11. # ?错误: 32=2m=Σd(v)<3*4+4*3+3(n-7), 解得n>29/3≈9.67, n∈Z,∴ n≥10. # 《集合论与图论》第18讲41 习题讲解(#10) ?2. 方法一: 穷举法 ?证明: 由握手定理及其推论, G中5度顶点 的个数只能是0,2,4,6,8, 相应的G中6度 顶点的个数是9,7,5,3,1.在这5种组合中, 前3种至少有5个6度顶点, 后2种至少有6 个5度顶点. # ?注意: 0个5度顶点是可能的 《集合论与图论》第18讲42 习题讲解(#10) ?2. 方法二: 反证法 ?证明: (反证)假设结论不成立, 即G中至多 有4个6度顶点并且至多有5个5度顶点. 因 为G是9阶图并且只有5度和6度顶点, 所 以G中恰好有4个6度顶点和5个5度顶点. 但是, 这与握手定理及其推论相矛盾! # 《集合论与图论》第18讲43 习题讲解(#10) ?3.证明: (反证)假设存在这样的多面体,令 G=<V,E>, 其中V={ v | v 是多面体的面}, E={ (u,v) | 面u与面v之间有公共棱}. 则G 有奇数个顶点, 并且所有顶点都有奇数度. 这是与握手定理及其推论相矛盾的!. # 《集合论与图论》第18讲44 习题讲解(#10) ?4. 证明: 令G=<V,E>, 其中V={v|v是选手}, E={(u,v)|选手u与选手v下过棋}. G是简单 图并且δ(G)≥1.设V(G)={v 1 ,v 2 ,…,v n }, 则 ?i∈{1,2,…,n}, d(v i )∈{1,2,…,n-1}. 由抽屉 原则,存在i,j∈{1,2,…,n}, i≠j, d(v i )=d(v j ). # ?定理: 简单图中至少有2个顶点度相等. 《集合论与图论》第18讲45 习题讲解(#10) ?5. 方法一: 考虑G 解: 2m=3n, (握手定理) n=6 2n-3=m, (已知条件) m=9 所以G的度数列为(3,3,3,3,3,3), 删除1个 顶点后G 1 为(2,2,2,3,3). 考虑G 1 的2个3度 顶点是否相邻,可得出2种非同构情况. # G 1 G 《集合论与图论》第18讲46 习题讲解(#10) ?5. 方法二: 考虑G 解: 2m=3n, (握手定理) n=6 2n-3=m, (已知条件) m=9 所以G的度数列为(3,3,3,3,3,3), G的度数 列是(2,2,2,2,2,2). 考虑G的圈的长度, 可 得出2种非同构情况. # G G 《集合论与图论》第18讲47 习题讲解(#10) ?7. 解: (1) (6,6,5,5,3,3,2) 不可简单图化 (5,4,4,2,2,1), (3,3,1,1,0), (2,0,0,0) (2) (5,3,3,2,2,1) 可以(1种非同构的) (2,2,1,1,0), (1,0,1,0) 《集合论与图论》第18讲48 习题讲解(#10) ?7. 解(续): (3) (3,3,2,2,2,2) 可以(4种非同构的) (2,1,1,2,2), (2,2,2,1,1), (1,1,1,1) ?错误: (2,1,1,2,2), (0,0,2,2) 不可