福州大学：《离散数学》课程教学资源（课件讲稿）第十五章 欧拉图与哈密顿图

15.1欧拉图 ■欧拉通路 ■欧拉回路 ■欧拉图 ■半欧拉图

欧拉通路 欧拉回路 欧拉图 半欧拉图 15.1 欧拉图

哥尼斯堡七桥问题 D 欧拉图是能一笔画出的边不重复的回路

哥尼斯堡七桥问题 欧拉图是能一笔画出的边不重复的回路

哥尼斯堡七桥问题 从前，一个称为哥尼斯堡城的城市有一条横贯全市的 普雷格尔河，河中有两个小岛，用七座桥将岛和岛，河岸 和岛连接起来，如图9.32所示。18世纪中叶，该城市的人们 提出了一个问题：能否不重复的走完七桥，最后回到原地。 城中的很多人试图解决这个问题，然而试验者都以失败告 终。1736年瑞士的数学家列昂哈德·欧拉(Leonhard Euler) 发表了一篇论文《哥尼斯堡七桥问题》，这篇论文的基本 内容就是定理15.1。在这篇论文中第一次论证了这个问题是 无解的。他将河岸和岛抽象成图的结点，而把桥画成相应 的连接边，如图9.33所示。于是，不重复的走完七桥，最后 回到原地，等价于图中存在一条回路，经过每一条边一次 且仅一次，即图中存在欧拉回路。因为图中的四个结点的 度数都是奇数。所以图中不存在欧拉回路

哥尼斯堡七桥问题 从前，一个称为哥尼斯堡城的城市有一条横贯全市的 普雷格尔河，河中有两个小岛，用七座桥将岛和岛，河岸 和岛连接起来，如图9.32所示。18世纪中叶，该城市的人们 提出了一个问题：能否不重复的走完七桥，最后回到原地。 城中的很多人试图解决这个问题，然而试验者都以失败告 终。1736年瑞士的数学家列昂哈德·欧拉(Leonhard Euler) 发表了一篇论文《哥尼斯堡七桥问题》，这篇论文的基本 内容就是定理15.1。在这篇论文中第一次论证了这个问题是 无解的。他将河岸和岛抽象成图的结点，而把桥画成相应 的连接边，如图9.33所示。于是，不重复的走完七桥，最后 回到原地，等价于图中存在一条回路，经过每一条边一次 且仅一次，即图中存在欧拉回路。因为图中的四个结点的 度数都是奇数。所以图中不存在欧拉回路

图9.32 图9.33

欧拉图 欧拉通路：图中行遍所有顶点且恰好经过每条边一次的通路 欧拉回路：图中行遍所有顶点且恰好经过每条边一次的回路 欧拉图：有欧拉回路的图 半欧拉图：有欧拉通路而无欧拉回路的图. 几点说明： 上述定义对无向图和有向图都适用. 规定平凡图为欧拉图. 欧拉通路是简单通路，欧拉回路是简单回路. 环不影响图的欧拉性

欧拉图 欧拉通路: 图中行遍所有顶点且恰好经过每条边一次的通路. 欧拉回路: 图中行遍所有顶点且恰好经过每条边一次的回路. 欧拉图: 有欧拉回路的图. 半欧拉图: 有欧拉通路而无欧拉回路的图. 几点说明： 上述定义对无向图和有向图都适用. 规定平凡图为欧拉图. 欧拉通路是简单通路, 欧拉回路是简单回路. 环不影响图的欧拉性

欧拉图（续） 例图中，(1)，(4)为欧拉图；(2)，（⑤）为半欧拉图；(3)，(6既不 是欧拉图，也不是半欧拉图， 在3)，(6)中各至少加几条边才能成为欧拉图？ C1 3 s (2) (3) (4) (5) (6)

欧拉图(续) 例 图中, (1), (4)为欧拉图; (2), (5)为半欧拉图; (3)，(6)既不 是欧拉图, 也不是半欧拉图. 在(3), (6)中各至少加几条边才能成为欧拉图?

欧拉图的判别法 定理15.1无向图G具有一条欧拉路当且仅当G是 连通的且有零个或两个奇度顶点。 证明：设G具有一条欧拉路，下证G是连通的且有零 个或两个奇度顶点。 设G中有一条欧拉路L:eye22.eyk,该路经过 G的每一条边。因为G中无孤立顶点，所以该路经过G的 所有项点，即G的所有项点都在该路上。故G中任意两 个顶点连通，从而G是连通图

定理15.1 无向图G具有一条欧拉路当且仅当G是 连通的且有零个或两个奇度顶点。 证明：设G具有一条欧拉路，下证G是连通的且有零 个或两个奇度顶点。 设G中有一条欧拉路L：v0 e1 v1 e2 v2 „ek vk，该路经过 G的每一条边。因为G中无孤立顶点，所以该路经过G的 所有顶点，即G的所有顶点都在该路上。故G中任意两 个顶点连通，从而G是连通图。 欧拉图的判别法

设y是图G的任意顶点，若y,不是L的端点，每当沿L 经过，一次都经过该顶点关联的两条边，为该顶点的度 数增加2。由于G的每一条边都在该路上，且不重复，所 以，的度数必为偶数。若是L的端点'，当=y时，则 和y的度数也为偶数，即G中无奇度顶点；当时， 则y,和y的度数均为奇数，即G中有两个奇度顶点

设vi是图G的任意顶点，若vi不是L的端点，每当沿L 经过vi一次都经过该顶点关联的两条边，为该顶点的度 数增加2。由于G的每一条边都在该路上，且不重复，所 以vi的度数必为偶数。若vi是L的端点v0，当v0 =vk时，则 v0和vk的度数也为偶数，即G中无奇度顶点；当v0 ≠vk时， 则v0和vk的度数均为奇数，即G中有两个奇度顶点

设G是连通图，有零个或两个奇度顶点，用下述方法 构造一条欧拉路： ①若G中有两个奇度顶点，则从其中的一个开始 构造一条简单路。 从y出发经关联边e进入y,若y是偶数度顶点，则 必可以由y,经关联边e2进入2。如此下去，每边只取一次。 由于G是连通图，必可到达另一个奇度顶点y,从而得 到一条简单路L1:yoe1y122·kk

设G是连通图，有零个或两个奇度顶点，用下述方法 构造一条欧拉路： ①若G中有两个奇度顶点，则从其中的一个v0开始 构造一条简单路 。 从v0出发经关联边e1进入v1，若v1是偶数度顶点，则 必可以由v1经关联边e2进入v2。如此下去，每边只取一次。 由于G是连通图，必可到达另一个奇度顶点vk，从而得 到一条简单路L1：v0 e1 v1 e2 v2 „ ek vk

若G中无奇度顶点，则从任意顶点y,出发，用上述 方法必可回到顶点，得到一条简单回路L1: Voe]ve2v2Vo ②若L经过G的所有边，则L就是欧拉路。 ③否则，在G中删除L,得子图G,则G中的每一 个顶点的度数为偶数。因为G是连通图，故L,和G至少 有一个顶点y,重合，在G中由y出发重复①，得到简单 回路L2 ④若L,与L,组合在一起恰是G,则得到了欧拉路， 否则，重复③可得到简单回路L3 以此类推直到得到一条经过G中所有边的欧拉路

若G中无奇度顶点，则从任意顶点v0出发，用上述 方法必可回到顶点 v0 ， 得到一条简单回路 L1 ： v0 e1 v1 e2 v2 „v0。 ②若L1经过G的所有边，则L1就是欧拉路。 ③否则，在G中删除L1，得子图G′ ，则G′中的每一 个顶点的度数为偶数。因为G是连通图，故L1和G′至少 有一个顶点vi重合，在G′中由vi出发重复①，得到简单 回路L2。 ④若L1与L2组合在一起恰是G，则得到了欧拉路， 否则，重复③可得到简单回路L3。 以此类推直到得到一条经过G中所有边的欧拉路