deg(v)≥n-1则G中存在哈密尔顿道路证明.PPT

计算机学院 计算机科学与工程学院 冯伟森 Email：fws365@scu.edu.cn * * 计算机学院 * 主要内容 哈密尔顿图及其应用 哈密尔顿道路（圈 ）的定义 连通图G是哈密尔顿图的必要条件 连通图G是哈密尔顿图的充分条件 连通图G是哈密尔顿图的充要条件 哈密尔顿图的应用(推销商问题) * 计算机学院 * 哈密尔顿图 周游世界问题  1857（59）年爱尔兰数学家W.R.Hamilton在给他朋友的一封信中，首先谈到关于十二面体的一个数学游戏：将右图中的每个结点看成一个城市，联结两个结点的边看成是交通线，他的问题就是能不能找到一条旅行路线，使得沿着交通线经过每个城市恰好一次，再回到原来的出发地? 他把这个问题称为周游世界问题。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 * 计算机学院 * 定义13.2　设G是一个连通图，若G中存在一条包含全部结点的基本道路，则称这条道路为G的哈密尔顿道路；若G中存在一个包含全部结点的圈，则称这个圈为G的哈密尔顿圈；含有哈密尔顿圈的图称为哈密尔顿图。 规定平凡图为哈密尔顿图。 哈密尔顿道路是经过图中所有结点的道路中长度最短的通路； 哈密尔顿回路是经过图中所有结点的回路中长度最短的回路。 * 计算机学院 * 例13-2.1 既存在哈密尔顿道路，又存在哈密尔顿圈，即为哈密尔顿图。 (a) (c) (b) a c 既不存在哈密尔顿道路，也不存在哈密尔顿圈。 既存在哈密尔顿道路，又存在哈密尔顿圈，即为哈密尔顿图。 存在哈密尔顿道路，但不存在哈密尔顿圈。 (d) * 计算机学院 * 定理13.3 设无向连通图G＝V,E是哈密尔顿图，S是V的任意非空真子集，则 ?(G-S)≤|S| 其中?(G-S)是从G中删除S后所得到图的连通分支数。 证明：设C是G的一个哈密尔顿圈，则对 ?S(≠?)?V，有 ?(C-S)≤|S| ∵ C-S是G-S的一个生成子图 ∴ ?(G-S)≤?(C-S)≤|S| 为什么？ 此定理表明哈密尔顿 有较好的连通性 * 计算机学院 * 注意 定理13.3在应用中它本身用处不大，但它的逆否命题却非常有用。我们经常利用定理13.3的逆否命题来判断某些图不是哈密尔顿图，即：若存在V的某个非空子集V1使得?(G-V1)＞|V1|，则G不是哈密尔顿图。例如在右图中取V1=｛a,c｝，则?(G-V1)＝4＞|V1|＝2，因而该图不是哈密尔顿图。 定理13.3给出的是哈密尔顿图的必要条件，而不是充分条件。下图所示的彼得森图，对V的任意非空子集V1，均满足?(G-V1)≤|V1|，但它不是哈密尔顿图。 c a * 计算机学院 * 定理13.4 设G＝V，E是具有n个结点的简单图。如果对任意两个结点u,v∈V，均有 deg(u)+deg(v)≥n-1 则G中存在哈密尔顿道路。 证明：1、首先证明满足上述条件的G是连通图。否则G至少有两支，即 G1＝V1，E1和G2＝V2，E2 对?v1∈V1，v2 ∈V2 ， 显然 deg(v1)＋deg(v2)≤|V1|-1+|V2|-1=n-2 与已知矛盾，故G是连通的。 * 计算机学院 * 证明(续1) 2、证明G中存在哈密尔顿道路。 设L＝v1v2…vk为G中最长的一条基本道路，显然k≤n。 若k＝n，则L为G中经过所有结点的道路，即为哈密尔顿道路。 若k＜n，由L的最长性可知，v1和vk的全部邻接点都在L上。 若v1vk?E，则v1v2…vkv1就构成G的一个包含L的圈。 若v1vk?E，则存在L上的结点vi，使得 Why? * 计算机学院 * 证明(续2) v1vi?E ? vi-1vk?E。 （否则，即对?vi?L， v1vi?E而vi-1vk?E。设v1在L上与vi1，vi2，…，vit相邻（t≥2），则vk不能与vi1-1,vi2-1,…,vit-1中的任何一个相邻，这样就有d(vk)≤k-t-1，d(v1)=t，d(v1)+d(vk)≤k-1＜n-1。推出矛盾。） 这样就可以构造一个圈 C＝v1v2…vi-1vkvk-1…viv1。 v1 vk vi vi-1 vj u vk-1 如图所示，这个圈包含了L中的全部结点。 * 计算机学院 * 证明(续3) 这样，对a）和b），都可以构造一个包含L中的全部结点的一个圈C。 因为k＜n，所以V中还有一些结点不在C中，由G的连通性知，存在C外的结点u与C上结点vj相邻。显然，可以构造一条基本道路P′＝uvjvj+1…vi-1vkv