文档介绍：第九章:平面图与图的着色
平面图及其欧拉公式
非哈密顿平面图
库拉托斯基定理、对偶图
图的顶点着色
图的边着色
1
平面图及欧拉公式



u
v



u
v
图G称为被嵌入平(曲)面S内,如果G的图解已画在平面S上,而且任何两条边均不相交(除顶点外),已嵌入平面的图称为平面图。
如果一个图可以嵌入平面,则称此图是可平面的。



2



u
v
f1
f2
f3
f4
平面图把平面分成了若干个区域,这些区域都是单连通的,称之为G的面,其中无界的那个连通区域称为G的外部面,其余的单连通区域称为G的内部面。
平面图的内部面与外部面
平面图及欧拉公式
3
平面图的每个内部面都是G的某个圈围成的单连通区域。
没有圈的图没有内部面,只有一个外部面。



u
v
f1
f2
f3
f4
平面图及欧拉公式
1
4
5
3
0
2
4
V-E+F=2
如果用V表示多面体的顶点,用E表示棱,用F表示面数。
(欧拉公式) 如果一个平面连通图有p个顶点、q条边、f个面,则:p-q+f=2
证:对面数用归纳法
当f=1时,G没有内部面
所以G中无圈,G是树;
p-q+f=1+1=2
假如对一切不超过f-1个面的平面连通图欧拉公式成立,现证f个面时的情况。
平面图及欧拉公式
5
f≥2,G至少有一个内部面,从而G中有一个圈,
这个内部面是由这个圈围成的,
从这个圈上去掉一条边x,
则打通了两个面,
G-x有p个顶点,q-1条边,f-1个面
由归纳假设
p-(q-1)+(f-1)=2
p-q+f=2
因此面数是f时也成立。



u
v
f1
f2
f3
f4



u
v
f1
f2
f3
f4
平面图及欧拉公式
6
若平面连通图G有p个顶点q条边且每个面都是由长为n的圈围成的,则
q=n(p-2)/(n-2)
因为G的每个面都是长为n的圈围成的
所以G的每条边都在G的两个面上
证:
q=fn/2
f=2q/n
p-q+2q/n=2
q=n(p-2)/(n-2)
平面图及欧拉公式
7
最大(极大)可平面图
一个图称为最大可平面图,如果这个可平面图再加入一条边,新图必然是不可平面的。




再加一条边就是k5,可证k5是不可平面图。
图1是最大可平面图
平面图及欧拉公式




图1
8




最大平面图的性质
平面图及欧拉公式
设G是一个有p个顶点q条边的最大可平面图,则G的每个面都是三角形,
q=3p-6,p≥3。
9
设G是一个有p个顶点q条边的最大可平面图,则G的每个面都是三角形,
q=3p-6,p≥3。
证:若G的一个面不是三角形,

...

v1
v2
v3
v4
1、假如有两点不相邻,则在此面中把不相邻的两顶点连接起来,不影响平面性。
矛盾,因此不可能有两点不相邻。
平面图及欧拉公式
10