第8章 几种典型图(2}.pptVIP

第10章 几种典型图 10.1 欧拉图 10.2 哈密顿图 10.3 平面图 10.4 二分图 10.5 例题选解 习 题 十 8.2 哈密顿图 哈密顿图的概念源于1859年爱尔兰数学家威廉·哈密顿爵士（SirWillianHamilton）提出的一个“周游世界”的游戏。这个游戏把一个正十二面体的二十个顶点看成是地球上的二十个城市，棱线看成连接城市的道路，要求游戏者沿着棱线走，寻找一条经过所有顶点（即城市）一次且仅一次的回路，如图8.2.1（a）所示。也就是在图8.2.1（b）中找一条包含所有顶点的初级回路，图中的粗线所构成的回路就是这个问题的回答。 定义8.2.1 若图G中有一条经过所有顶点一次且仅一次的回路，则称该回路为哈密顿回路，称G为哈密顿图；若图G中有一条经过所有顶点一次且仅一次的通路，则称此通路为哈密顿通路，称G为半哈密顿图。 乍一看，哈密顿图与欧拉图有某种对偶性（点与边的对偶性），但实际上，前者的存在性问题比后者难得多。迄今为止，寻找到一个判断哈密顿图的切实可用的充分必要条件仍是图论中尚未解决的主要问题之一。人们只是分别给出了一些必要条件和充分条件。 定理8.2.1 若G是哈密顿图，则对于顶点集V的每一个非空子集S，均成立 P（G-S）≤|S| 其中，P（G-S）是G-S的连通分支数，|S|是S中顶点的个数。 证明 设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|。 这个定理给出的只是一个无向图是哈密顿图的必要条件，亦即哈密顿图必满足这个条件，满足这个条件的不一定是哈密顿图。 例如，著名的彼得森（Petersen）图（如图8.2.2所示）不是哈密顿图，但对任意的SV，S≠，均满足 ? P(C-S)≤|S| 然而，不满足这个条件的必定不是哈密顿图。 【例8.2.1】 含有割点的图必定不是哈密顿图。 证明 设v是图G中的割点，则 ?P（G-v）≥2＞|{v}| 因此，图G不是哈密顿图。 下面介绍无向图中有哈密顿通路的充分条件。 定理8.2.2 若G是n（n≥3）个顶点的简单图，对于每一对不相邻的顶点u，v，满足 ?d（u）+d（v）≥n-1 则G中存在一条哈密顿通路。 ? 证明 首先证明G是连通图。假设G非连通，则G至少有两个连通分支G1，G2，设G1中有n1个顶点，G2中有n2个顶点，则v1 V（G1），v2 V（G2），因为d（v1）≤n1-1，d（v2）≤n2-1，故d（v1）+d（v2）≤n1+n2-2＜n-1，这与题设条件矛盾，因此，G必连通。 其次，再证G中含有哈密顿通路。设?是G中任意一条有m-1条边的初级通路：v1v2…vm若m=n，则l就是G中的一条哈密顿通路；若m〈n，我们来扩充此路。 （1）如果通路的两个端点v1、vm还与路?之外的顶点邻接，则延伸此通路。 ?（2）如果v1、vm均只与原通路?上的顶点邻接，如下可证：G中有一条包含l的长度为m的回路。 若v1与vm邻接，则v1v2…vmv1即所求之回路。 若v1与vi1，vi2…，vip邻接，1＜i1，i2，…，ip＜m，考虑vm： 重复过程（1）、（2），不断扩充通路l，直至它的长度为n-1，这时便得到G中的一条哈密顿通路。证毕仿此可证： 定理8.2.3 若G是n（n≥3）个顶点的简单图，对于每一对不相邻的顶点u，v，满足