文档介绍：第4,5章E,H图,匹配103
§ 高效率计算机鼓轮的设计
计算机中旋转鼓轮的位置是借助于鼓轮表面上的一系列电触点所产生的二元信号来识别的。这个表面分为m段，每段由绝缘体或导体材料组成。绝缘段给出信号0（没有电流），导通段给00001**********……)
(abhipgcdklmnjefq……) = (00001**********……)
§
问题：邮递员从邮局出发，递送邮件，然后返回邮局，要求辖区每条街至少走一遍且走过的总路程最短，应如何选择路线？
图论模型：在一个连通的具有非负权的赋权图G中找一条包含每条边（允许重复）。
对该问题
(1) 若图G是一个欧拉图，则找出G的欧拉回路即可。
(2) 对一般图，其解法为：添加重复边以使G成为欧拉图G*，并使添加的重复边的边权之和为最小，再求G*的欧拉回路。
(3) 对恰有两个度数为奇的点的图G，可证：需要重复的边正好是从一个奇度点到另一个奇度点的最短路上的边，即问题为欧拉问题与最短路问题的综合。
说明:
(1) 若G是Euler图，则G的任何Euler环游都是最优环游.
(2) 若G 不是Euler图，用添加重复边以使G成为欧拉图G*
的方法时，添加的重复边具有的特征由定理3给出.
定理3 若W是图G中一条包含所有边的闭通道，则W在这样的闭通道中具有最短的长度的充要条件是：
(1) 每一条边最多重复经过一次；
(2) 在G的每一个圈上，重复经过的边的数目不超过圈的长度的一半
算法的思想 从任一点出发按下法来描画一条边不重复的迹，使在每一步中未描画的子图的割边仅当没有别的边可选择时才被描画。
Euler图中确定Euler环游的Fleury算法
Fleury算法
1. 任意选取一个顶点v0，置w0= v0。
2. 假设迹wi=v0e1v1…eivi已经选定，那么按下述方法从
E \ {e1,e2,…,ei}中选取边ei+1：使
(1) ei+1和vi相关联；
(2) 除非没有别的边可选择，否则ei+1 不是 G=G -{e1,e2,…,ei}的割边。
3. 当第2步不能再执行时，算法停止。
例
可证，Fleury算法是一个好算法。
例：某博物馆的一层布置如下图，其中边代表走廊，结点e是入口，结点g是礼品店，通过g我们可以离开博物馆。请找出从博物馆e进入，经过每个走廊恰好一次，最后从g处离开的路线。
a
f
e
d
c
b
i
h
g
j
解：图中只有两个奇度顶点e和g,因此存在起点为e,终点为g的欧拉迹。
为了在G中求出一条起点为e,终点为g的欧拉迹，在e和g间添加一条平行边m
a
f
e
d
c
b
i
h
g
j
m
用Fleury算法求出欧拉环游为：
emgcfabchbdhgdjiejge
所以：解为：egjeijdghdbhcbafcg
设G=(n, m)是欧拉图
由Fleury算法知：算法需要m次循环；
算法中主要运算是判断： ，该判断的时间复杂性是n2数量级的。
所以Fleury算法时间复杂性是：O(n2m), 是好算法。
算法复杂性分析
(2) 考查G’的圈, 若存在圈C,其中重复边的总长大于圈长的一半，则在圈C上交换重复边和不重复边得图G”.重复这个过程,直到得到一个图G*,在G*中没有重复边的总长大于圈长的一半的圈.
不是Euler图求最优环游的方法
(1) 用每条边最多添一条边的方法任意添一些重复边使图G 成为一个欧拉多重图G’.
(3) 用Fleury算法求G*的Euler环游.
例 图G如图(a)所示(各边权为1),它有10个奇度点。任意添一些边得到一个欧拉多重图(b)。
(b)中有色圈中重复边的数目为5，大于圈长8的一半，在这个圈上交换重复边和不重复边，得到(c)。
(c)，由(c)中每条欧拉闭迹对应原图一条闭通道，它含有所有的边且具有最短的长度。
(a)
(b)
(c)
§ 哈密尔顿图
经过图中每个点仅一次的路（圈）称为的Hamilton路 (圈)，存在Hamilton圈的图称为哈密尔顿图，简称H图。Hamilton路也简称H路。
只有哈密尔顿路，但不是哈密尔顿图
哈密尔顿图
无哈密尔顿路
例如
证明 设C 是G 中一条哈密尔顿圈