离散数学与课件 图论6 .ppt

第十七章 平面图 本章的主要内容 平面图的基本概念 欧拉公式 平面图的判断 平面图的对偶图 几点说明及一些简单结论 一般所谈平面图不一定是指平面嵌入，上图中4个图都是平面图，但讨论某些性质时，一定是指平面嵌入. 结论： (1) K5, K3,3都不是平面图（待证） (2) 设G??G，若G为平面图，则G?也是平面图（定理17.1） (3) 设G??G，若G?为非平面图，则G也是非平面图（定理17.2），由此可知，Kn(n?6)，K3,n(n?4) 都是非平面图。 (4) 平行边与环不影响平面性. 平面图(平面嵌入)的面与次数 定义： 1. G的面——G的平面嵌入的边将平面化分成的若干区域 2. 无限面或外部面——（可用R0表示）——面积无限的面 3. 有限面或内部面（可用R1, R2, …, Rk等表示）——面积 有限的面 4. 面 Ri 的边界——包围Ri的回路组 5. 面 Ri 的次数——Ri边界的长度，用deg(Ri)表示 若平面图G有k个面，可笼统地用R1, R2, …, Rk表示，不需要指出外部面. 定义中回路组是指：边界可能是初级回路(圈)，可能是简单回路，也可能是复杂回路。特别地，还可能是非连通的回路之并. 极大平面图 定义：若在简单平面图G中的任意两个不相邻的顶点之间 加一条新边所得图为非平面图，则称G为极大平面图. 注意：若简单平面图G中已无不相邻顶点，G显然是极大平 面图，如K1(平凡图), K2, K3, K4都是极大平面图。 定理17.8 设G为n阶m条边r个面的连通平面图，则n?m+r=2 （此公式称为欧拉公式） 证 对边数m做归纳法 m=0，G为平凡图，结论为真. 设m=k（k?1）结论为真，m=k+1时分情况讨论. (1) G中无圈，则G为树，删除一片树叶，用归纳假设. (2) 否则，在某一个圈上删除一条边，进行讨论. 平面图判定定理 17.4 平面图的对偶图 定义：设G是某平面图的某个平面嵌入，构造G的对偶图 G*如下： (1) 在G的面Ri中放置G*的顶点v*i. (2) 设e为G的任意一条边. 若e在G的面 Ri与 Rj 的公共边界上，做G*的边e*与e相 交，且e*关联G*的位于Ri与Rj中的顶点v*i与v*j，即 e*=(v*i,v*j)， e*不与其它任何边相交. 若e为G中的桥且在面Ri的边界上，则e*是以Ri中G*的顶 点v*i为端点的环，即e*=(v*i,v*i). 对偶图的性质 G 的对偶图G*有以下性质： (1) G*是平面图，而且是平面嵌入。 (2) G*是连通图 (3) 若边e为G中的环，则G*与e对应的边e*为桥，若e为桥，则G*中与e对应的边e*为环。 (4) 在多数情况下，G*为多重图（含平行边的图）。 (5) 同构的平面图（平面嵌入）的对偶图不一定是同构的。 如上面的例子。 平面图与对偶图之间的关系 定理17.17 设G*是连通平面图G的对偶图，n*, m*, r*和n, m, r分别为G*和G的顶点数、边数和面数，则 (1) n*= r (2) m*=m (3) r*=n (4) 设G*的顶点v*i位于G的面Ri中，则d(v*i)=deg(Ri) 证明： (1)、(2)平凡 (3) 应用欧拉公式 (4) 的证明中注意，桥只能在某个面的边界中，非桥边在两个面的边界上。 平面图与对偶图的关系 定理17.18 设G*是具有k（k?2）个连通分支的平面图G的对 偶图，则 (1) n*= r (2) m*=m (3) r*=n?k+1 (4) 设G*的顶点v*i位于G的面Ri中，则d(v*i)=deg(Ri) 其中n*, m*, r*, n, m, r同定理17.17. 证明(3) 时应同时应用欧拉公式及欧拉公式的推广。 自对偶图 定义：设G*是平面图G的对偶图，若G*?G，则称G为自 对偶图. 概念： n阶轮图（ Wn ）、奇阶轮图、偶阶轮图 轮图都是自对偶图。 画出W6和W7的对偶图，并说明它们都是自对偶图。 第十七章 小结 主要内容 平面图的基本概念 欧拉公式 平面图的判断 平面图的对偶图 基本要求 理解基本概念：平面图、平面嵌入、面、次数、极大平面图、极小非平面图、对偶图 牢记极大平面图的主要性质和判别方法 熟记欧拉公式及推广，并能用欧拉公式及推广形式证明有关定理与命题 会用库拉图斯基定理证明某些图不是平面图 记住平面图与它的对偶图阶数、边数、面数之间的关系 练习1 解 设G的阶数、边数、面数分别为n, m, r. (1) 否则，