五欧拉图与哈密顿图.ppt

问题的提出 作业　 P303　 . . . 例2 下列各图中 是否有哈密顿回路、哈密顿通路？ (1) 带1度顶点的图无哈密顿回路； (2) 若图中有2度顶点，则关联这个顶点的两条边属于任意一条哈密顿回路； (3) 当构造哈密顿回路且该回路经过某一顶点时除了回路所用的两条边，不用再考虑这个顶点关联的其它边； (4) 哈密顿回路不能包含更小的回路； (5) 若图中某些必须出现在哈密顿回路中的边已构成回，而图中尚有不在该回路中的点，则此图不是哈密顿图。 说 明： 从定义可以看出，哈密顿通路是图中生成的初 级通路，而哈密顿回路是生成的初级回路. 判断一个图是否为哈密顿图，就是判断能否将 图中所有顶点都放置在一个初级回路（圈）上， 但这不是一件易事. 与判断一个图是否为欧拉图不一样，到目前为止， 人们还没有找到哈密顿图简单的充分必要条件. 下面给出的定理都是哈密顿通路（回路）的必要 条件或充分条件. 二、哈密顿图与半哈密顿图的 一些必要与充分条件 定理15.6设无向图G = V, E 是哈密顿图， 对于任意 均有 其中，p(G－V1) 为 G-V1 的连通分支数. 必要条件 　证： 设C为G中任意一条哈密顿回路，易知， 当V1中顶点在C上均不相邻时，p(C-V1)达到最 大值|V1|，而当V1中顶点在C上有彼此相邻的情 况时，均有 所以有 而C是G的生成子图，所以，有 可验证彼得松图 满足定理中的条件， 但它不是哈密顿图. 当然，若一个图不满足定理中的条件，它 一定不是哈密顿图. 　　定理15.6的条件是哈密顿图的必要条件，但不是充分条件.　常用它判断一个图不是哈密顿图。 推论 设无向图G = V, E 是半哈密顿图，对于 任意的 均有 证: 设P是G中起于 u 终于 v 的哈密顿通路， 令G= G∪(u ,v)（在G的顶点 u, v 之间加新边）， 易知G为哈密顿图， 由定理15.6可知， 而有 例15.3 在图15.6中给出的三个图都是二部图. 它们中的那些是哈密顿图？哪些是半哈密顿图？ 为什么？ 图15.6 解 在(1)中，易知互补顶点子集 设此二部图为G1， 则 由定理15.6及其推论可知，G1不是哈密顿图， 也不是半哈密顿图. 设(2)中图为G2，则 其中 易知， 由定理15.6可知， G2不是哈密顿图，但G2是半哈密顿图，其实， 为G2中一条哈密顿通路. 设(3)中图为G3. 其中 G3中存在哈密顿 回路（演示），如 所以G3是哈密顿图. 　通过本例，清楚地看出，哈密顿通路是经过 图中所有顶点的一条初级通路，而哈密顿回路 是经过图中所有顶点的初级回路. 例15.4 设G是 n 阶无向连通图. 证明： 若G中有割点或桥，则G不是哈密顿图. 对于二部图还能得出下面结论： 一般情况下，设二部图G=V1,V2,E， 由定理15.6及其推论可以得出下面结论： （2）若G是半哈密顿图，则|V2|=|V1|+1. （3）若|V2|≥|V1|+2，则G不是哈密顿图， 也不是半哈密顿图. （1）若G是哈密顿图，则|V1|=|V2|. 定理15.7 设G是n阶无向简单图，若对于G中 任意不相邻的顶点 vi , vj，均有 d( vi )+ d( vj )≥ n－1