马的周游路线 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,E>是无向哈密顿图,则对 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,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(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,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的任意非空真子集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,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. #