离散数学 贾振华 第八章 欧拉图与哈密尔顿图

《离散数学 贾振华 第八章 欧拉图与哈密尔顿图》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8章欧拉图与哈密尔顿图本章学习目标本章主要介绍了从实际问题引出的两个特殊的图：欧拉图和哈密尔顿图。通过本章学习，读者应该掌握以下内容：（1）欧拉通路、欧拉回路、欧拉图和半欧拉图的概念（2）欧拉图和半欧拉图的判定准则（3）哈密尔顿通路、哈密尔顿回路、哈密尔顿图和半哈密尔顿图的概念（4）哈密尔顿图和半哈密尔顿图的判定准则主要内容8.1欧拉图8.1.1欧拉图的定义8.1.2欧拉图的判定8.1.3求欧拉回路的算法8.1.4欧拉图的应用8.2哈密尔顿图8.1欧拉图8.1.1欧拉图的定义(a)(b)定义8.1.1（1）通过图中所有边一次且仅一次行遍所有顶点的通路，称为欧拉通路；（2）通过图中

2、所有边一次且仅一次行遍所有顶点的回路，称为欧拉回路；（3）具有欧拉回路的图，称为欧拉图；（4）具有欧拉通路但无欧拉回路的图，称为半欧拉图。8.1欧拉图8.1.1欧拉图的定义(a)(b)在图8.1-1中，（a）存在欧拉通路，但不存在欧拉回路，因而它不是欧拉图。而（b）中存在欧拉回路，所以（b）是欧拉图。8.1欧拉图8.1.2欧拉图的判定(a)(b)定理8.1.1无向图是欧拉图，当且仅当是连通的，且中所有顶点的度数都是偶数。推论无向连通图中存在欧拉回路，当且仅当中所有顶点的度数都是偶数。8.1欧拉图8.1.2欧拉图的判定(a)(b)定理8.1.2无向图是半欧拉图，当且仅当是连通的，且只

3、有两个顶点的度数为奇数，而其他顶点的度数为偶数。证明设图G中度数为奇数的顶点为u，v，在图G中附加一条新边，从而形成一个新图G’。于是，G有一条u与v间的欧拉通路，当且仅当G’有一条欧拉回路。这也就是说，G有一条u与v间的欧拉通路，当且仅当G’是连通的，且所有顶点的度数都是偶数，从而当且仅当G是连通的，且只有u,v的度数为奇数，而其余顶点的度数均为偶数。推论无向连通图中顶点与间存在欧拉通路，当且仅当中与的度数为奇数，而其他顶点的度数为偶数。8.1欧拉图8.1.2欧拉图的判定图8.1-2图8.1-38.1欧拉图8.1.2欧拉图的判定定理8.1.3有向图是欧拉图，当且仅当是强连通的，且

4、中每个顶点的入度都等于出度。定理8.1.4有向图是半欧拉图，当且仅当是单向连通的，且中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其他顶点的入度都等于出度。8.1欧拉图8.1.3求欧拉回路的算法设G为欧拉图，一般说来，G中存在若干条欧拉回路，下面介绍一种求欧拉回路的算法—Fleury算法。算法如下：（1）任取v0∈V(G)，P0=V0令；（2）设Pi=v0e1v1e2…eivi已经行遍，按下面方法从E(G)-{e1,e2,…ei}中选取ei+1：（a）ei+1与vi相关联；（b）除非无别的边可供行遍，否则ei+1不应该为Gi=G-(e1e2…ei)中的割边

5、（桥）；（3）当（2）不能再进行时，算法停止。8.1欧拉图8.1.3求欧拉回路的算法例如在图8.1-4中，就是图的一条欧拉回路。8.1欧拉图8.1.4欧拉图的应用欧拉图的应用，计算机旋转鼓轮的设计原理。将旋转鼓轮的表面分成2n段，例如，将图8.1-5所示的旋转鼓轮的表面分成24=16段，每段由绝缘体或导电体组成，绝缘体将给出信号0，导电体将给出信号1。鼓轮的表面还有4个触点0，根据鼓轮的一个确定位置，就可读出一个4位二进序列。在图8.1-5中，按当时确定的位置，读出的数为1101，鼓轮按顺时针方向旋转一格，下一个读数为1010。8.1欧拉图8.1.4欧拉图的应用欧拉图的应用，计算机

6、旋转鼓轮的设计原理。我们要设计成这样的旋转鼓轮表面，当鼓轮旋转一周后，能够读出0000～1111的16个不同的二进制数。8.1欧拉图8.1.4欧拉图的应用欧拉图的应用，计算机旋转鼓轮的设计原理。现在构造一个有向图G，G有8个顶点，每个顶点分别表示000～111的一个二进制数。设αi∈{0，1}，从顶点α1α2α3引出两条有向边，其终点分别为α2α30和α2α31，这两条边分别为α1α2α30以及α1α2α31，按照此种方法，对于八个顶点的有向图共有16条边，在这个图的任意一条通路中，其邻接的边必是αiαjαkαt和αjαkαtαs的形式，即前一条有向边的后3位与后一条有向边的前3位

7、相同。因为图中的16条边被记成不同的4位二进制信息，即对应于图中的一条欧拉回路。8.1欧拉图8.1.4欧拉图的应用在图8.1-6中，每个顶点的入度等于2，出度等于2，所以在图中至少存在一条欧拉回路，如（e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8），根据邻接边的标记方法，这16个二进制数可写成对应的二进制序列0000100110101111。把这个序列排成环状，即与所求的鼓轮相对应。8.2哈密尔顿图8.2.1哈密尔顿图周游世界问题图8.