1、7.4 欧拉图与汉密尔顿图 1 欧拉图 定义 7-4.1 ： 给定 无孤立结点图 G，若存在一条路，经过图中每边一次且仅一次，该条路称为 欧拉路 ；若存在一条回路，经过图中每边一次且仅一次，该回路称为 欧拉回路 。具有欧拉回路的图称作 欧拉图 。7.4 欧拉图与汉密尔顿图2 定理 7-4.1 无向图 G具有一条欧拉路，当且仅当 G是连通的，且有零个或两个奇数度结点。 证明1) 先证必要性 :G有欧拉路 G连通连通 且（且（ 有有 0个个 或或 2个奇数度结点个奇数度结点 ）设设 G的欧拉路是点边序列 v0e1v1e2 e kvk，其中结点可能重复，但边不重复。因欧拉路经过（所有边 ）所有结点，
2、所以图 G是连通的。对于任一非端点结点对于任一非端点结点 vi，在欧拉路中每当，在欧拉路中每当 vi出现依次，必关联两条边，故出现依次，必关联两条边，故vi虽可重复出现，但是虽可重复出现，但是 deg(vi)必是偶数。对于端点必是偶数。对于端点 ,若若 v0=vk ，则，则 deg(v0)必是必是偶数，即偶数，即 G中无奇数度结点中无奇数度结点 。若。若 v0v k ，则，则 deg(v0)必是奇数，必是奇数， deg(vk)必是必是奇数奇数 ,即即 G中有两个奇数度结点中有两个奇数度结点 。 必要性证完。 7.4 欧拉图与汉密尔顿图2)再证充分性 :(证明过程给出了一种构造方法 )G连通连通
3、 且（且（ 有有 0个个 或或 2个奇数度结点个奇数度结点 ） G有欧拉路 (1)若有若有 2个奇数度结点个奇数度结点 ,则从其中一个结点开始构造一条迹则从其中一个结点开始构造一条迹 ,即从即从 v0出发经关联边出发经关联边 e1进入进入 v1,若若 deg(v1)为偶数为偶数 ,则必可由则必可由 v1再经关联边再经关联边 e2进入进入v2,如此下去如此下去 ,每边仅取一次每边仅取一次 ,由于由于 G是连通的是连通的 ,故必可到达另一奇数度结点故必可到达另一奇数度结点停下停下 ,得到一条迹得到一条迹 L1:v0e1v1e2 e kvk。若。若 G中没有奇数度结点中没有奇数度结点 ,则从任一结则
4、从任一结点点 v0出发出发 ,用上述方法必可回到结点用上述方法必可回到结点 v0,得到一条闭迹。得到一条闭迹。(2) 若若 L1通过了通过了 G的所有边的所有边 , L1就是一条欧拉路。就是一条欧拉路。(3) 若若 G中去掉中去掉 L1后得到子图后得到子图 G ,则则 G 中每个结点度数都为偶数中每个结点度数都为偶数 ,因因为原来的图为原来的图 G是连通的是连通的 ,故故 L1与与 G 至少有一个结点至少有一个结点 vi重合重合 ,在在 G 中由中由 vi出出发重复发重复 (1)的方法的方法 ,得到闭迹得到闭迹 L2。(4)当当 L1与与 L2组合组合 ,若恰是若恰是 G,得欧拉路得欧拉路 ,
5、否则重复否则重复 (3),可得闭迹可得闭迹 L3,依依此类推可得一条欧拉路。此类推可得一条欧拉路。 充分性证完由于有了欧拉路和欧拉回路的判 别 准 则 ，因此哥尼斯堡七 桥问题 立即有了确切的否定答案，因 为 从图 中可以看到 deg(A) 5， deg(B) deg(C)deg(D)=3，故欧拉回路必不存在。3.定理 7-4.1的推论 无向图 G具有一条 欧拉回路 ，当且仅当 G连通且所有结点度数皆为偶数。7.4 欧拉图与汉密尔顿图7.4 欧拉图与汉密尔顿图 一笔画 问题： 就是 判断一个图形能否一笔画 成 实质上就是判断图形 是否存在欧拉路径和欧拉回路的问题 。例如 ,下 图 (a)和 (
6、b)均可一笔画成 ,因为符合存在欧拉路径和欧拉回路条件。见 303页图 7- 4.3 (a)为 欧拉路 ，有从v2到 v3的一笔画。(b)为 欧拉回路 ，可以从任一 结 点出 发，一笔画回到原出发 点。V2 V3V1V4 V5V2 V3V1V4 V5311页 (3) 完全图 Kn每个结点的度数为 n-1，要使 n-1为偶数，必须 n为奇数。故当 n为奇数时，完全图 Kn有欧拉回路。练习311页 3）5.定义 7-4.2：给定有向图 G，通过图中每边一次且仅一次的一条单向路（回路），称作单向欧拉路（回路）。可以将 欧拉路和欧拉回路的概念推广到有向图中。6.定理 7-4.2 有向图 G具有 一条 单向欧拉回路 ， 当且仅当 G连通 ，并且每个结点的 入度等于出度 。有向图 G有 单向欧拉路 ， 当且仅当 G连通 ，并且恰有两个结点的入度与出度不等， 它们中一个的出度比入度多 1，另一个入度比出度多 1。证明思路与定理 7-4.1类似
