第17讲 Euler图与Hamilton图 主要内容: 1. Euler图. 2. Hamilton图.

Chapter 8 几类特殊的图 图论是处理离散对象的一种重要的数学工具. 本章讨论几类在理论研究和实际应用中都有着重要意义的特殊图. Euler图; Hamilton图; 无向树; 有向树(特别是根树); 平面图及其面着色; 二部图等.

8.1 Euler图 1.Euler图的有关概念

Definition 8-1 设G = (V, E)是任意图, G中经过所有边一次且仅一次的路称为Euler轨迹; 存在Euler回路的图称为Euler图或简称为E图.

Euler回路Euler轨迹,但反过来一般不成立. 在图(a)中的图中存在Euler轨迹,但不存在Euler回路.

2.Euler定理(本节主要定理) Theorem 8-1(Euler定理) 设G是连通无向图,则G是Euler图的充要条件是G的每节点度数为偶数. Proof ()显然. ()设G是(n, m)图. 对边数m归纳.

1921年Fleury给出了一个求Euler回路的算法. Theorem 8-2(P222) 设G是弱连通有向图, 则G是Euler图的充要条件是G的每节点的入度等于其出度. See Figure 8-1(b).

Theorem 8-3 设G是连通无向图,则G中存在Euler轨迹的充要条件是G的度数为奇数的节点个数为0或为2. 有趣的中国古老数学游戏“一笔画问题”与该定理密切相关. 所谓一个图能一笔画出是指从图的某节点出发,线可以相交但不能重合,不起笔就可以将图画完(P223, 3) 多笔画(P223, 4). P224, 5, 6.

同样,对于有向图有 Theorem 8-4 设G是弱连通有向图,则G中存在Euler轨迹的充要条件是 (1) G的每节点的入度等于其出度, 或者 (2) G中存在一个节点出度比入度多1,存在一个节点入度比出度多1,而其余所有节点的入度等于其出度.

3.中国邮递员问题(Chinese postman problem)

显然, 若连通无向图有度数为奇数的节点, 由于必须返回邮局, 邮递员必须得重复走一些街道, 问题是怎样才能使得完成投递任务所走的路最短 显然, 若连通无向图有度数为奇数的节点, 由于必须返回邮局, 邮递员必须得重复走一些街道, 问题是怎样才能使得完成投递任务所走的路最短. 这是一个允许添加多重边后求最短Euler回路的问题. P224, 8?

中国邮递员问题首次由中国图论专家管梅谷于1962年提出并研究, 提出了“奇偶点图上作业法”, 引起世界上不少数学家的关注 中国邮递员问题首次由中国图论专家管梅谷于1962年提出并研究, 提出了“奇偶点图上作业法”, 引起世界上不少数学家的关注. 在1973年匈牙利数学家Edmonds和Johnson对中国邮递员问题给出了一种有效算法, 另外在1995年王树禾研究了多邮递员中国邮路问题(k-Postman Chinese Postman Problem).

8.2 Hamilton 图 1859年爱尔兰数学家W. R. Hamilton发明了一个周游世界游戏: 在一个正12面体的20个顶点上标示世界上的20个大城市,若从一个城市出发,沿正12面体的棱旅行,经过每个城市一次且仅经过一次,最后回到原出发点,就算旅行成功. 从这个游戏抽象出图论中一种非常重要的Hamilton图,且派生出至今为止仍具研究价值的TSP (Traveling Salesman Problem).

1.Hamilton 图的有关概念 Definition 8-2 设G = (V, E)是任意图, G中经过所有节点一次且仅一次的路径称为H路径(Hamiltonian path); G中经过所有节点一次且仅一次(除起点重复一次外)的圈称为H回路 (Hamiltonian cycle); 存在H回路的图称为Hamilton图(Hamiltonian graph)或简称为H图.

由H回路可得到H路径, 不返回出发点即可, 但反过来一般不成立. 在图(a)中的图中存在H路径, 但不存在H回路.(b)中的图存在H回路,它是H图.

判断一个图是否是Hamilton 图是非常困难的,虽然已经有一些图是Hamilton 图的充要条件,但到目前为止还没有一种方法可以有效地解决Hamilton 图的判断问题,这是一个计算机科学中的一个NP难问题. 下面分别介绍Hamilton 图的必要条件和Hamilton 图的充分条件.

2.Hamilton 图的必要条件 Theorem 8-5 设G = (V, E)是Hamilton无向图, 则对于任意  W  V, 均有w(G -W)  |W|. Proof 根据已知条件, G中存在Hamilton回路C. 显然, w(G -W)  w(C -W)  |W|. 例8-3(P225) 对于Petersen图, 可以验证它满足上述定理的条件, 但它不是Hamilton图.

3.Hamilton 图的充分条件 1960年Ore得到一个Hamilton 图的充分条件. Theorem 8-6 (Ore, 1960) 设G = (V, E)是n(n  3)阶简单无向图, 若对于任意的不相邻节点u, v  V, 有deg(u) + deg(v)  n, 则G是Hamilton图. 课堂 P228, 7.

Proof G是连通的. Key: 在G中选取一条最长路径 (a)v1与vp邻接? (b)v1与vp不邻接? 最长路径法!

例8-4(P227) Ore定理的条件不是必要的. Ore的上述结果推广了1952年Dirac的结果. Corollary (Dirac, 1952) 设G = (V, E)是n(n  3)阶简单无向图, 若对于任意节点v  V, 有deg(v)  n/2, 则G是Hamilton图. 类似于定理8-6有 Theorem 8-7 设G = (V, E)是n(n  3)阶简单无向图, 若对于任意的不相邻节点u, v  V, 有deg(u) + deg(v)  n-1, 则G中存在H路径.

在定理8-6的证明过程中,使用了“最长路径法”技巧. 下面再举一个例子说明该方法的使用. 例8-5 设G = (V, E)是n(n  3)阶连通无向图, 证明: 中存在两个节点, 将它们删除后得到的图仍是连通的. Hint 选取最长路径, 使用反证法即可.

4.旅行商问题(TSP) 有n个城镇, 其中任意两个城镇间都有道路(若没有则规定该边上的权为+), 一个售货员要去这n个城镇售货, 从某城镇出发, 依次访问其余n - 1个城镇且每个城镇只能访问一次, 最后又回到原出发地. 问售货员要如何安排经过个城镇的行走路线才能使他所走的路程最短. 这就是“货郎担问题”或旅行商问题(TSP, Traveling Salesman Problem).

求解TSP就是要在一个赋权图中,找出一条权最小的Hamilton回路. 这是一个比判断一个图是否是Hamilton图更困难的问题.