文档介绍：平面图
平面图与平面嵌入
平面图的面及其次数
极大平面图
极小非平面图
欧拉公式
库拉图斯基定理
平面图的对偶图
1
课件
平面图与非平面图
如果能将图G除顶点外边不相交地画在平面上,
则称G是平面图. 这个画出的无边相交的图称作G的平面
嵌入. 没有平面嵌入的图称作非平面图.
例如下图中(1)~(4)是平面图, (2)是(1)的平面嵌入,
(4)是(3)的平面嵌入. (5)是非平面图.
2
课件
平面图的面与次数
设G是一个平面嵌入
G的面: 由G的边将平面划分成的每一个区域
无限面(外部面): 面积无限的面, 用R0表示
有限面(内部面): 面积有限的面, 用R1, R2,…, Rk表示
面Ri的边界: 包围Ri的所有边构成的回路组
面Ri的次数: Ri边界的长度,用deg(Ri)表示
说明: 构成一个面的边界的回路组可能是初级回路, 简单回
路, 也可能是复杂回路, 甚至还可能是非连通的回路之并.
3
课件
实例
例1 右图有个面
4
deg(R1)=
deg(R2)=
deg(R3)=
deg(R0)=
1
3
2
8
R1的边界:
R2的边界:
R3的边界:
R0的边界:
a
bce
fg
abcdde, fg
4
课件
实例
例2 右边2个图是同一
平面图的平面嵌入.
R1在(1)中是外部面,
在(2)中是内部面;
R2在(1)中是内部面, 在(2)中是外部面.
(1)
R1
R2
R3
(2)
R1
R2
R3
说明: (1) 一个平面图可以有多个不同形式的平面嵌入,
它们都同构.
(2) 可以通过变换(测地投影法)把平面图的任何一面作为
外部面
5
课件
平面图的面与次数(续)
平面图各面的次数之和等于边数的2倍
证一条边或者是2个面的公共边界, 或者在一个面的边界
中出现2次. 在计算各面的次数之和时, 每条边恰好被计算
2次.
6
课件
极大平面图
若G是简单平面图, 且在任意两个不相邻的顶点
之间加一条新边所得图为非平面图, 则称G为极大平面图
例如 K1, K2, K3, K4都是极大平面图
(1)是K5删去一条边, 是极大平面图. (2)、(3)不是.
(2)
(3)
(1)
7
课件
极大平面图的性质
极大平面图是连通的
设G为n(n3)阶简单图, G为极大平面图的充分必要条
件是, G每个面的次数均为3.
例如
极大平面图
外部面的次数为4
非极大平面图
8
课件
极小非平面图
若G是非平面图, 并且任意删除一条边所得图都
是平面图, 则称G为极小非平面图
例如 K5, K3,3都是极小非平面图
下述4个图也都是极小非平面图
9
课件
欧拉公式
设G为n阶m条边r个面的连通平面图, 则
nm+r=2
证对边数m做归纳证明. m=0, G为平凡图, 结论成立.
设m=k(k0)时结论成立, 对m=k+1,
若G中无圈, 则G必有一个度数为1的顶点v, 删除v及关联的
边, 记作G. G连通, 有n-1个顶点, k条边和r个面. 由归纳假
设, (n-1)-k+r=2, 即n-(k+1)+r=2, 得证m=k+1时结论成立.
否则, 删除一个圈上的一条边,记作G. G连通, 有n个顶点,k
条边和r-1个面. 由归纳假设, n-k+(r-1)=2, 即n-(k+1)+r=2. 得
证m=k+1时结论也成立. 证毕.
10
课件