离散数学 第6章 图论(2).ppt

《离散数学 第6章 图论(2).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、离散数学西安交通大学电子与信息工程学院计算机系1离散数学§6.Euler图Euler图的定义Euler图的理论2离散数学§6Euler图Euler图产生的背景就是前面介绍的Konigsberg七桥问题，有了前面几节的知识后，我们可以讨论Euler图的解决方法了。定义1.Euler路Euler圈Euler图设G＝(V,E)是连通的、无孤立点的图。(1)Euler路是一条简单路P，路P穿过图G中每条边一次且仅一次；(2)Euler圈是一条简单圈C，圈C穿过图G中每条边一次且仅一次；(3)含有Euler圈的图G称为Euler图(简称为E-图)。3离散数学注：

2、这类通过各边恰好一次的问题就是通常所说的一笔画问题（即笔不离纸，线不重复）。定理1.(Euler定理)设G＝(V,E)是无孤立点的无向图。那么，G是Euler图G是连通的且G中无奇结点。注：G中无奇结点即是G中每个结点都是偶结点。[证].先证必要性)：(采用蹦圈法)设C是G的一条Euler圈。则(1)图G是连通的：首先，由于图G中无孤立点，所以图G中的每个结点都有一些边与之关联，而Euler圈C包含了图G中的每一条边，于是圈C在通过各边的同时必通过图G中每个结点。因而图G中每个结点都在Euler圈C上。4离散数学因此，图G中任何两结点，沿着Euler圈

3、C可相互到达，故图G是连通的。(2)图G中无奇结点：其次，当圈C穿过某结点时，必从一边进，从另一边出，因此给该结点度数的贡献是2；尽管圈C可能会多次穿过某些结点，但由上述原因和Euler圈C仅穿过每条边一次(C是Euler圈)及每个结点都在圈C上可知：圈C穿过某结点k次，就给该结点的度数贡献2k；因此，图G中每个结点的度数必全为偶数，即图G中无奇结点。再证充分性)：(C.L.Liu算法)No1.从任一结点出发，走成一个简单圈C；由于图G中每个结点都是偶结点(无奇结点)，且图G连通，故图G中至少存在一个简单圈C。5离散数学No2.若此简单圈C已是Euler

4、圈，则此图G就是Euler图，算法结束(出口)。No3.(插圈)否则，图G中必还有若干条边不属于圈C。由图G的连通性可知：必有圈C外的边ej与圈C上的结点vi相关联(vi称为接触点)。由于在图G中除去圈C(只删边，不删结点)后所得的子图G中，每个结点仍都是偶结点(因为在圈C上的结点，都是一边进，另一CC图1viGGej6离散数学边出。因此圈C每穿过某结点一次，该结点的度数就被消耗掉2。故这些结点在删除圈C的边时，它们的度数都减少一个偶数)。由于图G中每个结点都仍是偶结点，于是从此结点vi出发，经过边ej及子图G中的其它边，必可走出一个简单圈C，

5、回到出发点vi。故圈C与圈C必由结点vi相连(如图1所示)。将圈C插入圈C中，形成一条新的更长的简单圈C:=CC，gotoNo2。由于图G中的边数是有限的，故算法不可能无穷的进行下去，所以算法必定在有限步结束。最后一定能得到一个包括图G中所有边在其上的简单圈C，此圈C即是Euler圈。所以图G即为Euler图。注：C.L.Liu美籍华人。著有《离散数学基础》(刘振宏译)；条件：全是偶结点保证可走出简单圈；条件：连通性保证边(从而结点)可走完。7离散数学例1.图G如图2所示。问图G是否为一Euler图？若是，试求出其Euler圈。[解].由于图

6、G中的六个结点全都是偶结点，并且图G显然是连通的，故根据上述Euler定理可知，图G为Euler图。按照C.L.Liu算法，可求得图G中的Euler圈。具体步骤如下：在图中任意找一简单圈C＝(1,2,3,1)。发现还有7条边不在此圈164325图28离散数学中，边(3,4)不在圈中且与圈中的结点3相关联。由结点3出发经过边(3,4)可得一简单圈C＝(3,4,5,3)，将C插入C得到一个新的更长的简单圈C＝(1,2,3,4,5,3,1)。此时仍有4条边不在圈C中，边(2,5)不在圈中且与圈中的结点2关联。由结点2出发经过边(2,5)又可得到一简单圈C

7、＝(2,5,6,4,2)，将C插入C又得到一条新的更长的简单圈C＝(1,2,5,6,4,2,3,4,5,3,1)。由于图G中所有的边都已在圈C中，故知此圈C为图G的一个Euler圈。例2．哥尼斯堡七桥问题无解。[解].在七桥图中(图3)，由于每个结点均为奇结点，故由Euler定理的充要条件知，该图中不存在经过每条边一次且仅一次的Euler圈。即七桥图不是Euler图。该问题无解。9离散数学ADCB图3v3vk-1vkev2v1图410离散数学推论.(Euler定理二)设G＝(V,E)是无孤立点的无向图。那么，G中有Euler路G是连通的且G中恰有两

8、个奇结点。[证].(采用增边删边法及抻路法)G中有Euler路P=