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