第6章—一些特殊的图讲述.ppt

哈密尔顿图 问题 1859年爱尔兰数学家威廉·哈密尔顿（Sir William Hamilton）发明了一个小游戏玩具：一个木刻的正十二面体，每面系正五角形，三面交于一角，共有20个角，每角标有世界上一个重要城市。哈密尔顿提出一个问题：要求沿正十二面体的边寻找一条路通过20个城市，而每个城市只通过一次，最后返回原地。哈密尔顿将此问题称为周游世界问题。游戏) 求解 抽象为图论问题 哈密尔顿给出了肯定回答，该问题的解是存在的 ?哈密尔顿回路(圈)?哈密尔顿图 运筹学、计算机科学和编码理论中的很多问题都可以化为哈密尔顿图问题 William Rowan Hamilton (1805-1865) 定义 6.5 经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。 经过图中所有顶点一次且仅一次的回路称为哈密顿回路。 具有哈密顿回路的图称为哈密顿图. 具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图. 注:平凡图是哈密顿图。 6.3 哈密顿图 例6.10 指出下列各图是否哈密顿图,有无哈密顿 通路, 回路？ 解 (1) 容易判断, 存在哈密顿回路, 故是哈密顿图. (2) 只有哈密顿通路, 无哈密顿回路, 故不是哈 密顿图. (3) 无哈密顿通路，显然不是哈密顿图. (1) (2) (3) 例 6.11：判断各图是否是哈密顿图。 1 2 3 4 e1 e2 e3 e4 e5 e1 e2 e3 e4 e5 e1 e2 e3 e4 e5 e6 e3 e1 e2 e4 e2 e1 e3 e4 e5 e2 e1 e3 e4 5 6 例 6.12画出具有下列条件的有5个结点的无向图 (1)?? 不是哈密顿图，也不是欧拉图； (2) 有哈密顿回路，没有欧拉回路； (3) 没有哈密顿回路，有欧拉回路； (4) 是哈密顿图，也是欧拉图. 解 作图如图(4)(不唯一). (1) (2) (3) (4) 例 6.12画出具有下列条件的有5个结点的无向图 (1)?? 不是哈密顿图，也不是欧拉图； (2) 有哈密顿回路，没有欧拉回路； (3) 没有哈密顿回路，有欧拉回路； (4) 是哈密顿图，也是欧拉图. 解 作图如图(4)(不唯一). (1) (2) (3) (4) 定理 6.6 —— 必要条件 设无向图G=V,E是哈密顿图,对于任意V1 ? V 且V1 ≠?, 均有 p(G-V1)≤| V1 |,其中p(G-V1)为G中删除V1(删除V1中各顶点及关联的边)后所得图的连通分支数。 证: 设C为G中任意一条哈密顿回路。 ① 若V1中的顶点在C上彼此相邻，则 p(C- V1)=1 ≤| V1 | ② 设V1中的顶点在C上存在 r( 2≤ r ≤ | V1 | )个 互不相邻，则 p(C- V1)=r ≤| V1 | 一般说来, V1中的顶点在C上既有相邻的,又有不相邻的,因而总有 p(C- V1) ≤| V1 | ， 而C是G的生成子图,∴ p(G-V1)≤ p(C-V1)≤| V1| 例 6.13 利用定理6.6可判断某些图不是哈密顿图 设下图①为G1,取 V1={v},则P(G1-V1)=2 | V1 |=1 G1-V1为图②所示,由定理6.6可知G1不是哈密顿图 v ① ② 例 6.13 利用定理6.6可判断某些图不是哈密顿图 设下图①为G2,在G2中取 V2 = { a, b, c, d, e, f,g }, 则 G2- V2为图 ② 所示,P( G2 - V2)= 9| V2 |=7 由定理6.6可知 G2 不是哈密顿图 ① ② a b c d e f g 定理 6.7 ——充分条件 设 G 是 n (n≥3)阶无向简单图，若对 G中任意不相邻的顶点 vi,vj的度数之和大于等于n-1，即 d(vi)+d(vj)≥n-1 则G中存在哈密顿通路. 推论 设G为n(n ≥3)阶无向简单图，若对于G中任意两个不相邻的顶点vi,vj，均有 d(vi)+d(vj)≥n 则G中存在哈密顿回路，从而G为哈密顿图。 e1 e2 e3 e4 e5 e6 d(vi)+d(vj)≥n-1 存在哈密顿通路 d(vi)+d(vj)≥n 存在哈密顿回路 (2) (3) 再如下图G 任意两个不相邻的顶点vi,vj d(vi)+d(vj)≥n-1 则G中存在哈密顿通路. d(vi)+d(vj)≥n