第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着色的。