第10章几种典型图 定义10.21若图G中有一条经过所有顶点一次且仅 次的回路,则称该回路为哈密顿回路,称G为哈密顿 图;若图G中有一条经过所有顶点一次且仅一次的通路, 则称此通路为哈密顿通路,称G为半哈密顿图 乍一看,哈密顿图与欧拉图有某种对偶性(点与 边的对偶性),但实际上,前者的存在性问题比后者 难得多。迄今为止,寻找到一个判断哈密顿图的切实 可用的充分必要条件仍是图论中尚未解决的主要问题 之一。人们只是分别给出了一些必要条件和充分条件
第10章 几种典型图 定义10.2.1 若图G中有一条经过所有顶点一次且仅 一次的回路，则称该回路为哈密顿回路，称G为哈密顿 图；若图G中有一条经过所有顶点一次且仅一次的通路， 则称此通路为哈密顿通路，称G为半哈密顿图。 乍一看，哈密顿图与欧拉图有某种对偶性（点与 边的对偶性），但实际上，前者的存在性问题比后者 难得多。迄今为止，寻找到一个判断哈密顿图的切实 可用的充分必要条件仍是图论中尚未解决的主要问题 之一。人们只是分别给出了一些必要条件和充分条件
第10章几种典型图 定理10.21若G是哈密顿图,则对于顶点集V的每 一个非空子集S,均成立 P(G-S) <SI 其中,P(GS)是G-S的连通分支数,S是S中顶 点的个数
第10章 几种典型图 定理10.2.1 若G是哈密顿图，则对于顶点集V的每 一个非空子集S，均成立 P（G-S）≤|S| 其中，P（G-S）是G-S的连通分支数，|S|是S中顶 点的个数
第10章几种典型图 证明设C是图G中的一条哈密顿回路,S是V的任 意非空子集,!a1∈S,C-{a1}是一条初级通路,若再 删去a2∈S,则当a1、a2邻接时,P(C{a1,a2})=1 2;而当a1、a2不邻接时,P(C-{a1,a2})=2,即 P(C-{a1,a2})s2={a1,a2} 如此做下去,归纳可证 P(C-S)≤S 因为CS是GS的生成子图,所以 P(G-S)≤P(CS)≤
第10章 几种典型图 证明 设C是图G中的一条哈密顿回路，S是V的任 a1∈S，C-{a1}是一条初级通路，若再 删去a2∈S，则当a1、a2邻接时，P（C-{a1，a2}）=1＜ 2；而当a1、a2不邻接时，P（C-{a1，a2}）=2，即 P（C-{a1，a2}）≤2=|{a1，a2}| 如此做下去，归纳可证 P（C-S）≤|S| 因为C-S是G-S的生成子图，所以 P（G-S）≤P（C-S）≤|S|。
第10章几种典型图 图1022
第10章 几种典型图 图 10.2.2
第10章几种典型图 这个定理给出的只是一个无向图是哈密顿图的必要 条件,亦即哈密顿图必满足这个条件,满足这个条件的 不一定是哈密顿图 例如,著名的彼得森( Petersen)图(如图10.2.,2所 示)不是哈密顿图,但对任意的SV,S⑧,均满足 P(C-S)≤S 然而,不满足这个条件的必定不是哈密顿图
第10章 几种典型图 这个定理给出的只是一个无向图是哈密顿图的必要 条件，亦即哈密顿图必满足这个条件，满足这个条件的 不一定是哈密顿图。 例如，著名的彼得森（Petersen）图（如图10.2.2所 示）不是哈密顿图，但对任意的S V，S≠ ，均满足 P(C-S)≤|S| 然而，不满足这个条件的必定不是哈密顿图。