离散数学第七章第四节

1、1第7-4讲 欧拉图与汉密尔顿图 1. 欧拉图2. 有向图中的欧拉路3. 周游世界问题4. 汉密尔顿图5. 标识法6.课堂练习7. 第7-4讲 作业21、欧拉图（1） 定义1 设图设图G无孤立结点，若存在一条路无孤立结点，若存在一条路(回路回路)，经过图中每，经过图中每边一次且仅一次，则称该路边一次且仅一次，则称该路(回路回路)为为欧拉路(欧拉回路) 。 具有欧拉回路的图叫具有欧拉回路的图叫欧拉图例如，下图例如，下图具有欧拉路，而没有欧拉回路。具有欧拉路，而没有欧拉回路。 从图中从图中v2出发出发经过图中每边一经过图中每边一次且仅一次到次且仅一次到v3可得欧拉路：可得欧拉路： v2 v1 v3

2、 v5 v4 v2 v3 但此图不可能有但此图不可能有欧拉回路，因欧拉回路，因而不是欧拉图。而不是欧拉图。31、欧拉图（2）定理1 无向图G有一条欧拉路，当且仅当G连通，且有零个或两个奇数度结点。证：必要性。设设图图G G有欧拉路有欧拉路v v0 0e e1 1v v1 1e e2 2v v2 2.e.ei iv vi ie ei+1i+1.e.ek kv vk k，其，其中结点可重复出现，但边不重复，且每条边都经历一次，因此，中结点可重复出现，但边不重复，且每条边都经历一次，因此，欧拉路遍历欧拉路遍历G G中所有结点，所以中所有结点，所以G G是连通的。是连通的。 其次，若其次，若v vi

3、i不是端点，则不是端点，则deg(vdeg(vi i) )必为偶数；而对端点必为偶数；而对端点v v0 0和和v vk k，如果如果v v0 0=v=vk k，则，则G G中无奇数度结点；如果中无奇数度结点；如果v v0 0 v vk k，则，则deg(vdeg(v0 0) )和和deg(vdeg(vk k) )必为奇数，故必为奇数，故G G中有一对奇数度结点。中有一对奇数度结点。 充分性。当当G G连通，且有零个或两个奇数度结点。可按如下连通，且有零个或两个奇数度结点。可按如下方法构造一条欧拉路。方法构造一条欧拉路。 (1)(1)若若G G有两个奇数度结点有两个奇数度结点v v0 0和和v

4、vk k，因，因G G连通，可构造一条迹连通，可构造一条迹 ( (无重复边的路无重复边的路)L)L1 1：v v0 0e e1 1v v1 1e e2 2.v.vk k；若；若G G无奇数度结点，则可从无奇数度结点，则可从任何结点任何结点v vi i出发构造一条闭迹出发构造一条闭迹L L1 1：v vi ie e1 1v v1 1e e2 2.v.vi i。41、欧拉图（3）定理1 无向图G有一条欧拉路，当且仅当G连通，且有零个或两个奇数度结点。证：充分性(续)。(2)(2)如果如果L L1 1遍历遍历G G的所有边，则的所有边，则L L1 1就是一条欧拉路。就是一条欧拉路。(3)(3)如果如

5、果L L1 1未遍历未遍历G G的所有边，则删除的所有边，则删除L L1 1的所有边及由此产生的的所有边及由此产生的孤立结点得子图孤立结点得子图GG，GG中每个结点的度数应为偶数。因中每个结点的度数应为偶数。因G G连连通，所以通，所以L L1 1与与GG至少有一个结点至少有一个结点v vj j重合，在重合，在GG中从结点中从结点v vj j出出发可构造闭迹发可构造闭迹L L2 2。(4)(4)如果如果L L1 1和和L L2 2组合在一起恰为组合在一起恰为G G，则得一条欧拉路，否则重复，则得一条欧拉路，否则重复第第3 3步，如此下去，必可得到一条经过图步，如此下去，必可得到一条经过图G G

6、所有边的欧拉路。所有边的欧拉路。证明过程示意图：51、欧拉图（4）推论 无向图G具有一条欧拉回路，当且仅当G连通，且所有结点度数皆为偶数。 由推论可知，七桥问题无解：右图中既无欧拉回路，又无欧拉路。62、有向图中的欧拉路 定义2 经过有向图中每边一次且仅一次的单向路经过有向图中每边一次且仅一次的单向路(回路回路)称为称为单向欧拉路(回路) 。 欧拉路可推广到有向图。欧拉路可推广到有向图。定理2 有向图G具有一条单向欧拉回路，当且仅当G连通，且每个结点的入度等于出度。有向图G具有一条单向欧拉路，当且仅当G连通，且除两个结点之外，每个结点的入度等于出度。而这两个结点，一个结点的入度比出度大1，另一

7、个结点的入度比出度小1。（证明与定理1类似，从略）73、周游世界问题（1） 1859年，Willian Hamilton给友人的信中首先谈到了关于12面体的数学游戏：将正12面体的每个顶点看作一个城市，两个顶点间的连线视为旅行线，能否找到一条旅行线，经过每个城市恰好一次，再回到出发地？ 按右图中各顶点的数字标定的顺序给出了周游世界问题按右图中各顶点的数字标定的顺序给出了周游世界问题的一个解。的一个解。83、周游世界问题（2） 周游世界问题可视为在一个平面图中，从任一结点出发，找一条路，经过每个结点恰好一次，再回到出发点？ 遗憾的是，周游世界问题不象七桥问题那样有一个完满遗憾的是，周游世界问题不

8、象七桥问题那样有一个完满的结局，判定此类问题是否有解至今还未找到一个方便的的结局，判定此类问题是否有解至今还未找到一个方便的充分必要条件。充分必要条件。94、汉密尔顿图（1） 定义3 经过图中每个结点一次且仅一次的路经过图中每个结点一次且仅一次的路(回路回路) 称为称为汉密尔顿路(汉密尔顿回路)。具有汉密尔顿回路的图叫。具有汉密尔顿回路的图叫汉密尔顿图 例如，判断下面各图例如，判断下面各图 是否为汉密尔顿图是否为汉密尔顿图。 图图(1)中有汉密尔顿路，但不存在汉密尔顿中有汉密尔顿路，但不存在汉密尔顿回回路，所以它不路，所以它不是汉密尔顿图；图是汉密尔顿图；图(2)中有汉密尔顿中有汉密尔顿回回路

9、，它是汉密尔顿图；路，它是汉密尔顿图；图图(3)中既无汉密尔顿中既无汉密尔顿回回路，也不存在汉密尔顿路。路，也不存在汉密尔顿路。104、汉密尔顿图（2） 定理3 若无向图无向图G=是汉密尔顿图，任意是汉密尔顿图，任意S V，则，则 W(G-S) |S|其中其中W(G-S)表示表示G中删除中删除S后所得子图的连通分支数。后所得子图的连通分支数。 证明：设设c是是G中的一条汉密尔顿回路中的一条汉密尔顿回路。 (1) 如果如果S中的结点在中的结点在c上两两相邻，则上两两相邻，则W(c-S)=1 |S|。 (2) 如果如果S中的结点在中的结点在c上存在上存在 r (2 r |S|)个互不相邻的部分，个

10、互不相邻的部分，则则W(c-S)=r |S|。 一般说来，一般说来，S中的结点在中的结点在c上既有相邻的，又有不相邻的，上既有相邻的，又有不相邻的，所以总有所以总有W(c-S) |S|。 注意到注意到c-S 是是G-S的生成子图，故的生成子图，故W(G-S) W(c-S) |S|。114、汉密尔顿图（3）定理3 若无向图无向图G=是汉密尔顿图，任意是汉密尔顿图，任意S V，则，则 W(G-S) |S|，其其中中W(G-S)表示表示G中删除中删除S后所得子图的连通分支数。后所得子图的连通分支数。 定理定理3只是汉密尔顿图的必要条件。如果图只是汉密尔顿图的必要条件。如果图G不满足这个条不满足这个条

11、件，则件，则G肯定不是汉密尔顿图。肯定不是汉密尔顿图。可利用定理3来判断一个图不是汉密尔顿图。因为因为 W(G-a,b,c,d,e,f,g) =9| a,b,c,d,e,f,g |=7，所以图所以图G不是汉密尔顿图。汉密尔顿图。124、汉密尔顿图（4）定理3 若无向图无向图G=是汉密尔顿图，任意是汉密尔顿图，任意S V，则，则 W(G-S) |S|，其其中中W(G-S)表示表示G中删除中删除S后所得子图的连通分支数。后所得子图的连通分支数。4 即使图即使图G满足定理满足定理3的条件，也不能肯定的条件，也不能肯定G是汉密尔顿图。是汉密尔顿图。如著名的彼德森图就是一例，它满足定理如著名的彼德森图就

12、是一例，它满足定理3的条件，但它不是的条件，但它不是汉密尔顿图。汉密尔顿图。 (1)删除删除1个或个或2个结点仍是连通图。个结点仍是连通图。 (2)删除删除3个结点，最多得个结点，最多得2个连通分个连通分支的子图。支的子图。 (3)删除删除4个结点，最多得个结点，最多得3个连通分个连通分支的子图。支的子图。 (4)删除删除5个或个或5个结点，则所得子图个结点，则所得子图的结点数已不大于的结点数已不大于5，从而排除了出现，从而排除了出现5个以上连通分支的可能性。个以上连通分支的可能性。134、汉密尔顿图（5） 定理4 设G是具有n个结点的简单图，如果图中每对结点度数之和大于或等于n-1，则G中存

13、在一条汉密尔顿路（证明略）（证明略） 到目前为止，判断一个图是否为到目前为止，判断一个图是否为汉密尔顿图还只能依据定汉密尔顿图还只能依据定义。只有部分满足特定条件的图才能用判别法（充分条件）义。只有部分满足特定条件的图才能用判别法（充分条件）推论 设G是具有n个结点的无向简单图，如果G中任一对结点度数之和都大于等于n，则G是汉密尔顿图 （证明从略）（证明从略） 注意：注意：本推论与定理本推论与定理4一样，它只不过是充分条件，而非一样，它只不过是充分条件，而非必要条件。不满足定理中条件的图，也可能是汉密尔顿图。必要条件。不满足定理中条件的图，也可能是汉密尔顿图。 例如，例如，下面的图是具有下面的

14、图是具有6 6个结点的无向简单图，它显然是个结点的无向简单图，它显然是汉密尔顿图汉密尔顿图，但该图中任一对结点度数之和等于，但该图中任一对结点度数之和等于4，并不大，并不大于等于图中结点总数于等于图中结点总数6！145、标识法（1） 判断图G中是否存在汉密尔顿路或汉密尔顿回路，除按定义来判断之外，没有一个充分必要条件可以依从，也就是说，没有确定的判断方法。下面的标识法是一个可作参照的方法，但它既不是必要条件，也不是充分条件。标识法的步骤如下: (1)先用字母先用字母A标识图中任一结点标识图中任一结点,接着用接着用B标识图中与标识图中与A邻接邻接的结点。然后再用字母的结点。然后再用字母A标识图中与标识图中与B邻接的结点，如此下去，邻接的结点，如此下去，直到图中所有结点标识完毕。直到图中所有结点标识完毕。 (2)在标识过程中，当无法实现在标识过程中，当无法实现A、B相间时，可在某些边上相间时，可在某些边上增加二度结点。增加二度结点。 (3)标识完毕后，如果若标识完毕后，如果若A、B数目差一个以上，则该图不存数目差一个以上，则该图不存在汉密尔顿回路。在汉密尔顿回路。 155、标识法（2） 标识法举例： 左经标识后，用左经标识后，用7个个A，8个个B，故该图没