第12章 平面图及其应用
12.1 平面图的基本概念
1.若图G=(V, E)存在着一种图形表示，使得将它画在平面上后没有两个结点重合，每条边不自身相交且没有两条边在它们公共关联的结点以外相交，则称G是具有平面性的图，或简称为平面图。
2.若图G是平面图，则G的任何子图都是平面图。
3.若图G是非平面图，则G的任何母图也都是非平面图。
4.Kn (n ≥ 5)和K3,n(n≥3)都是非平面图
5.面；边界；度；外部面
6.面度之和等于边数m的2倍，即
12.2 欧拉公式
1.设G是一个面数为f的(n, m)连通平面图，则
n - m + f = 2
2.对于具有k（ k≥2）个连通分支的平面图G，有
n - m + f = k + 1
3.设G是一个阶数大于2的(n, m)连通简单平面图，则
m ≤ 3n - 6
4.在任何简单连通平面图中，至少存在一个其度不超过5的结点
5.围长：图包含的最短圈的长度
6.设G是一围长 g大于2的(n, m)连通平面图，则
7.和
都是非平面图
12.3 平面图的判断
1.Kuratowski定理：一个图是平面图，当且仅当它不包含与和
的细分图同构子图。
12.4 平面图的对偶图
1.对偶图；存在着对偶图是一个图为平面图的充分必要条件
2.对于G和存在
,在面内的顶点的点度等于面的面度(f为面数)
3.若对偶图与本身同构，则称对偶图为自对偶图。
12.5 平面的点着色和图的着色
1.着色：使无环图相邻结点有不同的颜色
2.若G是k可着色的，但不是(k - 1)可着色的，就称G为k色图，k称为色数，记为。
3.当且仅当G是零图。
4.
5.设G中至少含一条边，则,当且仅当G为二部图。
6.对于任何的图G，均有
7.面着色，
8.地图G是k面可着色的，当且仅当它的对偶图是k可着色的。
9.任何连通平面图都是可以5着色的。
