1、第 7-4讲 欧拉图与汉密尔顿图 1. 欧拉图2. 有向图中的欧拉路3. 周游世界问题4. 汉密尔顿图5. 标识法6.课堂练习7. 第 7-4讲 作业11、 欧拉图 （ 1）定义 1 设图 G无孤立结点，若存在一条路 (回路 )，经过图中每边一次且仅一次，则称该路 (回路 )为 欧拉路 (欧拉回路 ) 。具有欧拉回路的图叫 欧拉图例如，下图 具有欧拉路，而没有欧拉回路。从图中 v2出发 经过图中每边一次且仅一次到 v3可 得欧拉路：v2 v1 v3 v5 v4 v2 v3但此图不可能有 欧拉回路，因而不是欧拉图。21、 欧拉图 （ 2）定理 1 无向图 G有一条欧拉路，当且仅当 G连通，且有零
2、个或两个奇数度结点。证： 必要性。 设 图 G有欧拉路 v0e1v1e2v2.eiviei+1.ekvk，其中结点可重复出现，但边不重复，且每条边都经历一次，因此，欧拉路遍历 G中所有结点，所以 G是连通的。其次，若 vi不是端点，则 deg(vi)必为偶数；而对端点 v0和 vk，如果 v0=vk，则 G中无奇数度结点； 如果 v0vk，则 deg(v0)和deg(vk)必为奇数，故 G中有一对奇数度结点。充分性。 当 G连通，且有零个或两个奇数度结点。可按如下方法构造一条欧拉路。(1)若 G有两个奇数度结点 v0和 vk，因 G连通，可构造一条迹 (无重复边的路 )L1： v0e1v1e2
3、.vk；若 G无奇数度结点，则可从任何结点 vi出 发构造一条闭迹 L1： vie1v1e2.vi。31、 欧拉图 （ 3）定理 1 无向图 G有一条欧拉路，当且仅当 G连通，且有零个或两个奇数度结点。证： 充分性 (续 )。(2)如果 L1遍历 G的所有边，则 L1就是一条欧拉路。(3)如果 L1未遍历 G的所有边，则删除 L1的所有边及由此产生的孤立结点得子图 G ， G 中每个结点的度数应为偶数。因 G连通，所以 L1与 G 至少有一个结点 vj重 合，在 G 中从结点 vj出发可构造闭迹 L2。(4)如果 L1和 L2组合在一起恰为 G， 则得一条欧拉路，否则重复第 3步，如此下去，必
4、可得到一条经过图 G所有边的欧拉路。证明过程示意图：41、 欧拉图 （ 4）推论 无向图 G具有一条欧拉回路，当且仅当 G连通，且所有结点度数皆为偶数。由推论可知，七桥问题无解：右图中既无欧拉回路，又无欧拉路。52、有向图中的欧拉路定义 2 经过有向图中每边一次且仅一次的单向路 (回路 )称为 单向欧拉路 (回路 ) 。 欧拉路可推广到有向图。定理 2 有向图 G具有一条单向欧拉回路，当且仅当 G连通，且每个结点的入度等于出度。有向图 G具有一条单向欧拉路，当且仅当 G连通，且除两个结点之外，每个结点的入度等于出度。而这两个结点，一个结点的入度比出度大 1，另一个结点的入度比出度小 1。（证明
5、与定理 1类似，从略）63、 周游世界问题 （ 1）1859年， Willian Hamilton给 友人的信 中 首先谈到了关于12面体的数学游戏：将正 12面体的每个顶点看作一个城市，两个顶点间的连线视为旅行线，能否找到一条旅行线，经过每个城市恰好一次，再回到出发地？按右图中各顶点的数字标定的顺序给出了周游世界问题的一个解。73、 周游世界问题 （ 2）周游世界问题可视为在一个平面图中，从任一结点出发，找一条路，经过每个结点恰好一次，再回到出发点？遗憾的是，周游世界问题不象七桥问题那样有一个完满的结局，判定此类问题是否有解至今还未找到一个方便的充分必要条件。84、 汉密尔顿图 （ 1）定义
6、 3 经过图中每个结点一次且仅一次的路 (回路 ) 称为 汉密尔顿路 (汉密尔顿回路 )。具有汉密尔顿回路的图叫 汉密尔顿图例如，判断下面各图 是否为汉密尔顿图 。图 (1)中有汉密尔顿路，但不存在汉密尔顿 回 路，所以它不是汉密尔顿图；图 (2)中有汉密尔顿 回 路，它是汉密尔顿图；图 (3)中既无汉密尔顿 回 路，也不存在汉密尔顿路。94、 汉密尔顿图 （ 2）定理 3 若 无向图 G=是汉密尔顿图，任意 SV， 则W(G-S) |S|其中 W(G-S) 表示 G中删除 S后所得子图的连通分支数。证明 ： 设 c是 G中的一条 汉密尔顿回路 。(1) 如果 S中的结点在 c上两两相邻，则 W(c-S)=1 |S|。(2) 如果 S中的结点在 c上存在 r (2r|S|)个互不相邻的部分， 则 W(c-S)=r |S|。一般说来， S中的结点在 c上既有相邻的，又有不相邻的，所以总有 W(c-S) |S|。注意到 c-S 是 G-S的生成子图，故 W(G-S) W(c-S) |S|。10
