1、7-4 欧拉图和汉密尔顿图要求：1、理解欧拉图、汉密尔顿图的定义。2、掌握欧拉图的判定方法。3、会判断一些图不是汉密尔顿图。4、熟悉一些欧拉图和汉密尔顿图。一、欧拉图1、哥尼斯堡七桥问题ABCDn 近代图论的历史可追溯到 18世纪的 七桥问题 穿过 哥尼斯堡 城的七座桥， 要求每座桥通过一次且仅通过一次。七桥问题等价于在图中求一条回路，此回路经过每条边一次且仅有一次。欧拉在 1736年的论文中提出了一条简单的准则，确定了哥尼斯堡七桥问题是不能解的。2、欧拉图 (Euler) 如果无孤立结点图 G上有一条经过 G的 所有边一次且仅一次的路径，则称该路径为图 G的 欧拉路径欧拉路径 （Euler
2、walk）。如果图 G上有一条经过 G边一次且仅一次的的回路，则称该回路为图 G的 欧拉回路欧拉回路 。具有欧拉回路的图称为具有欧拉回路的图称为 欧拉图欧拉图 （ Euler graph）。定理 7-4.1 无向图 G具有一条 欧拉路 ，当且仅当 G连通，并且有零个或两个奇数度结点。 证明思路： 1) 先证必要性 :G有欧拉路 G连通连通 且（且（ 有有 0个个 或或 2个奇数度结点个奇数度结点 ）设设 G的欧拉路是点边序列 v0e1v1e2 ekvk， 其中结点可能重复，但边不重复。因欧拉路经过（所有边 ）所有结点，所以图G是连通的。对于任一非端点结点对于任一非端点结点 vi， 在欧拉路中每
3、当在欧拉路中每当 vi出现一次，必关出现一次，必关联两条边，故联两条边，故 vi虽可重复出现，但是虽可重复出现，但是 deg(vi)必是偶数。对于端点必是偶数。对于端点,若若 v0=vk ，则，则 deg(v0)必是偶数，即必是偶数，即 G中无奇数度结点中无奇数度结点 。若。若 v0 vk ，则，则 deg(v0)必是奇数，必是奇数， deg(vk)必是奇数必是奇数 ,即即 G中有两个奇数度结中有两个奇数度结点点 。 必要性证完。 2)再证充分性 :(证明过程给出了一种构造方法 )G连通连通 且（且（ 有有 0个个 或或 2个奇数度结点个奇数度结点 ） G有欧拉路 (1)若有若有 2个奇数度结
4、点个奇数度结点 ,则从其中一个结点开始构造一条迹则从其中一个结点开始构造一条迹 ,即从即从 v0出发经关联边出发经关联边 e1进入进入 v1,若若 deg(v1)为偶数为偶数 ,则必可由则必可由 v1再经再经关联边关联边 e2进入进入 v2,如此下去如此下去 ,每边仅取一次每边仅取一次 ,由于由于 G是连通的是连通的 ,故必可故必可到达另一奇数度结点停下到达另一奇数度结点停下 ,得到一条迹得到一条迹 L1:v0e1v1e2 ekvk。若。若 G中中没有奇数度结点没有奇数度结点 ,则从任一结点则从任一结点 v0出发出发 ,用上述方法必可回到结点用上述方法必可回到结点v0,得到一条闭迹。得到一条闭
5、迹。(2) 若若 L1通过了通过了 G的所有边的所有边 , L1就是一条欧拉路。就是一条欧拉路。(3) 若若 G中去掉中去掉 L1后得到子图后得到子图 G,则则 G中每个结点度数都为中每个结点度数都为偶数偶数 ,因为原来的图因为原来的图 G是连通的是连通的 ,故故 L1与与 G至少有一个结点至少有一个结点 vi重合重合 ,在在 G中由中由 vi出发重复出发重复 (1)的方法的方法 ,得到闭迹得到闭迹 L2。(4)当当 L1与与 L2组合组合 ,若恰是若恰是 G,得欧拉路得欧拉路 ,否则重复否则重复 (3),可得闭迹可得闭迹L3,依此类推可得一条欧拉路。依此类推可得一条欧拉路。 充分性证完 由于
6、有了欧拉路和欧拉回路的判别准则，因此哥尼斯堡七桥问题立即有了确切的否定答案，因为从图中可以看到 deg(A) 5， deg(B) deg(C) deg(D)=3，故欧拉回路必不存在。定理 7-4.1的推论 无向图 G具有一条 欧拉回路 ，当且仅当 G连通且所有结点度数皆为偶数。4、一笔画问题要判定一个图 G是否可一笔画出，有两种情况：n 一是从图 G中某一结点出发，经过图 G的每一边一次仅一次到达另一结点。n 另一种就是从 G的某个结点出发，经过 G的每一边一次仅一次再回到该结点。v1v2 v3v4 v5为欧拉路，有从 v2到 v3的一笔画。为欧拉回路，可以从任一结点出发，一笔画回到原出发点。5.定义 7-4.2：给定有向图 G， 通过图中每边一次且仅一次的一条单向路（回路），称作单向欧拉路（回路）。可以将 欧拉路和欧拉回路的概念推广到有向图中。6.定理 7-4.2 (1)有向图 G为具有一条 单向欧拉回路 ，当且仅当 G连通 ，并且每个结点的 入度等于出度。 (2)有向图 G有 单向欧拉路 ，当且仅当 G连通 ，并且恰有两个结点的入度与出度不等， 它们中一个的出度比入度多 1，另一个入度比出度多 1。证明思路与 定理 7-4.1类似
