第11章 特殊图VIP免费

电子科技大学离散数学课程组——国家精品课程离散数学电子科技大学计算机科学与工程学院示范性软件学院2025年2月10日电子科技大学离散数学课程组——国家精品课程110-225/2/10第11章特殊图偶图3平面图4欧拉图1集合的表示方法2哈密顿图2电子科技大学离散数学课程组——国家精品课程110-325/2/1011.0内容提要1.几个特殊图的概念：欧拉图、哈密顿图、偶图、平面图；2.欧拉图、哈密顿图、偶图、平面图的判定；3.偶图的匹配、图的着色；4.欧拉图、哈密顿图、偶图、平面图的应用电子科技大学离散数学课程组——国家精品课程110-425/2/1010.1本章学习要求重点掌握一般掌握了解11各个特殊图相关基本概念2各个特殊图的性质3各个特殊图的判定方法31各个特殊图的应用2图的着色21哈密顿图、平面图的判断2证明方法电子科技大学离散数学课程组——国家精品课程110-525/2/1011.2欧拉图11.2.1欧拉图的引入与定义ABCDb5b2b1b3b4b7b6BCADb6b2b5b7b4b1b3电子科技大学离散数学课程组——国家精品课程110-625/2/10定义11.2.1设G是无孤立结点的图，若存在一条通路(回路)，经过图中每边一次且仅一次，则称此通路(回路)为该图的一条欧拉通路(回路)(EulerianEntry/Circuit)。具有欧拉回路的图称为欧拉图(EulerianGraph)。规定：平凡图为欧拉图。以上定义既适合无向图，又适合有向图。电子科技大学离散数学课程组——国家精品课程110-725/2/10欧拉通路和欧拉回路的特征欧拉通路是经过图中所有边的通路中长度最短的通路，即为通过图中所有边的简单通路；欧拉回路是经过图中所有边的回路中长度最短的回路，即为通过图中所有边的简单回路。如果仅用边来描述，欧拉通路和欧拉回路就是图中所有边的一种全排列。电子科技大学离散数学课程组——国家精品课程110-825/2/10例11.2.1判断下面的6个图中，是否是欧拉图？是否存在欧拉通路？v3v1v2v4(c)v3v1v2v4(a)v3v1v2v4(b)v3v1v2v4(f)v3v1v2v4(d)v3v1v2v4(e)欧拉图欧拉图不是欧拉图，但存在欧拉通路不存在欧拉通路不存在欧拉通路不是欧拉图，但存在欧拉通路电子科技大学离散数学课程组——国家精品课程110-925/2/1011.2.2欧拉图的判定定理11.2.1无向图G=具有一条欧拉通路，当且仅当G是连通的，且仅有零个或两个奇度数结点。分析只要找到了，就是存在的。我们具体找一条欧拉通路。对于结点的度数，我们在通路中去计算。证明若G为平凡图，则定理显然成立。故我们下面讨论的均为非平凡图。电子科技大学离散数学课程组——国家精品课程110-1025/2/10必要性：设G具有一条欧拉通路L=，则L经过G中的每条边，由于G中无孤立结点，因而L经过G的所有结点，所以G是连通的。对欧拉通路L的任意非端点的结点，在L中每出现一次，都关联两条边和，而当重复出现时，它又关联另外的两条边，由于在通路L中边不可能重复出现，因而每出现一次都将使获得2度。若在L中重复出现p次，则deg()=2p。0112m-1mmijijijiveve...vevkivkivkje1kjekivkiv电子科技大学离散数学课程组——国家精品课程110-1125/2/10若端点≠，设、在通路中作为非端点分别出现p1和p2次，则deg()=2p1+1，deg()=2p2+1因而G有两个度数为奇数的结点。若端点=，设在通路中作为非端点出现p3次，则deg()=1+2p3+1=2(p3+1)因而G无度数为奇数的结点。0ivmiv0ivmiv0ivmiv0ivmiv0iv电子科技大学离散数学课程组——国家精品课程110-1225/2/10充分性：构造性证明。我们从两个奇度数结点之一开始(若无奇度数结点，可从任一结点开始)构造一条欧拉通路，以每条边最多经过一次的方式通过图中的边。对于度数为偶数的结点，通过一条边进入这个结点，总可以通过一条未经过的边离开这个结点，因此，这样的构造过程一定以到达另一个奇度数结点而告终(若无奇度数结点，则以回到原出发点而告终)。如果图中所有的边已用这种方式经过了，显然这就是所求的欧拉通路。如果图中不是所有的边都经过了，我们去掉已经过的边，得到一个由剩余的边组成的子图，这个子图的所有结点的度数均为偶数。电子科技大学离散数学课程组——国家精品课程110-1325/2/10因为原来的图是连通的，因此，这个子图必与我们已经过的通路在一个或多个结点相接。从这些结点中的一...