3.1Euler环游解析.ppt

* Chapter3 Euler图和Hamilton图 §3.1-3.2 Euler环游 七桥问题也就是找对应图中的一条经过每条边一次且仅一次的闭迹，也即环游所有边一次且仅一次的闭迹。这个问题是由数学家Euler解决的，因此我们把满足这一条件的闭迹称为Euler环游。 返回 结束 返回 结束 一、定义 ： 1. Euler迹：经过 的每条边的迹称为Euler迹（边不重复）； 如例1中图(a)的迹 是欧拉迹 例 1 (a) (b) (c) 3.Euler通路：起点与终点不同的Euler迹称为Euler通路。 如例1中图(b)的闭迹 是Euler环游。 2. Euler环游：闭的Euler迹称为Euler环游。 若 有Euler环游，则 为Euler图； 返回 结束 注记： 1.研究Euler迹的问题称为Euler问题。 2.并不是所有图都是有Euler迹的，如例1(c)就不存在Euler迹。 3.一笔画问题与Euler问题。 二、性质（Euler图的判别问题） 1、Euler图 返回 结束 定理3.1.1 一个非平凡连通图 是Euler图当且仅当 没有奇点。 必要性：显然。 充分性：对 的边数用数学归纳法。由于 无奇点，有回路 ，则 的每个非平凡连通分支是连通没有奇点的，有Euler环游 ，将每个 连起来就可 得 的Euler环游。 返回 结束 用此定理很容易判断一个图是否是Euler图，此外，用Fleury算法可以求Euler图的Euler环游。 Fleury算法： 1、任意选取一个顶点 ，置 ； 2、假定迹 已经选出，那么用下列方法从 中选取 , 满足 (1) 与 关联； (2)除非没有别的边可选择， 不是 的割边。 3、当2不能执行时，停止。否则让 ，转2。 定理3.1.2 若G是Euler图，则G的任何用 Fleury算法构成的迹都是Euler环游。 定理3.1.3 一个非平凡连通图 有Euler通路当且仅当 恰好有两个奇点。 证：必要性：见前面分析过程。 充分性：设 是 中仅有的两个奇点，则 连通无奇点，有Euler环游 ，则 是 的一条Euler通路。 若 有Euler通路, 设 的Euler通路为： 。若 在 的内部出现 次， 即 仅有两个奇点。而 恰有两个奇点也是 有Euler通路的一个 充分条件。 2、Euler通路 证明巧妙的借鉴了定理4.1.1的结果 返回 结束 性质 一个非平凡连通图 有Euler迹当且仅当 至多有两个奇点. 这个结论其实也给出了一个给定的图形可以一笔画的判别方法. 返回 结束 图1有欧拉通路，图3是欧拉图，两个图都能一笔画。 3、k-笔不重复画问题 返回 结束 性质 图形K可以用 一 笔不重复画成 当且仅当 图形K 所对应的图G(K)含有Euler迹。 问题一：下面这个图能用几笔不重复的画成？ 返回 结束 定理3.1.4 若连通图 恰好有 个奇点，则在 中存在 条边不交的迹 ，使得 推论3.1.5 设图形K 所对应的图G(K)连通，且恰有 个奇点，则图形K可以用 笔不重复画成，且至少要用 笔不重复画成。 *