离散数学无向哈密顿图的一个必要条件鲁 定理132设无向图G=<V,E>是哈密顿图,对于任意V1c且 V1≠,均有p(G-V1)≤1 证设C为G中一条哈密顿回路 (1)p(C-1)≤|1 (2)p(G-V1)≤p(C-V1)≤1(因为CcG) 推论设无向图石=<V,E>是半哈密顿图,对于任意的vV 且类均有 p(G-V1)≤|1+1 证设厂为从到v的哈密顿通路,令G=G∪(,),则G为 哈密顿图.于是 p(G-V)=p(G-V1-(l,)sp(G-V1)+1sv|+1
11 无向哈密顿图的一个必要条件 定理13.2 设无向图G=<V,E>是哈密顿图，对于任意V1V且 V1，均有p(G−V1 ) |V1 | 证 设C为G中一条哈密顿回路 (1) p(C−V1 ) |V1 | (2) p(G−V1 ) p(C−V1 ) |V1 | （因为CG） 推论 设无向图G=<V,E>是半哈密顿图，对于任意的V1V 且V1均有 p(G−V1 ) |V1 |+1 证 设 为从u到v的哈密顿通路，令G = G(u,v)，则G为 哈密顿图. 于是 p(G−V1 ) = p(G−V1−(u,v)) p(G−V1 )+1 |V1 |+1
离散数学 例题 例2判断下面的图是不是哈密顿图,是不是半哈密顿图 a d e be d cK h pf 解(a)取V1={a,D(GV1)={b,c,4}=4>V=2,不是哈密顿图, 也不是半哈密顿图 (b)取V={a2g,h,i,c,p(GV1)={b,ef,,F6V=5,不是哈密 顿图.而 baegjckhfid是一条哈密顿通路,是半哈密顿图 (c) abcdgihjefa是一条哈密顿回路,是哈密顿图 12
12 例题 例2 判断下面的图是不是哈密顿图, 是不是半哈密顿图. 解 (a)取V1={a,f}, p(G−V1 )=|{b,c,d,e}|=4>|V1 |=2, 不是哈密顿图， 也不是半哈密顿图． (b)取V1={a,g,h,i,c}, p(G−V1 )=| {b,e,f,j,k,d}|=6>|V1 |=5, 不是哈密 顿图. 而baegjckhfid是一条哈密顿通路, 是半哈密顿图． (c) abcdgihjefa是一条哈密顿回路，是哈密顿图．
离散数学 例题 例3设G为m阶无向连通简单图,若G中有割点或桥,则G不 是哈密顿图. 证设为割点,则p(G-)≥2>{吵}=1 K2有桥,它显然不是哈密顿图.除K2外,其他有桥的连 通图均有割点 13
13 例题 例3 设G为n阶无向连通简单图，若G中有割点或桥，则G不 是哈密顿图. 证 设v为割点，则p(G−v) 2>|{v}|=1. K2有桥，它显然不是哈密顿图. 除K2外，其他有桥的连 通图均有割点
离散数学无向哈密顿图的一个充分条件鲁 定理133设G是m阶无向简单图,若对于任意不相邻的顶点 均有 d(v)+(y)≥m-1 则G中存在哈密顿通路. 推论设G为n(n≥3)阶无向简单图,若对于G中任意两个不相 邻的顶点v1v均有 d(v)+(y)≥n 则G中存在哈密顿回路. 14
14 无向哈密顿图的一个充分条件 定理13.3 设G是n阶无向简单图, 若对于任意不相邻的顶点 vi ,vj , 均有 d(vi )+d(vj ) n−1 () 则G 中存在哈密顿通路. 推论 设G为n (n3) 阶无向简单图, 若对于G中任意两个不相 邻的顶点vi ,vj , 均有 d(vi )+d(vj ) n （） 则G中存在哈密顿回路
离散数学 判断是否为哈密顿图 判断是否为(半)哈密顿图至今还是一个难题 ⑩)观察出一条哈密顿回路或哈密顿通路. (2)证明满足充分条件 (3)证明不满足必要条件. 例4证明右图周游世界问题)是哈密顿图 Q ile abcdefg hijkimnopgrsta 是一条哈密顿回路. g 注意,此图不满足定理113推论的条件 例5完全图Kn(n≥3)是哈密顿图 证任何两个顶点u,,d(u)+l(v)=2(mn-1)≥n 15
15 判断是否为哈密顿图 判断是否为(半)哈密顿图至今还是一个难题. (1) 观察出一条哈密顿回路或哈密顿通路. (2) 证明满足充分条件. (3) 证明不满足必要条件. 例4 证明右图(周游世界问题)是哈密顿图 证 a b c d e f g h i j k l m n o p q r s t a 是一条哈密顿回路. 注意，此图不满足定理11.3推论的条件. 例5 完全图Kn (n3)是哈密顿图. 证 任何两个顶点u,v，d(u)+d(v) = 2(n−1) n