离散数学课件17平面图.pptx

第17章 平面图离 散 数 学中国地质大学本科生课程第一页，共四十七页。 本章说明本章的主要内容平面图的基本概念欧拉公式平面图的判断平面图的对偶图第二页，共四十七页。 本章所涉及到的图均指无向图。第三页，共四十七页。 17.1 平面图的基本概念17.2 欧拉公式17.3 平面图的判断17.4 平面图的对偶图 本章小结 习 题 作 业第四页，共四十七页。 17.1 平面图的基本概念一、关于平面图的一些基本概念1、 平面图的定义定义17.1 G可嵌入曲面S——如果图G能以这样的方式画在曲面S上，即除顶点处外无边相交。 G是可平面图或平面图——若G可嵌入平面。G的平面嵌入——画出的无边相交的平面图。非平面图——无平面嵌入的图。第五页，共四十七页。 （2）是（1）的平面嵌入，（4）是（3）的平面嵌入。第六页，共四十七页。 2、 几点说明及一些简单结论一般所谈平面图不一定是指平面嵌入，但讨论某些性质时，一定是指平面嵌入。K5和K3,3都不是平面图。定理17.1 设G??G，若G为平面图，则G?也是平面图。 设G??G，若G?为非平面图，则G也是非平面图。由定理可知， Kn(n?5)和K3,n(n?3)都是非平面图。定理17.2 若G为平面图，则在G中加平行边或环所得图还是平面图。即平行边和环不影响图的平面性。 第七页，共四十七页。 二、平面图的面与次数（针对平面图的平面嵌入）1、 定义定义17.2 设G是平面图，G的面——由G的边将G所在的平面划分成的每一个区域。无限面（外部面）——面积无限的面，记作R0。有限面（内部面）——面积有限的面 ，记作R1, R2, …, Rk。面Ri的边界——包围面Ri的所有边组成的回路组。面Ri的次数——Ri边界的长度，记作deg(Ri)。第八页，共四十七页。 2、几点说明若平面图G有k个面，可笼统地用R1, R2, …, Rk表示，不需要指出外部面。回路组是指：边界可能是初级回路（圈），可能是简单回路，也可能是复杂回路。特别地，还可能是非连通的回路之并。平面图有4个面，deg(R1)=1, deg(R2)=3, deg(R3)=2, deg(R0)=8。 R1R2R3R0第九页，共四十七页。 定理17.3 平面图G中所有面的次数之和等于边数m的两倍，即 本定理中所说平面图是指平面嵌入。 ?e∈E(G)，?当e为面Ri和Rj(i≠j)的公共边界上的边时，在计算Ri和Rj的次数时，e各提供1。?当e只在某一个面的边界上出现时，则在计算该面的次数时，e提供2。于是每条边在计算总次数时，都提供2，因而deg(Ri)=2m。证明第十页，共四十七页。 三、极大平面图1、 定义定义17.3 若在简单平面图G中的任意两个不相邻的顶点之间加一条新边所得图为非平面图，则称G为极大平面图。注意：若简单平面图G中已无不相邻顶点，G显然是极大平面图，如K1（平凡图）, K2, K3, K4都是极大平面图。2、极大平面图的主要性质定理17.4 极大平面图是连通的，并且n(n?3)阶极大平面图中不可能有割点和桥。第十一页，共四十七页。 定理17.5 设G为n(n?3) )阶简单连通的平面图，G为极大平面图当且仅当G的每个面的次数均为3。本节只证明必要性，即设G为n(n?3) )阶简单连通的平面图，G为极大平面图，则G的每个面的次数均为3。由于n?3, 又G必为简单平面图，可知，G每个面的次数均?3。因为G为平面图，又为极大平面图。可证G不可能存在次数>3的面。证明思路第十二页，共四十七页。 假设存在面Ri的次数deg(Ri)=s≥4，如图所示。在G中，若v1与v3不相邻，在Ri内加边(v1,v3)不破坏平面性，这与G是极大平面图矛盾，因而v1与v3必相邻，由于Ri的存在，边(v1,v3)必在Ri外。 类似地，v2与v4也必相邻，且边(v2,v4)也必在Ri外部，于是必产生(v1,v3)与(v2,v4)相交于Ri的外部，这又矛盾于G是平面图，所以必有s＝3，即G中不存在次数大于或等于4的面，所以G的每个面为3条边所围，也就是各面次数均为3。sS-1第十三页，共四十七页。 只有右边的图为极大平面图。 因为只有该图每个面的次数都为3。 第十四页，共四十七页。 四、极小非平面图定义17.4 若在非平面图G中任意删除一条边，所得图G?为平面图，则称G为极小非平面图。由定义不难看出：K5, K3,3都是极小非平面图。极小非平面图必为简单图。例如：以下各图均为极小非平面图。小节结束第十五页，共四十七页。 17.2 欧拉公式 一、欧拉公式相关定理1、 欧拉公式定理17.6 对于任意的连通的平面图G，有 n-m+r=2其中，n、m、r分别