哈尔滨理工大学斛监課裎 离影数 第17章平面图及图的着色 计算机系
第17章 平面图及图的着色 离 散 数 学 哈尔滨理工大学本科生课程 计算机系
本章说可 口本章的主要内容 平面图的基本概念 欢拉公式 平面图的判断 平面图的对偶图 顶点着色及点色数 地图的着色与平面图的点着色 边着色及边色数
本章说明 ❑本章的主要内容 –平面图的基本概念 –欧拉公式 –平面图的判断 –平面图的对偶图 –顶点着色及点色数 –地图的着色与平面图的点着色 –边着色及边色数
本章所涉及到的图均指无向图
本章所涉及到的图均指无向图
口17.1平面图的基本概念 口17.2欧拉公式 口17.3平面图的判断 口17.4平面图的对偶图 口17.5图中顶点的着色 口17.6地图的着色与平面图的点着色 口17.7边着色 口口口 本章小结 习题 作业
❑ 17.1 平面图的基本概念 ❑ 17.2 欧拉公式 ❑ 17.3 平面图的判断 ❑ 17.4 平面图的对偶图 ❑ 17.5 图中顶点的着色 ❑ 17.6 地图的着色与平面图的点着色 ❑ 17.7 边着色 ❑ 本章小结 ❑ 习 题 ❑ 作 业
°17.1平面图的基本概念 关于平面图的一些基本概念 1、平面图的定义 口G可嵌入曲面S如果图G能以这样的方式画在曲面S上 ,即除顶点处外无边相交。 口G是可平面图或平面图若G可嵌入平面。 口G的平面嵌入—画出的无边相交的平面图 口非平面图—无平面嵌入的图
17.1 平面图的基本概念 一、关于平面图的一些基本概念 1、 平面图的定义 定义17.1 ❑ G可嵌入曲面S——如果图G能以这样的方式画在曲面S上 ，即除顶点处外无边相交。 ❑ G是可平面图或平面图——若G可嵌入平面。 ❑ G的平面嵌入——画出的无边相交的平面图。 ❑ 非平面图——无平面嵌入的图
(1) (2) (2)是(1)的平面嵌入,(4)是(3)的平面嵌入
（2）是（1）的平面嵌入，（4）是（3）的平面嵌入
2、几点说明及一些简单结论 般所谈平面图不一定是指平面嵌入,但讨论某些性质时 定是指平面嵌入 口K和K3都不是平面图。 口z理叮设G'cG,若G为平面图,则G也是平面图 口理叮设G'cG,若G为非平面图,则G也是非平面图。 口维论K5和K3(≥3)都是非平面图。 口宠理若G为平面图,则在G中加平行边或环所得图还是 平面图 即平行边和环不影响图的平面性
2、 几点说明及一些简单结论 ❑ 一般所谈平面图不一定是指平面嵌入，但讨论某些性质时， 一定是指平面嵌入。 ❑ K5和K3,3都不是平面图。 ❑ 定理17.1 设GG，若G为平面图，则G也是平面图。 ❑ 定理17.2 设GG，若G为非平面图，则G也是非平面图。 ❑ 推论 Kn (n5)和K3,n (n3)都是非平面图。 ❑ 定理17.3 若G为平面图，则在G中加平行边或环所得图还是 平面图。 即平行边和环不影响图的平面性
二、平面图的面与次数(针对平面图的平面嵌入) 1、定义 定72设G是平面图, 口G的面—由G的边将G所在的平面划分成的每一个区域。 口无限面(外部面)—面积无限的面,记作R0 口有限面(内部面)—面积有限的面,记作R1,R 口面R的边界包围面R的所有边组成的回路组。 口面R的次数—R边界的长度,记作leg(R)
二、平面图的面与次数（针对平面图的平面嵌入） 1、 定义 定义17.2 设G是平面图， ❑ G的面——由G的边将G所在的平面划分成的每一个区域。 ❑ 无限面（外部面）——面积无限的面，记作R0。 ❑ 有限面（内部面）——面积有限的面，记作R1 , R2 , …, Rk。 ❑ 面Ri的边界——包围面Ri的所有边组成的回路组。 ❑ 面Ri的次数——Ri边界的长度，记作deg(Ri )
几点说明 口若平面图G有k个面,可笼统地用R,R2…,R表示,不需 要指出外部面。 口回路组是指:边界可能是初级回路(圈),可能是简单回 路,也可能是复杂回路。特别地,还可能是非连通的回路 之并。 R1a b RO g R2 平面图有4个面,deg(R)=1,deg(R2)=3,deg(R3)=2,deg(R)=8
2、几点说明 ❑ 若平面图G有k个面，可笼统地用R1 , R2 , …, Rk表示，不需 要指出外部面。 ❑ 回路组是指：边界可能是初级回路（圈），可能是简单回 路，也可能是复杂回路。特别地，还可能是非连通的回路 之并。 平面图有4个面，deg(R1 )=1, deg(R2 )=3, deg(R3 )=2, deg(R0 )=8。 R1 R2 R3 R0
定平面图G中所有面的次数之和等于边数m的两倍,即 ∑deg(R)=2m其中r为G的面数 本定理中所说平面图是指平面嵌入。 ve∈E(G), ①当e为面R和R动的公共边界上的边时,在计算R和R的次 数时,e各提供1 ②当e只在某一个面的边界上出现时,则在计算该面的次数时 ,e提供2 于是每条边在计算总次数时,都提供2,因而deg(R)=2mo
定理17.4 平面图G中所有面的次数之和等于边数m的两倍，即 本定理中所说平面图是指平面嵌入。 e∈E(G)， 当e为面Ri和Rj (i≠j)的公共边界上的边时，在计算Ri和Rj的次 数时，e各提供1。 当e只在某一个面的边界上出现时，则在计算该面的次数时 ，e提供2。 于是每条边在计算总次数时，都提供2，因而deg(Ri )=2m。 1 deg( ) 2 r i i R m r G = = 其中 为 的面数 证 明