欧拉图与汉密尔顿图

7.4欧拉图与汉密尔顿图10/10/202317.4欧拉图与汉密尔顿图1/27一、哥尼斯堡七桥问题能否从河岸或小岛出发，通过每一座桥，且仅通过一次回到原地？问题10/10/20232第七章图论2/27欧拉通路（回路）

给定无孤立结点图G,若存在一条路,通过图中每边一次且仅一次,该条路称为欧拉路;若存在一条回路,通过图中每边一次且仅一次,该回路称为欧拉回路.存在欧拉回路图。欧拉图

10/10/202337.4欧拉图与汉密尔顿图3/27例1欧拉图欧拉路10/10/202347.4欧拉图与汉密尔顿图4/27定理1（欧拉定理）无向图G具有一条欧拉路充要条件是：1.图是连通；2.图中奇数度顶点个数是０个或2个.无向连通图G

是欧拉图充足必要条件是G

不含奇数度结点。推论10/10/202357.4欧拉图与汉密尔顿图5/27哥尼斯堡七桥问题图中奇数度结点个数是4个，因此不是欧拉图。10/10/202367.4欧拉图与汉密尔顿图6/27欧拉路构造若图G

有两个奇数度结点，则从其中一种结点开始，每次只取一条边，能够构造出一条达到另一种奇数度结点迹L1。若G中没有奇数度结点，则L1是闭合。若L1通过了G中所有边,则L1就是欧拉路。设G中去掉L1后得到子图G’，则G’每个结点度数为偶数。由于图G是连通，因此L1与G’最少有一结点vi

重合，在G’中由vi出发反复（1）办法，得到闭迹L2

.若L1与L2合在一起恰是图G,则得到欧拉路，结束；不然反复以上过程。设图G满足定理1条件，则构造欧拉路办法如下：10/10/202377.4欧拉图与汉密尔顿图7/27例2：一笔画判定问题10/10/202387.4欧拉图与汉密尔顿图8/27例2（续）房间通路一笔画能否从任意一种房间或外面出发，不反复地通过每一种房门？问题10/10/202397.4欧拉图与汉密尔顿图9/27例2（续）走遍花径10/10/2023107.4欧拉图与汉密尔顿图10/27定理2有向图中欧拉定理

连通有向图D具有有向欧拉回路充足必要条件是D

中每个结点入度等于出度。连通有向图D

具有有向欧拉路充要条件是：（1）除两个结点外，其他每个结点入度等于出度；（2）这两个结点中，一种结点入度比其出度大1，另一种结点入度比其出度小1。10/10/2023117.4欧拉图与汉密尔顿图11/27例3计算机鼓轮设计阴影表达导体1空白表达绝缘体0

鼓轮上16个部分如何安排导体和绝缘体,才能使鼓轮每转一部分,四个触点得到一组不一样四位二进制数？问题10/10/2023127.4欧拉图与汉密尔顿图12/27设有八个结点有向图，其结点分别记为三位二进制数。从结点a1a2a3能够引出两条有向边，其终点分别是a2a30以及a2a31。该两条边分别记为a1a2a30和a1a2a31。该图任一条路中，其邻接边必是a1a2a3a4和a2a3a4a5形式。上述问题能够看作是求该图中一条欧拉回路。e0e1e2e3e4e5e6e7e8e9e10e11e12e13e14e15000001100011110010101111e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8000010011010111110/10/2023137.4欧拉图与汉密尔顿图13/27例3（续完）0000100110101111能够推广到鼓轮具有n个触点情况10/10/2023147.4欧拉图与汉密尔顿图14/27二、汉密顿周游世界问题在左图所示十二面体中，能否找到一条回路，使它具有这个图所有结点？

10/10/2023157.4欧拉图与汉密尔顿图15/27汉密尔顿路（回路）

通过图中每个结点一次且仅一次通路(回路)。汉密尔顿图存在汉密尔顿回路图。10/10/2023167.4欧拉图与汉密尔顿图16/27例：汉密尔顿图汉密尔顿路10/10/2023177.4欧拉图与汉密尔顿图17/27例（续）汉密尔顿图汉密尔顿路10/10/2023187.4欧拉图与汉密尔顿图18/27定理3若图G=<V,E>具有汉密尔顿回路，则对于结点集V每个非空子集V1都有W(G-V1)≤|V1

|成立，其中W(G-V1)是G-V1中连通分支数.定理3给出是汉密顿图必要条件，能够用于判断一种图不是汉密尔顿图。注意10/10/2023197.4欧拉图与汉密尔顿图19/27例判断下列图是否为汉密尔顿图在G’中，取故G’不是汉密尔顿图10/10/2023207.4欧拉图与汉密尔顿图20/27彼得森(Peterssen)图彼得森图满足W(G-V1)≤|V1

|但它不是汉密顿图。彼得森图满足定理3条件图不一定是汉密尔顿图。10/10/2023217.4欧拉图与汉密尔顿图21/27定理4设Ｇ是有ｎ(n

3)

个结点无向简单图，假如G中任何一对结点度数之和

n-1，则Ｇ中存在一条汉密尔顿路。设Ｇ是有ｎ(n

3)

个结点无向简单图，假如G中任何一对结点度数之和

n，则Ｇ中存在一条汉密尔顿回路。推论定理4及其推论给出是具有汉密顿路（回路）充足条件。注意10/10/2023227.4欧拉图与汉密尔顿图22/27例两个结点度数之和都是4<6，但G是汉密尔顿图。10/10/2023237.4欧拉图与汉密尔顿图23/27例10/10/2023247.4欧拉图与汉密尔顿图24/27定理5

设n阶有向图D=<V,E>中,假如所有有向边均用无向边替代，所得无向图中含生成子图Kn,则有向图D中存在哈密顿通路。|V|

3有向完全图为哈密顿图。推论10