1
8.4 平面图
?平面图与平面嵌入
?平面图的面, 有限面, 无限面
?面的次数
?极大平面图
?极小非平面图
?欧拉公式
?平面图的对偶图
2
平面图和平面嵌入
定义 如果能将图 G除顶点外边不相交地画在平面上,
则称 G是 平面图, 这个画出的无边相交的图称作 G
的 平面嵌入, 没有平面嵌入的图称作 非平面图,
例如 下图中 (1)~(4)是平面图,(2)是 (1)的平面嵌入,
(4)是 (3)的平面嵌入, (5)是非平面图,
3
平面图和平面嵌入 (续 )
? 按定义,平面图不一定是平面嵌入, 但今后讨论性质时,通
常是针对平面嵌入的, 今后平面图均指它的一个平面嵌入,
? K5和 K3,3是非平面图
? 设 G??G,若 G为平面图,则 G?也是
平面图 ; 若 G?为非平面图,则 G也
是非平面图,
? Kn(n?5),K3,n(n?3)都是非平面图,
? 平行边与环不影响图的平面性,
K5
K3,3
4
平面图的面与次数
设 G是一个平面嵌入
G的面, 由 G的边将平面划分成的每一个区域
无限面 (外部面 ),面积无限的面,用 R0表示
有限面 (内部面 ),面积有限的面,用 R1,R2,…,Rk表示
面 Ri的边界, 包围 Ri的所有边构成的回路组
面 Ri的次数, Ri边界的长度，用 deg(Ri)表示
说明, 构成一个面的边界的回路组可能是初级回路,简单回
路,也可能是复杂回路,甚至还可能是非连通的回路之并,
定理 平面图各面的次数之和等于边数的 2倍,
5
平面图的面与次数 (续 )
例 1 右图有 4个面,deg(R1)=1,
deg(R2)=3,deg(R3)=2,
deg(R0)=8,请写各面的边界,
例 2 左边 2个图是同一个平面
图的平面嵌入, R1在 (1)中是
外部面,在 (2)中是内部面 ; R2
在 (1)中是内部面,在 (2)中是
外部面, 其实,在平面嵌入中
可把任何面作为外部面,
6
极大平面图
定义 若 G是简单平面图,并且在任意两个不相邻的顶点之
间加一条新边所得图为非平面图,则称 G为 极大平面图,
性质 ?
若简单平面图中已无不相邻顶点，则是极大平面图, 如
K1,K2,K3,K4都是极大平面图, ?
极大平面图必连通, ?
阶数大于等于 3的极大平面图中不可能有割点和桥, ?
设 G为 n(n?3)阶极大平面图,则 G每个面的次数均为 3,
? 任何 n(n?4)阶极大平面图 G均有 δ(G)?3,
7
实例
3个图都是平面图,但只有右边的图为极大平面图,
8
极小非平面图
定义 若 G是非平面图,并且任意删除一条边所得图
都是平面图,则称 G为 极小非平面图,
说明,
K5,K3,3都是极小非平面图
极小非平面图必为简单图
下面 4个图都是极小非平面图
9
欧拉公式
定理 8.11 (欧拉公式 ) 设 G为 n阶 m条边 r个面的连通平面图,
则 n?m+r=2,
证 对边数 m做归纳证明,
m=0,G为平凡图,结论为真,
设 m=k(k?1)结论为真,m=k+1时分情况讨论如下,
(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时结论成立,
(2) 否则,删除一个圈上的一条边,记作 G?,G?连通,有 n个顶
点,k条边和 r-1个面, 由 归纳假设,n-k+(r-1)=2,即 n-(k+1)+r=2,
得证 m=k+1时结论也成立, 证毕,
10
欧拉公式 (续 )
欧拉公式的推广
设 G是有 p (p?2) 个连通分支的平面图,则
n ? m + r = p + 1
证 设第 i 个连通分支有 ni个顶点,mi 条边和 ri 个面,
对各连通分支用欧拉公式,
ni ? mi + ri = 2,i = 1,2,…,p
求和并注意 r = r1+… +rp+ p?1,即得
n ? m + r = p + 1
11
与欧拉公式有关的定理
)2(
2
?
?
? n
l
lm
K5 K3,3
定理 设 G为 n阶连通平面图,有 m条边,且每个面的次数不
小于 l (l ?3),则
证 由定理 (各面次数之和等于边数的 2倍 )及欧拉公式得
2m ? lr = l (2+m-n)
可解得所需结论,
推论 K5 和 K3,3不是平面图,
证 用反证法,假设它们是平面图,
则 K5, n=5,m=10,l=3
K3,3, n=6,m=9,l=4
与定理 8.11矛盾,
12
与欧拉公式有关的定理 (续 )
)1(2 ???? pnl lm
定理 8.11 的推广, 设 G为有 p (p?2) 个连通分支的
平面图,且每个面的次数不小于 l (l ?3),则
定理 8.12 设 G为简单平面图, 则 ? (G)?5,
13
同胚与收缩
消去 2度顶点 v 如上图从 (1)到 (2)
插入 2度顶点 v 如上图从 (2)到 (1)
G1与 G2同胚, G1与 G2同构,或
经过反复插入、或消去 2度顶
点后同构
收缩边 e 如下图从 (1)到 (2)
14
库拉图斯基定理
定理 8.13 G是平面图 ?G中不含与 K5同胚的子图,
也不含与 K3,3同胚的子图,
定理 8.14 G是平面图 ?G中无可收缩为 K5的子图,
也无可收缩为 K3,3的子图,
15
非平面图证明
例 证明 2个图均为非平面图,
证
图中红色部分分别与 K3,3和 K5 同胚
16
平面图的对偶图
定义 设平面图 G,有 n个顶点,m条边和 r个面,构造 G
的 对偶图 G*=<V*,E*>如下,
在 G的每一个面 Ri中任取一个点 vi*作为 G*的顶点,
V*= { vi*| i=1,2,…,r },
对 G每一条边 ek,若 ek在 G的面 Ri与 Rj的公共边界上,
则作边 ek*=(vi*,vj*),且与 ek相交 ; 若 ek为 G中的桥且在
面 Ri的边界上,则作环 ek*=(vi*,vi*),
E*={ ek*| k=1,2,…,m },
17
平面图的对偶图（续）
例 黑色实线为原平面图,红色虚线为其对偶图
18
平面图的对偶图 (续 )
性质,
? G*是平面图, 而且是平面嵌入,
? G*是连通图
? 若边 e为 G中的环, 则 G*与 e对应的边 e*为桥 ; 若 e
为桥, 则 G*中与 e对应的边 e*为环,
? 在多数情况下, G*含有平行边,
? 同构的平面图的对偶图不一定同构,
上面两个平面图是同构的,但它们的对偶图不同构,
19
平面图与对偶图的阶数, 边数与面数之间的关系,
设 G*是平面图 G的对偶图, n*,m*,r*和 n,m,r分别
为 G*和 G的顶点数, 边数和面数, 则
(1) n*= r
(2) m*=m
(3) r*=n-p+1,其中 p是 G的连通分支数
(4) 设 G*的顶点 vi*位于 G的面 Ri中,则 d(vi*)=deg(Ri)
平面图的对偶图 (续 )
8.4 平面图
?平面图与平面嵌入
?平面图的面, 有限面, 无限面
?面的次数
?极大平面图
?极小非平面图
?欧拉公式
?平面图的对偶图
2
平面图和平面嵌入
定义 如果能将图 G除顶点外边不相交地画在平面上,
则称 G是 平面图, 这个画出的无边相交的图称作 G
的 平面嵌入, 没有平面嵌入的图称作 非平面图,
例如 下图中 (1)~(4)是平面图,(2)是 (1)的平面嵌入,
(4)是 (3)的平面嵌入, (5)是非平面图,
3
平面图和平面嵌入 (续 )
? 按定义,平面图不一定是平面嵌入, 但今后讨论性质时,通
常是针对平面嵌入的, 今后平面图均指它的一个平面嵌入,
? K5和 K3,3是非平面图
? 设 G??G,若 G为平面图,则 G?也是
平面图 ; 若 G?为非平面图,则 G也
是非平面图,
? Kn(n?5),K3,n(n?3)都是非平面图,
? 平行边与环不影响图的平面性,
K5
K3,3
4
平面图的面与次数
设 G是一个平面嵌入
G的面, 由 G的边将平面划分成的每一个区域
无限面 (外部面 ),面积无限的面,用 R0表示
有限面 (内部面 ),面积有限的面,用 R1,R2,…,Rk表示
面 Ri的边界, 包围 Ri的所有边构成的回路组
面 Ri的次数, Ri边界的长度，用 deg(Ri)表示
说明, 构成一个面的边界的回路组可能是初级回路,简单回
路,也可能是复杂回路,甚至还可能是非连通的回路之并,
定理 平面图各面的次数之和等于边数的 2倍,
5
平面图的面与次数 (续 )
例 1 右图有 4个面,deg(R1)=1,
deg(R2)=3,deg(R3)=2,
deg(R0)=8,请写各面的边界,
例 2 左边 2个图是同一个平面
图的平面嵌入, R1在 (1)中是
外部面,在 (2)中是内部面 ; R2
在 (1)中是内部面,在 (2)中是
外部面, 其实,在平面嵌入中
可把任何面作为外部面,
6
极大平面图
定义 若 G是简单平面图,并且在任意两个不相邻的顶点之
间加一条新边所得图为非平面图,则称 G为 极大平面图,
性质 ?
若简单平面图中已无不相邻顶点，则是极大平面图, 如
K1,K2,K3,K4都是极大平面图, ?
极大平面图必连通, ?
阶数大于等于 3的极大平面图中不可能有割点和桥, ?
设 G为 n(n?3)阶极大平面图,则 G每个面的次数均为 3,
? 任何 n(n?4)阶极大平面图 G均有 δ(G)?3,
7
实例
3个图都是平面图,但只有右边的图为极大平面图,
8
极小非平面图
定义 若 G是非平面图,并且任意删除一条边所得图
都是平面图,则称 G为 极小非平面图,
说明,
K5,K3,3都是极小非平面图
极小非平面图必为简单图
下面 4个图都是极小非平面图
9
欧拉公式
定理 8.11 (欧拉公式 ) 设 G为 n阶 m条边 r个面的连通平面图,
则 n?m+r=2,
证 对边数 m做归纳证明,
m=0,G为平凡图,结论为真,
设 m=k(k?1)结论为真,m=k+1时分情况讨论如下,
(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时结论成立,
(2) 否则,删除一个圈上的一条边,记作 G?,G?连通,有 n个顶
点,k条边和 r-1个面, 由 归纳假设,n-k+(r-1)=2,即 n-(k+1)+r=2,
得证 m=k+1时结论也成立, 证毕,
10
欧拉公式 (续 )
欧拉公式的推广
设 G是有 p (p?2) 个连通分支的平面图,则
n ? m + r = p + 1
证 设第 i 个连通分支有 ni个顶点,mi 条边和 ri 个面,
对各连通分支用欧拉公式,
ni ? mi + ri = 2,i = 1,2,…,p
求和并注意 r = r1+… +rp+ p?1,即得
n ? m + r = p + 1
11
与欧拉公式有关的定理
)2(
2
?
?
? n
l
lm
K5 K3,3
定理 设 G为 n阶连通平面图,有 m条边,且每个面的次数不
小于 l (l ?3),则
证 由定理 (各面次数之和等于边数的 2倍 )及欧拉公式得
2m ? lr = l (2+m-n)
可解得所需结论,
推论 K5 和 K3,3不是平面图,
证 用反证法,假设它们是平面图,
则 K5, n=5,m=10,l=3
K3,3, n=6,m=9,l=4
与定理 8.11矛盾,
12
与欧拉公式有关的定理 (续 )
)1(2 ???? pnl lm
定理 8.11 的推广, 设 G为有 p (p?2) 个连通分支的
平面图,且每个面的次数不小于 l (l ?3),则
定理 8.12 设 G为简单平面图, 则 ? (G)?5,
13
同胚与收缩
消去 2度顶点 v 如上图从 (1)到 (2)
插入 2度顶点 v 如上图从 (2)到 (1)
G1与 G2同胚, G1与 G2同构,或
经过反复插入、或消去 2度顶
点后同构
收缩边 e 如下图从 (1)到 (2)
14
库拉图斯基定理
定理 8.13 G是平面图 ?G中不含与 K5同胚的子图,
也不含与 K3,3同胚的子图,
定理 8.14 G是平面图 ?G中无可收缩为 K5的子图,
也无可收缩为 K3,3的子图,
15
非平面图证明
例 证明 2个图均为非平面图,
证
图中红色部分分别与 K3,3和 K5 同胚
16
平面图的对偶图
定义 设平面图 G,有 n个顶点,m条边和 r个面,构造 G
的 对偶图 G*=<V*,E*>如下,
在 G的每一个面 Ri中任取一个点 vi*作为 G*的顶点,
V*= { vi*| i=1,2,…,r },
对 G每一条边 ek,若 ek在 G的面 Ri与 Rj的公共边界上,
则作边 ek*=(vi*,vj*),且与 ek相交 ; 若 ek为 G中的桥且在
面 Ri的边界上,则作环 ek*=(vi*,vi*),
E*={ ek*| k=1,2,…,m },
17
平面图的对偶图（续）
例 黑色实线为原平面图,红色虚线为其对偶图
18
平面图的对偶图 (续 )
性质,
? G*是平面图, 而且是平面嵌入,
? G*是连通图
? 若边 e为 G中的环, 则 G*与 e对应的边 e*为桥 ; 若 e
为桥, 则 G*中与 e对应的边 e*为环,
? 在多数情况下, G*含有平行边,
? 同构的平面图的对偶图不一定同构,
上面两个平面图是同构的,但它们的对偶图不同构,
19
平面图与对偶图的阶数, 边数与面数之间的关系,
设 G*是平面图 G的对偶图, n*,m*,r*和 n,m,r分别
为 G*和 G的顶点数, 边数和面数, 则
(1) n*= r
(2) m*=m
(3) r*=n-p+1,其中 p是 G的连通分支数
(4) 设 G*的顶点 vi*位于 G的面 Ri中,则 d(vi*)=deg(Ri)
平面图的对偶图 (续 )
