1、电子科技大学离散数学课程组 国家精品课程 双语示范课程离 散 数 学*电子科技大学计算机科学与工程学院电子科技大学离散数学课程组 国家精品课程 双语示范课程110-2*第 11章 特殊图 偶图3平面图4欧拉图1集合的表示方法2 哈密顿图电子科技大学离散数学课程组 国家精品课程 双语示范课程110-3*11.0 内容提要 1. 几个特殊图的概念：欧拉图、哈密顿图、偶图、平面图；2. 欧拉图、哈密顿图、偶图、平面图的判定；3. 偶图的匹配、图的着色；4. 欧拉图、哈密顿图、偶图、平面图的应用电子科技大学离散数学课程组 国家精品课程 双语示范课程110-4*10.1 本章学习要求重点掌握 一般掌握
2、了解11 各个特殊图相关基本概念2 各个特殊图的性质3 各个特殊图的判定方法 31 各个特殊图的应用2 图的着色21 哈密顿图、平面图的判断2 证明方法 电子科技大学离散数学课程组 国家精品课程 双语示范课程110-5*11.2 欧拉图 11.2.1 欧拉图的引入与定义ABC Db5b2b1b3 b4b7b6BCADb6b2 b5b7b4b1b3电子科技大学离散数学课程组 国家精品课程 双语示范课程110-6*定义 11.2.1设 G是 无孤立结点的图 ，若存在一条通路 (回路 )，经过图中每边一次且仅一次 ，则称此通路 (回路 )为该图的一条 欧拉通路 (回路 )(Eulerian Entr
3、y/Circuit)。具有欧拉回路的图称为 欧拉图(Eulerian Graph)。规定： 平凡图为欧拉图。以上定义既适合无向图，又适合有向图。 电子科技大学离散数学课程组 国家精品课程 双语示范课程110-7*欧拉通路和欧拉回路的特征欧拉通路 是经过 图中所有边 的通路中 长度最短的通路 ，即为 通过图中所有边的简单通路 ；欧拉回路 是经过 图中所有边 的回路中 长度最短的回路 ，即为 通过图中所有边的简单回路 。如果仅用边来描述， 欧拉通路和欧拉回路就是图中所有边的一种全排列 。电子科技大学离散数学课程组 国家精品课程 双语示范课程110-8*例 11.2.1判断下面的 6个图中，是否是欧
4、拉图？是否存在欧拉通路？ v3v1v2v4(c)v3v1v2v4(a)v3v1v2v4(b)v3v1v2v4(f)v3v1v2v4(d)v3v1v2v4(e)欧拉图 欧拉图 不是欧拉图，但存在欧拉通路 不存在欧拉通路 不存在欧拉通路 不是欧拉图，但存在欧拉通路 电子科技大学离散数学课程组 国家精品课程 双语示范课程110-9*11.2.2 欧拉图的判定 定理 11.2.1 无向图 G = 具有一条欧拉通路，当且仅当 G是连通的，且仅有零个或两个奇度数结点。分析 只要找到了，就是存在的。我们具体找一条欧拉通路。对于结点的度数，我们在通路中去计算。证明 若 G为平凡图，则定理显然成立。故我们下面讨论的均为非平凡图。电子科技大学离散数学课程组 国家精品课程 双语示范课程110-10*必要性：设 G具有一条欧拉通路 L = ，则 L经过 G中的每条边，由于 G中无孤立结点，因而 L经过 G的所有结点，所以 G是连通的。对欧拉通路 L的任意非端点的结点 ，在 L中每出现 一次，都关联两条边 和 ，而当 重复出现时，它又关联另外的两条边，由于在通路 L中边不可能重复出现，因而每出现一次都将使获得 2度。若在 L中重复出现 p次，则 deg( )= 2p。
