复旦大学：《离散数学》课程教学讲义（图论）第九章 平面图与图的着色

第九章平面图与图的着色

第九章 平面图与图的着色

91平面图与欧拉公式 9.1平面图与欧拉公式(补充) 92顶点着色 93平面图的着色 94边的着色 95图着色的应用

 9.1 平面图与欧拉公式  9.1 平面图与欧拉公式（补充）  9.2 顶点着色  9.3 平面图的着色  9.4 边的着色  9.5 图着色的应用

平面图 在现实生活中,常常要画一些图形,希 望边与边之间尽量减少相交的情况,例 如印刷线路板上的布线,交通道的设计 等。 ■同构

平面图  在现实生活中，常常要画一些图形，希 望边与边之间尽量减少相交的情况，例 如印刷线路板上的布线，交通道的设计 等。  同构

9.1平面图与欧拉公式 、平面图 ■定义91(平面图) 若一个图能画在平面上使它的边互不 相交(除在顶点处),则称该图为平面图, 或称该图能嵌入平面的。 e6 e5 e3 e2 es e4

9.1 平面图与欧拉公式  一、平面图  定义9.1（平面图） 若一个图能画在平面上使它的边互不 相交（除在顶点处），则称该图为平面图， 或称该图能嵌入平面的

图91(a),(b) 图91(a)平面图G,(b)所示的G是G的平面嵌入

 图9.1(a),(b)  图9.1(a)平面图G, (b) 所示的 Ğ 是 G的平面嵌入

图92:并不是所有的图都是平面图。(K5和

 图9.2：并不是所有的图都是平面图。（ K 5 和 K3,3 ）

9.1平面图与欧拉公式 、欧拉公式 1定义92(面/外部面/内部面) 平面图G嵌入平面后将G分成若干 个连通闭区域,每一个连通闭区域称为G 的一个面 恰有一个无界的面,称为外部面 其余的面称为内部面

9.1 平面图与欧拉公式  二、欧拉公式  1 定义9.2（面/外部面/内部面） 平面图G嵌入平面后将Ğ分成若干 个连通闭区域，每一个连通闭区域称为G 的一个面。 恰有一个无界的面，称为外部面。 其余的面称为内部面

9.1平面图与欧拉公式 2欧拉公式 (1)定理9.1 若连通平面图G有n个顶点,e条边和f 个面,则 n-e+f2 称为欧拉公式。 证明方法:归纳法

9.1 平面图与欧拉公式  2 欧拉公式  （1）定理9.1 若连通平面图G有n个顶点，e条边和f 个面，则 n-e+f=2 称为欧拉公式。  证明方法：归纳法

明 1)归纳基砷:一条边,欧拉公式成立 (2)归纳步骤:假设m-1条边,欧拉公式成立; 考察m条边的连通平面图: 1)若有度数为1的顶点,则删去该顶点及其关联边, 便得到连通平面图G’,G满足欧拉公式,再将删去 的点和边加回G得到G也满足欧拉公式; 2)若没有度数为1的顶点,则删去有界面边界上的 任一边,便得到连通平面图G’,G满足欧拉公式, 再将删去的边加回G'得到G也满足欧拉公式

 证明：  （1）归纳基础：一条边，欧拉公式成立；  （2）归纳步骤：假设m-1条边，欧拉公式成立； 考察m条边的连通平面图： 1）若有度数为1的顶点，则删去该顶点及其关联边， 便得到连通平面图G’，G’满足欧拉公式，再将删去 的点和边加回G’得到G也满足欧拉公式； 2）若没有度数为1的顶点，则删去有界面边界上的 任一边，便得到连通平面图G’， G’满足欧拉公式， 再将删去的边加回G’得到G也满足欧拉公式

9.1平面图与欧拉公式 (2)推论91 若G是n≥3的平面简单图,则e<3n-6。 证明:只证明连通的平面简单图的情况,G是n≥3 的平面简单图,每个面由3条或更多条边围成, 因此边的总数大于等于3,因为每条边至多被 计算两次,所以G中至少有2条边,即e≥32。 根据欧拉公式,有n-e+2e/3≥2 所以3n-6≥e

9.1 平面图与欧拉公式  (2)推论9.1 若G是n3的平面简单图，则e3n-6。 证明：只证明连通的平面简单图的情况，G是n3 的平面简单图，每个面由3条或更多条边围成， 因此边的总数大于等于3f，因为每条边至多被 计算两次，所以G中至少有3f/2条边，即e3f/2。 根据欧拉公式，有n-e+2e/32。 所以3n-6e