1、第四章 欧拉图与哈密尔顿图主要内容一、欧拉图与中国邮路问题二、哈密尔顿图三、最短路问题与货郎担问题教学时数安排 8学时讲授本章内容1本次课主要内容(一 )、欧拉图及其性质(二 )、 Fleury算法(三 )、中国邮路问题欧拉图与中国邮路问题21、欧拉图的概念(一 )、欧拉图及其性质(1)、问题背景 欧拉与哥尼斯堡七桥问题结论：在一个点线连接的图形中，如果每个顶点关联偶数条边，并且点与点之间有路可行，则从某点出发，经过每条边一次且仅一次，可以回到出发点。3哥尼斯堡城 (位于德国北部 ), 在欧拉的生活与图论历史中扮演着非常重要角色。因为它，产生了著名的欧拉图定理，因为它，产生了图论。注： 一笔画
2、 -中国 古老的 民间游戏要求：对于一个图 G, 笔不离纸 , 一笔画成 .(2)、欧拉图概念定义 1 对于连通图 G，如果 G中存在经过每条边的闭迹，则称 G为欧拉图，简称 G为 E图。欧拉闭迹又称为欧拉环游，或欧拉回路。欧拉图41324132非欧拉图有欧拉迹 非欧拉图无欧拉迹1 23 442、欧拉图的性质定理 1 下列陈述对于非平凡连通图 G是等价的：(1) G是欧拉图；(2) G的顶点度数为偶数；(3) G的边集合能划分为圈。证明 : (1)(2)由 (1)，设 C是欧拉图 G的任一欧拉回路， v是 G中任意顶点， v在环游中每出现一次，意味在 G中有两条不同边与 v关联，所以，在 G中
3、与 v关联的边数为偶数，即v的度数为偶数，由 v的任意性，即证明 (2)。(2)(3)由于 G是连通非平凡的且每个顶点度数为偶数，所以G中至少存在圈 C1,从 G中去掉 C1中的边，得到 G的生成5子图 G1,若 G1没有边，则 (3)成立。否则， G1的每个非平凡分支是度数为偶数的连通图，于是又可以抽取一个圈。反复这样抽取， E(G)最终划分为若干圈。(3)(1)设 C1是 G的边划分中的一个圈。若 G仅由此圈组成，则 G显然是欧拉图。否则，由于 G连通，所以，必然存在圈 C2,它和 C1有公共顶点。于是， C1C 2是一条含有 C1与 C2的边的欧拉闭迹，如此拼接下去，得到包含 G的所有边
4、的一条欧拉闭迹。即证 G是欧拉图。推论 1 连通图 G是欧拉图当且仅当 G的顶点度数为偶。推论 2 连通非欧拉图 G存在欧拉迹当且仅当 G中只有两个顶点度数为奇数。6例 1 下面图中谁是欧拉图？谁是非欧拉图但存在欧拉迹？谁是非欧拉图且不存在欧拉迹？G1G2 G3解： G1是欧拉图； G2是非欧拉图，但存在欧拉迹； G3中不存在欧拉迹。7(二 )、 Fleury算法该算法解决了在欧拉图中求出一条具体欧拉环游的方法。方法是尽可能避割边行走。1、 算法(1)、 任意选择一个顶点 v0,置 w0=v0;8(2)、 假设迹 wi=v0e1v1 eivi已经选定，那么按下述方法从 E- e1,e2, ei中选取边 ei+1:1)、 ei+1与 vi+1相关联；2)、除非没有别的边可选择，否则 ei+1不能是Gi=G- e1,e2, ei的割边。(3)、 当 (2)不能执行时，算法停止。例 3 在下面欧拉图 G中求一条欧拉回路。dcbafe g图 Ghji9解：dcbafe g图 Ghji例 4 某博物馆的一层布置如下图，其中边代表走廊，结点 e是入口，结点 g是礼品店，通过 g我们可以离开博物馆。请找出从博物馆 e进入，经过每个走廊恰好一次，最后从 g处离开的路线。afedcbihgj10
