福州大学：《离散数学》课程教学资源（课件讲稿）第十七章 平面图及图的着色

第十七章平面图 ■平面图的基本概念 ■欧拉公式 ■平面图的判断 ■平面图的对偶图 ■图中顶点的着色 ■地图的着色与平面图的着色 边着色

第十七章 平面图  平面图的基本概念  欧拉公式  平面图的判断  平面图的对偶图  图中顶点的着色  地图的着色与平面图的着色  边着色

17.1平面图的基本概念 ■平面图与平面嵌入 ■平面图的面、有限面、无限面 ■面的次数 ·极大平面图 ■极小非平面图

17.1 平面图的基本概念  平面图与平面嵌入  平面图的面、有限面、无限面  面的次数  极大平面图  极小非平面图

平面图和平面嵌入 定义如果能将图G除顶点外边不相交地画在平面上， 则称G是平面图.这个画出的无边相交的图称作G 的平面嵌入.没有平面嵌入的图称作非平面图. 例如下图中(1)(4)是平面图，(2)是(1)的平面嵌入， (4)是3)的平面嵌入.（⑤）是非平面图. (1) (2) (3) (4) (5)

平面图和平面嵌入 定义 如果能将图G除顶点外边不相交地画在平面上, 则称G是平面图. 这个画出的无边相交的图称作G 的平面嵌入. 没有平面嵌入的图称作非平面图. 例如 下图中(1)~(4)是平面图, (2)是(1)的平面嵌入， (4)是(3)的平面嵌入. (5)是非平面图

平面图和平面嵌入（续) ●1 按定义，平面图不一定是平面嵌入.但今后讨论平面图时， 可根据上下文加以区分. 。K和K.3是非平面图 。Ke和K2.3是平面图 K 设GcG,若G为平面图，则G也是 平面图；若G为非平面图，则G也 是非平面图. 。Kn(25),K3n(n23)都是非平面图. 飞33 平行边与环不影响图的平面性

平面图和平面嵌入(续) • 按定义, 平面图不一定是平面嵌入. 但今后讨论平面图时, 可根据上下文加以区分. • K5和K3,3是非平面图 • K5 -e和K2,3是平面图 • 设GG, 若G为平面图, 则G也是 平面图; 若G为非平面图, 则G也 是非平面图. • Kn (n5), K3,n (n3)都是非平面图. • 平行边与环不影响图的平面性. K5 K3,3

平面图的面与次数 设G是一个平面嵌入 G的面：由G的边将平面划分成的每一个区域 无限面（外部面）：面积无限的面，用R表示 有限面（内部面）：面积有限的面，用R1,R2,R表示 面R的边界：包围R的所有边构成的回路组 面R的次数：边界的长度，用deg(R)表示 说明：构成一个面的边界的回路组可能是初级回路，简单回 路，也可能是复杂回路，甚至还可能是非连通的回路之并， 定理平面图各面的次数之和等于边数的2倍

平面图的面与次数 设G是一个平面嵌入 G的面: 由G的边将平面划分成的每一个区域 无限面(外部面): 面积无限的面, 用R0表示 有限面(内部面): 面积有限的面, 用R1 , R2 ,., Rk表示 面Ri的边界: 包围Ri的所有边构成的回路组 面Ri的次数: Ri边界的长度，用deg(Ri )表示 说明: 构成一个面的边界的回路组可能是初级回路, 简单回 路, 也可能是复杂回路, 甚至还可能是非连通的回路之并. 定理 平面图各面的次数之和等于边数的2倍

平面图的面与次数（续） 例1右图有4个面，deg(R)=1, deg(R,)=3,deg(R3)=2, Ro R deg(Ro)=8.请写各面的边界. 例2左边2个图是同一个平面 图的平面嵌入.R在(1)中是 R R: 外部面，在(2)中是内部面；R2 R2 R 在(1)中是内部面，在(2)中是 R, 外部面.其实，在平面嵌入中 (1) (2) 可把任何面作为外部面

平面图的面与次数(续) 例1 右图有4个面, deg(R1 )=1, deg(R2 )=3, deg(R3 )=2, deg(R0 )=8. 请写各面的边界. 例2 左边2个图是同一个平面 图的平面嵌入. R1在(1)中是 外部面, 在(2)中是内部面; R2 在(1)中是内部面, 在(2)中是 外部面. 其实, 在平面嵌入中 可把任何面作为外部面

极大平面图 定义若G是简单平面图，并且在任意两个不相邻的顶点之 间加一条新边所得图为非平面图，则称G为极大平面图. 性质 。若简单平面图中已无不相邻顶点，则是极大平面图.如 K1,K2,K3,K4,K-e都是极大平面图. ·极大平面图必连通。 ·阶数大于等于3的极大平面图中不可能有割点和桥 ● 设G为n(n23)阶简单连通平面图，G为极大平面图当且 仅当G每个面的次数均为3

极大平面图 定义 若G是简单平面图, 并且在任意两个不相邻的顶点之 间加一条新边所得图为非平面图, 则称G为极大平面图. 性质 • 若简单平面图中已无不相邻顶点，则是极大平面图. 如 K1 , K2 , K3 , K4 , K5 -e都是极大平面图. • 极大平面图必连通. • 阶数大于等于3的极大平面图中不可能有割点和桥. • 设G为n(n3)阶简单连通平面图， G为极大平面图当且 仅当G每个面的次数均为3

实例 3个图都是平面图，但只有右边的图为极大平面图

实例 3个图都是平面图, 但只有右边的图为极大平面图

极小非平面图 定义若G是非平面图，并且任意删除一条边所得图 都是平面图，则称G为极小非平面图. 说明： K,K3都是极小非平面图 极小非平面图必为简单图 下面4个图都是极小非平面图

极小非平面图 定义 若G是非平面图, 并且任意删除一条边所得图 都是平面图, 则称G为极小非平面图. 说明: K5 , K3,3都是极小非平面图 极小非平面图必为简单图 下面4个图都是极小非平面图

17.2欧拉公式 ■欧拉公式 ■与欧拉公式有关的定理

17.2 欧拉公式  欧拉公式  与欧拉公式有关的定理