【免费】图论讲义71资源-CSDN文库

需积分: 0 121 浏览量 2022-08-03 23:29:26 上传评论收藏 673KB PDF 举报

资源详情

资源评论

资源推荐

第四章 Euler 环游和 Hamilton 圈

§4.1 Euler 环游

°

Euler 迹：经过图 G 的每条边的迹称为 G 的 Euler 迹。

°

Euler 环游：经过图 G 的每条边恰好一次的闭迹。（图 G 的环游是指

经过 G 的每条边至少一次的闭途径）。

*一笔画问题：

°

Euler 图：一个图若包含 Euler 环游，则这个图称为 Euler 图。

°

半 Euler 图：一个图若包含 Euler 迹，但不包含 Euler 环游，则这个图

称为半 Euler 图。

*哥尼斯堡七桥问题：

定理 4.1：一个非空连通图是 Euler 图当且仅当它没有奇点。

证：设 G 是 Euler 图，C 是 G 的 Euler 环游，其起点(也是终点)为 u。

顶点 v 作为 C 的内部顶点每出现一次，就有两条与它关联的边出现，

因为 Euler 环游包含 G 的每条边，所以对于所有的

v ≠ u

，

d(v)

都是

偶数。类似地，由于 C 开始并且终止于 u，所以

d(u)

也是偶数。于是，

G 没有奇点。

反之，假设 G 是一个非 Euler 连通图：它至少有一条边，而且没有

奇点。选择这样一个图 G，使其具有尽可能少的边。由于 G 的每个顶

点的度至少是 2，所以 G 包含一个闭迹。设 C 是 G 中其长为最大的闭

迹。根据假设，C 不是 G 的 Euler 环游，因而

G − E(C)

具有适合

ε G

'

> 

的某个分支

G'

。由于 C 本身是 Euler 图，它没有奇点；于是

连通图

G'

也没有奇点。由于

ε G

'

<  G ,

根据 G 的选择可以推知：

G'

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余6页未读，立即下载

评论0

内容反馈

chenbtravel

粉丝: 17
资源: 296

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip