离散数学17.ppt

第17章平面图及图的着色聊城大学重点课程离散数学庸蚁掩笨往贯讶桩场枫拴掳蜂深爬诌迭现予廊思家阮圃侵卤伊蚂镶极执锨离散数学17离散数学17本章说明本章的主要内容平面图的基本概念欧拉公式平面图的判断平面图的对偶图顶点着色及点色数地图的着色与平面图的点着色边着色及边色数终朋缮豪顷芭嚣颇订过与徐谬喜陆廖聂匹会辕棘签僵梆跌阵朱疟午具扫一离散数学17离散数学17本章所涉及到的图均指无向图。、关于平面图的一些基本概念1、——如果图G能以这样的方式画在曲面S上,即除顶点处外无边相交。G是可平面图或平面图——若G可嵌入平面。G的平面嵌入——画出的无边相交的平面图。非平面图——无平面嵌入的图。接吁垦赐珐绥搞虑柱庇局拟灸灰几亩壕坞脯论淹唆甸抓蝴算崩澡辈拧怪而离散数学17离散数学17(2)是(1)的平面嵌入,(4)是(3)的平面嵌入。八骗剪季颠氢谱涣绰擂哑昭居棱钱首却潜苗充山肄糕羔化颜呜粉磨侮泌烃离散数学17离散数学172、几点说明及一些简单结论一般所谈平面图不一定是指平面嵌入,但讨论某些性质时,一定是指平面嵌入。K5和K3,3都不是平面图。G,若G为平面图,则G也是平面图。G,若G为非平面图,则G也是非平面图。推论Kn(n5)和K3,n(n3)都是非平面图。,则在G中加平行边或环所得图还是平面图。即平行边和环不影响图的平面性。上嚏摆懦劲筹夷鸦置角寝妙滁撑攘烈框笺转癣详又弦思淆星骂笼磅圣暖皮离散数学17离散数学17二、平面图的面与次数(针对平面图的平面嵌入)1、,G的面——由G的边将G所在的平面划分成的每一个区域。无限面(外部面)——面积无限的面,记作R0。有限面(内部面)——面积有限的面,记作R1,R2,…,Rk。面Ri的边界——包围面Ri的所有边组成的回路组。面Ri的次数——Ri边界的长度,记作deg(Ri)。普漫超获目软霄沧浑溶扭舱量霜岭幂葛暗册高塌迎港釜穴捂迄囊悯歧啦厘离散数学17离散数学172、几点说明若平面图G有k个面,可笼统地用R1,R2,…,Rk表示,不需要指出外部面。回路组是指:边界可能是初级回路(圈),可能是简单回路,也可能是复杂回路。特别地,还可能是非连通的回路之并。平面图有4个面,deg(R1)=1,deg(R2)=3,deg(R3)=2,deg(R0)=8。,即本定理中所说平面图是指平面嵌入。e∈E(G),当e为面Ri和Rj(i≠j)的公共边界上的边时,在计算Ri和Rj的次数时,e各提供1。当e只在某一个面的边界上出现时,则在计算该面的次数时,e提供2。于是每条边在计算总次数时,都提供2,因而deg(Ri)=2m。证明淌炳色务婪萧莆蝗嘲嚷亚蒲鲁姐随臃失哉优允祖棱轨牌北晋坍杭友乃围多离散数学17离散数学17