第11章 特殊图

《第11章 特殊图》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、离散数学电子科技大学计算机科学与工程学院示范性软件学院15九月2021第11章特殊图偶图3平面图4欧拉图1集合的表示方法2哈密顿图211.0内容提要几个特殊图的概念：欧拉图、哈密顿图、偶图、平面图；欧拉图、哈密顿图、偶图、平面图的判定；偶图的匹配、图的着色；欧拉图、哈密顿图、偶图、平面图的应用10.1本章学习要求重点掌握一般掌握了解11各个特殊图相关基本概念2各个特殊图的性质3各个特殊图的判定方法31各个特殊图的应用2图的着色21哈密顿图、平面图的判断2证明方法11.2欧拉图11.2.1欧拉图的引入与定义ABCDb5b2b1b3b4b7b6BCADb6b2b5b7b4b1b3定义11.2.1设

2、G是无孤立结点的图，若存在一条通路(回路)，经过图中每边一次且仅一次，则称此通路(回路)为该图的一条欧拉通路(回路)(EulerianEntry/Circuit)。具有欧拉回路的图称为欧拉图(EulerianGraph)。规定：平凡图为欧拉图。以上定义既适合无向图，又适合有向图。欧拉通路和欧拉回路的特征欧拉通路是经过图中所有边的通路中长度最短的通路，即为通过图中所有边的简单通路；欧拉回路是经过图中所有边的回路中长度最短的回路，即为通过图中所有边的简单回路。如果仅用边来描述，欧拉通路和欧拉回路就是图中所有边的一种全排列。例11.2.1判断下面的6个图中，是否是欧拉图？是否存在欧拉通路？v3v1v

3、2v4(c)v3v1v2v4(a)v3v1v2v4(b)v3v1v2v4(f)v3v1v2v4(d)v3v1v2v4(e)欧拉图欧拉图不是欧拉图，但存在欧拉通路不存在欧拉通路不存在欧拉通路不是欧拉图，但存在欧拉通路11.2.2欧拉图的判定定理11.2.1无向图G=具有一条欧拉通路，当且仅当G是连通的，且仅有零个或两个奇度数结点。分析只要找到了，就是存在的。我们具体找一条欧拉通路。对于结点的度数，我们在通路中去计算。证明若G为平凡图，则定理显然成立。故我们下面讨论的均为非平凡图。必要性：设G具有一条欧拉通路L=，则L经过G中的每条边，由于G中无孤立结点，因而L经过G的所有结点，所以G是

4、连通的。对欧拉通路L的任意非端点的结点，在L中每出现一次，都关联两条边和，而当重复出现时，它又关联另外的两条边，由于在通路L中边不可能重复出现，因而每出现一次都将使获得2度。若在L中重复出现p次，则deg()=2p。若端点≠，设、在通路中作为非端点分别出现p1和p2次，则deg()=2p1+1，deg()=2p2+1因而G有两个度数为奇数的结点。若端点=，设在通路中作为非端点出现p3次，则deg()=1+2p3+1=2(p3+1)因而G无度数为奇数的结点。充分性：构造性证明。我们从两个奇度数结点之一开始(若无奇度数结点，可从任一结点开始)构造一条欧拉通路，以每条边最多经过一次的方式通过图中的边

5、。对于度数为偶数的结点，通过一条边进入这个结点，总可以通过一条未经过的边离开这个结点，因此，这样的构造过程一定以到达另一个奇度数结点而告终(若无奇度数结点，则以回到原出发点而告终)。如果图中所有的边已用这种方式经过了，显然这就是所求的欧拉通路。如果图中不是所有的边都经过了，我们去掉已经过的边，得到一个由剩余的边组成的子图，这个子图的所有结点的度数均为偶数。因为原来的图是连通的，因此，这个子图必与我们已经过的通路在一个或多个结点相接。从这些结点中的一个开始，我们再通过边构造通路，因为结点的度数全是偶数，因此，这条通路一定最终回到起点。我们将这条回路加到已构造好的通路中间组合成一条通路。如有必要，

6、这一过程重复下去，直到我们得到一条通过图中所有边的通路，即欧拉通路。由定理11.2.1的证明知：若连通的无向图有两个奇度数结点，则它们是G中每条欧拉通路的端点。结论推论11.2.1无向图G=具有一条欧拉回路，当且仅当G是连通的，并且所有结点的度数均为偶数。定理11.2.2有向图G具有一条欧拉通路，当且仅当G是连通的，且除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大1，另一个结点的出度比入度大1。推论11.2.2有向图G具有一条欧拉回路，当且仅当G是连通的，且所有结点的入度等于出度。欧拉通路与欧拉回路判别准则对任意给定的无向连通图，只需通过对图中

7、各结点度数的计算，就可知它是否存在欧拉通路及欧拉回路，从而知道它是否为欧拉图；对任意给定的有向连通图，只需通过对图中各结点出度与入度的计算，就可知它是否存在欧拉通路及欧拉回路，从而知道它是否为欧拉图。利用这项准则，很容易判断出哥尼斯堡七桥问题是无解的，因为它所对应的图中所有4个结点的度数均为奇数；也很容易得到例11.2.1的结论。定义11.2.2设G=，e∈E，如果p(G-e)＞p(G)