第五章 图论 5.5欧拉图和哈密顿图 哥尼斯褒七桥问题 5.5.1欧拉图 定义1 欧拉通路：含所有边的简单通路 欧拉回路：含所有边的简单回路

Presentation on theme: "第五章 图论 5.5欧拉图和哈密顿图 哥尼斯褒七桥问题 5.5.1欧拉图 定义1 欧拉通路：含所有边的简单通路 欧拉回路：含所有边的简单回路"— Presentation transcript:

1 第五章 图论 5.5欧拉图和哈密顿图 哥尼斯褒七桥问题 5.5.1欧拉图 定义1 欧拉通路：含所有边的简单通路 欧拉回路：含所有边的简单回路
欧拉图：有欧拉回路的图

2 例1 在图7-47里，哪些无向图具有欧拉回路？在没有欧拉回路的那些图里，哪些具有欧拉通路？
解 图G1具有欧拉回路，例如a, e, c, d, e, b, a。G2和G3都没有欧拉回路。但是G3具有欧拉通路，即a, c, d, e, b, d, a, b。G2没有欧拉通路。 图H2具有欧拉回路，例如a, g, c, b, g, e, d, f, a。H1和H3都没有欧拉回路。H3具有欧拉通路，即c, a, b, c, d, b,但是H1没有欧拉通路。

3 定理1 欧拉图的充要条件 连通图是欧拉图每个顶点的度 都为偶数
证明：先直观描述 ：显然 ： 1.回路的存在性 从连通图G中的任一节点v0开始，取关联于v0的边e1={v0,v1}，因为d(v1)为偶数，所以可以在G中继续取关联于v1的边e2={v1,v2},…，直到取到一条边ek+1={vk,v0}，得到一条简单回路h1: (v0,e1, v1,e2,…,v1,ei+1，…，ek+1,v0)。这里，ei≠ej(i≠j)。显然，h1G。 (接下页)

4 2.若h1=G，则G是欧拉图，否则转下一步。 3.记H=G-h1，因为G是连通图，所以H与h1至少有一个节点重合，不妨记为vi，又因为h1中d(vi)是偶数，故在H中d(vi)仍是偶数，从而从图H的节点vi出发，重复步骤1的做法，又可得简单回路h2: (vi,e1’,v1,e2’,…,vi)这里ei’≠ ej’(i≠j),那么h1∪ h2所对应的简单回路是：(v0,e1,v1,e2,…,vi, e1’,v1,e2’,…,vi，ei+1，…，ek+1,v0)。不妨将h1∪ h2仍记为h2，转步骤2。 对于有限图G，我们总可以在有限步骤中构造出简单回路h1，使得h1=G，故G是欧拉图。

5 例3 一笔画问题 能否用一笔画的方法画出图7-50所示的穆罕默德短弯刀？其中图形是在同一个顶点上开始和结束。
解： 可以解决这个问题，因为图7-50所示的图G具有欧拉回路。它具有这样的回路是因为它的所有顶点偶有偶数度。用算法1来构造欧拉回路。首先形成回路a, b, d, c, b, e, i, f, e, a。通过删除这条回路的边并且删除因此产生的孤立点，就得到子图H。然后形成H中的回路d, g, h, j, i, h, k, g, f, d。形成这条回路之后就用完了G中的所有边。在适当的地方拼接这条回路和第一条回路，就产生出欧拉回路.a, b, d, g, h, j, i, h, k, g, f, d, c, b, e, i, f, e, a。这条回路给出了铅笔不离开纸面并且不重复地画出弯刀的方法。 （接下页）

6 （接上页） 算法1 构造欧拉回路 procedure Euler（G ：所有顶点有偶数度的连通多重图） circuit:=在G中任选的顶点开始连续地加入边所形成的回到 该顶点的回路 H:=删除这条回路的边之后的G while H还有边 begin subcircuit:=在既是H中的顶点也是circuit一条边 的端点开始的H中的一条回路 H:=删除subcircuit的边和所有孤立点之后的H Circuit:=在适当顶点上插入subcircuit之后的circuit end｛circuit 是欧拉回路｝

7 定理2 欧拉通路的充要条件 连通图有欧拉通路而无欧拉回路恰有两个奇数度顶点
证明：定理1的直接推论 有向图的欧拉通路和欧拉回路：类似与无向图 5.5.2哈密顿图 定义2 哈密顿通路：含所顶点的基本通路 哈密顿回路：含所有顶点的简单回路 哈密顿图：有哈密顿回路的图

8 哈密顿的智力题： 木质十二面体，有十二个正五边形表面，二十个顶点，顶点标记为不同的城市，每个顶点上有钉子，另有一细线。目标是从一个城市开始，沿十二面体的边旅行，访问其他19个城市，每个恰好一次，回到第一个城市结束。旅行经过的回路用钉子和细线来标记。

9 哈密顿图的必要条件 没有1度的顶点 2度顶点的边必定在哈密顿回路上 与一个顶点关联的边中有且仅有两条在哈密顿回路上 哈密顿回路中没有小回路 对V的任意非空子集S，有(G-S)≤S。G-S是从G中删除S中的顶点及其关联边 后余下的图，(G-S)表示图G-S的连通分支的数目。

10 例6 证明图7-35中的图没有哈密顿回路。 证明： G中没有哈密顿回路，因为G有1度顶点，即e。现在考虑H。因为顶点a, b，d 和e 的度都为2，所以这些顶点关联的每一条边都必然属于任意一条哈密顿回路。现在容易看出H中不存在哈密顿回路，因为任何这样的哈密顿回路都不得不包含4条关联c的边，这是不可能的。

11 例7 Kn(n>2)是哈密顿图 解 ：从Kn中的任意一个顶点开始来形成哈密顿回路。以所选择的任意顺序来访问顶点，只要求通路在同一个顶点开始和结束，而且恰好访问其他每个顶点一次。这样做是可能的，因为在Kn中任意两个顶点之间都有边。 定理 哈密顿图的充分条件 若G是n个节点的无向连通简单图，其任一节点v满足d(v)≥n/2，则G是哈密顿图。 证明：①为证这个结论，我们先给出一个引理：若G=(V,E)是有n个节点的无向简单图，对于每一对不相邻的节点u，v，有d(u)+d(v)≧n,则G是哈密顿图的充分必要条件是H=(V,E∪{e})为哈密顿图，这里e是与节点u，v关联的无向边。 （接下页）

12 ②现在我们来证明：若G中对于每一对不相邻的节点u，v，有d(u)+d(v)≧n,则G是哈密顿图。因为若在G中每一对不相邻节点u,v之间连一条无向边，得到图H，则H是n阶无向完全图，从而H是哈密顿图，由引理，可知G是哈密顿图。 ③由2，我们可直接推出若任一节点v满足d(v)≥n/2，则G是哈密顿图。 例8 格雷码及其应用：构造长度为n的2进制编码的序列，使相邻的码仅相差1位 用Qn来建模 (接下页)

13 解： 格雷码是圆周的弧的一种标记，使得相邻的弧具有恰好相差一位的位串标记。在图7-56 b）里的赋值是一个格雷码。可以这样找出格雷码：以下述的方式列出所有长度为n的位串，使得每一个位串与前一个位串恰好相差一位，而且最后一个位串与第一个位串恰好相差一位。可以用n立方体Qn来为这个问题建模。解决这个问题所需要的是Qn中的一条哈密顿回路。这样的哈密顿回路容易求出。例如， Q3的一条哈密顿回路所产生的前后恰好相差一位的位串序列是000, 001, 011, 010, 110, 111, 101和100。

14 习题 1.对哪些m和n来说完全偶图具有 a) 欧拉回路？ b) 欧拉通路？ 2.对哪些图来说下列图具有哈密顿回路？ a) Kn b) Cn c) Wn d) Qn 3.一个诊断消息可以在计算机网络上发出，以便在所有连接河所有设备上执行测试。为了测试所有的连接，应当使用什么种类的通路？为了测试所有的设备呢？