离散数学7.4-6

《离散数学7.4-6》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、7-4Euler图与Hamilton图一、Euler图哥尼斯堡七桥问题：09:53:081离散数学无向的Euler图1.无向的Euler图定义给定G是一个无孤立结点的无向图，若存在一条路(回路)，经过图中每边一次且仅一次，则称此路(回路)为该图的一条欧拉路(回路)。具有欧拉回路的图称为欧拉图。如何判断一个图是否是欧拉图或存在欧拉路呢？09:53:082离散数学判断欧拉图及欧拉路的方法定理无向图G＝具有一条欧拉路当且仅当G是连通的，且仅有零个或者两个奇度数结点。推论无向图G＝是欧拉图当且仅当G是连通的，且G的所有结点的度数都为偶数。七桥问题存在答案吗？0

2、9:53:083离散数学证明1)、若G＝(1，0)是一个平凡图，则定理显然成立。下面讨论G是非平凡图的情况。“”设G具有一条Euler路L。①设该欧拉路L＝v0e1v1e2v2e3……ekvk。即从v0出发，经过结点v1，v2，……vk-1，边e1，e2……ek到达vk，其中的结点可以重复出现，但边不重复，并且L中的边是包括了G中所有的边。由于G中无孤立结点，因而L经过了G中的所有结点，所以G是连通的。②对于欧拉路L的任意非端点的结点vi，在L中每出现vi一次，都关联着G中的两条边，而当vi又重复出现时，它又关联着G中的另外的两条边，由于在通路L中边不可能重复出现，因而vi每

3、出现一次，都将使得结点vi的度数增加2度，若vi在路中重复出现j次，则deg(vi)＝2j。09:53:084离散数学证明(续1)。若端点v0vk，设v0，vk在通路中作为非端点分别出现j1次和j2次，v0，vk每出现一次，都将使得结点v0，vk的度数增加2度，而v0，vk作为端结点时，仅仅只出现一次，且在其v0，vk的度数上只增加1度，则v0，vk的总度数分别是：deg(v0)＝2j1+1，deg(vk)＝2j2+1。综上所述，即G仅仅只有两个奇度数结点，即两个端结点v0，vk的度数为奇数。若端点v0＝vk，则G中的所有结点在通路中都可看成为非端点，由上可知，每个结

4、点的度数都是偶数，即G中仅有零个奇度数结点。09:53:085离散数学“”构造性证明。证明(续2)若有两个奇度数结点。则我们从两个度数为奇数的结点之一开始构造一条欧拉路，以每条边最多经过一次的方式通过图中的边。对于度数为偶数的结点，通过一条边进入这个结点，总可以通过一条未经过的边离开这个结点，因此，这样的构造过程一定以到达另一个度数为奇数的结点而告终(若无度数为奇数的结点，则以回到原出发点而告终)。如果图中所有的边已用这种方式经过了，显然这就是所求的欧拉路。如果这个图中不是所有的边都经过了，我们将去掉已经过的边，得到一个由剩余的边组成的子图，这个子图的所有结点的度数均为偶

5、数。因为原来的图是连通的，因此，这个子图必与我们已经过的路在一个或多个结点相接。09:53:086离散数学证明(续3)由这些结点中的一个开始我们再通过边构造路，因为结点的度数全为偶数，因此，这条路一定最终回到起点。我们将这条回路加到已构造好的路中间组合成一条路。如有必要，这一过程重复下去，直到我们得到一条通过图中的所有边的路，即欧拉路。若有零个奇度数结点。则我们可从任意一个结点出发重复上述过程即可。2)、该结论直接是1)的推广。■09:53:087离散数学例由定理容易看出：是欧拉图；不是欧拉图，但存在欧拉路；即不是欧拉图，也不存在欧拉路。09:53:088离散数学例(蚂蚁比

6、赛问题)解在图中，仅有两个度数为奇数的结点b，c，因而存在从b到c的欧拉路，蚂蚁乙走到c只要走一条欧拉路，边数为9条。而蚂蚁甲要想走完所有的边到达c，至少要先走一条边到达b，再走一条欧拉路，因而它至少要走10条边才能到达c，所以乙必胜。甲、乙两只蚂蚁分别位于如下图中的结点a，b处，并设图中的边长度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点c处。如果它们的速度相同，问谁先到达目的地？09:53:089离散数学例一笔画问题—图G是否可一笔画出对于上图，有图(a)是能一笔画并且能回到出发点的，图(b)也能一笔画但不能回到出发点的。09:53:0

7、810离散数学有向的Euler图2.有向的Euler图定义给定G是一个无孤立结点的有向图，若存在一条单向路(回路)，经过图中每边一次且仅一次，则称此单向路(回路)为该图的一条单向欧拉路(回路)。具有单向欧拉回路的图称为欧拉图。如何判断一个有向图是否是欧拉图或存在单向欧拉路呢？09:53:0811离散数学判断欧拉图及欧拉通路的方法定理有向图G＝具有一条单向欧拉路当且仅当G是连通的，且除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大1，另一个结