Chapter 2 关系.pptVIP

第17讲 Euler图与Hamilton图 Chapter 8 几类特殊的图 图论是处理离散对象的一种重要的数学工具. 本章讨论几类在理论研究和实际应用中都有着重要意义的特殊图. Euler图; Hamilton图; 无向树; 有向树(特别是根树); 平面图及其面着色; 二部图等. 8.1 Euler图 1.Euler图的有关概念 8.2 Hamilton 图 1859年爱尔兰数学家W. R. Hamilton发明了一个周游世界游戏: 在一个正12面体的20个顶点上标示世界上的20个大城市,若从一个城市出发,沿正12面体的棱旅行,经过每个城市一次且仅经过一次,最后回到原出发点,就算旅行成功. 从这个游戏抽象出图论中一种非常重要的Hamilton图,且派生出至今为止仍具研究价值的TSP (Traveling Salesman Problem). * * 主要内容: 1. Euler图. 2. Hamilton图. Definition 8-1 设G = (V, E)是任意图, G中经过所有边一次且仅一次的路称为Euler轨迹; 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回路的算法. 类似于Euler定理有 Theorem 8-2(P222) 设G是弱连通有向图, 则G是Euler图的充要条件是G的每节点的入度等于其出度. See Figure 8-1(b). 根据Euler定理容易得出 Theorem 8-3 设G是连通无向图,则G中存在Euler轨迹的充要条件是G的度数为奇数的节点个数为0或为2. 根据该定理知,“七桥问题”无解, 甚至不存在Euler轨迹. 有趣的中国古老数学游戏“一笔画问题”与该定理密切相关. 所谓一个图能一笔画出是指从图的某节点出发,线可以相交但不能重合,不起笔就可以将图画完(P223, 3)? 多笔画(P223, 4). P224, 5, 6. 同样,对于有向图有 Theorem 8-4 设G是弱连通有向图,则G中存在Euler轨迹的充要条件是 (1) G的每节点的入度等于其出度, 或者 (2) G中存在一个节点出度比入度多1,存在一个节点入度比出度多1,而其余所有节点的入度等于其出度. 3.中国邮递员问题(Chinese postman problem) 一位邮递员从邮局选好邮件去投递, 然后返回邮局, 要求邮递员必须经过其负责的每一条街至少一次, 为这位邮递员设计一条投递线路, 使其所走的路最短.(P224, 7) 显然, 若连通无向图有度数为奇数的节点, 由于必须返回邮局, 邮递员必须得重复走一些街道, 问题是怎样才能使得完成投递任务所走的路最短. 这是一个允许添加多重边后求最短Euler回路的问题. P224, 8? 中国邮递员问题首次由中国图论专家管梅谷于1962年提出并研究, 提出了“奇偶点图上作业法”, 引起世界上不少数学家的关注. 在1973年匈牙利数学家Edmonds和Johnson对中国邮递员问题给出了一种有效算法, 另外在1995年王树禾研究了多邮递员中国邮路问题(k-Postman Chinese Postman 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 图的充分条件. *