1. 基本概念

• 平面图：将G除了顶点外无边相交地画在平面上。这种画法称为图的平面表示，也叫平面嵌入。
  • K 5 K_5K5​和K 3 , 3 K_{3,3}K3,3​都不是平面图。
• 如果图是平面图，那么子图是平面图。
• 如果子图是非平面图，那么图是非平面图。
  • 据此，我们可以知道，K n ( n > = 6 ) K_n(n>=6)Kn​(n>=6)以及K 3 , n K_{3,n}K3,n​都是非平面图。
• 平行边和环不影响平面性。

上图中(a)和(b)经过重新绘制后变成(e)和(f)，它们不包含任何交叉边，是一个平面图。而 c、d分别是K 3 , 3 K_{3,3}K3,3​和K 5 K_5K5​，都不是平面图。

面：由边划分出来的区域。

无限面/外部面：面积无限大的面。

有限面/内部面：面积有限的面。

边界：回路组。回路组可以是非连通回路之并。

次数：边界的长度，记作deg

Ps：上图来自东北大学离散数学MOOC

r1区域，边界为ABCDFDA，deg(r1)=6

r2区域，边界为ABCA，deg(r2)=3

r3区域，边界为ACDA，deg(r3)=3

r0区域，边界为ADA，deg(r4)=2

定理：平面图各个面的deg之和=边数的二倍

以上图为例，次数之和=14，边数=7，满足。

如果平面图G有K个面，可用R 1 , R 2 , . . . , R k R_1,R_2,…,R_kR1​,R2​,…,Rk​表示，不需要指出外部面。

Ps：上图来自东北大学离散数学MOOC。

deg(R1)=1

deg(R2)=3

deg(R3)=2

deg(R0)=8，这体现了回路组可以是非连通回路之并。分别是abcdeafg

2. 欧拉公式

• 定理7-2：设G是n阶m边r面的连通平面图，n-m+r=2。
• 证明：
  • m=0，平凡图，成立。
  • 设m=k(k>=1)为真，m=k+1时，分情况讨论。
    • 如果是G无回路，G为树，如果要将k+1变到k，我们删除一条边，即删除一个叶子结点， n-1-(m-1)+r=n-m+r=2，等式依旧成立。
    • 如果G有圈，圈上删除一条边，这条边是两个面的公共边，删除后r-1，所以n-(m-1)+r-1=2仍然不变。
• 定理7-3：设G是具有k个连通分支的平面图，则n-m+r=k+1

理解：外部公共面会被加k次，所以需要减去k-1。

即当G是连通的时候，等式右边是r；当G是不连通的时候，等式右边是k+1

• 定理7-4：设G为连通的平面图，且d e g ( R i ) > = l , l > = 3 deg(R_i)>=l,l>=3deg(Ri​)>=l,l>=3，则m < = l l − 2 ( n − 2 ) m<= \frac{l}{l-2}(n-2)m<=l−2l​(n−2)
  • 证：2 m = ∑ i = 1 r d e g ( R i ) > = l ∗ r = l ( 2 + m − n ) 2m= \sum_{i=1}^{r}deg(R_i)>=l*r=l(2+m-n)2m=i=1∑r​deg(Ri​)>=l∗r=l(2+m−n)解得：m < = l l − 2 ( n − 2 ) m<=\frac{l}{l-2}(n-2)m<=l−2l​(n−2)也可以得到：m < = 3 n − 6 m<=3n-6m<=3n−6
  • 推论：K 5 K_5K5​中，m=10，3n-6=3*5-6=9，不满足，所以不是平面图。K 3 , 3 同理， m = 9 , 3 n − 6 = 12 K_{3,3}同理，m=9, 3n-6=12K3,3​同理，m=9,3n−6=12不满足关系，所以不是平面图。
• 定理7-5：在具有k(k>=2)个连通分支的平面图中，m < = l l − 2 ( n − k − 1 ) m<=\frac{l}{l-2}(n-k-1)m<=l−2l​(n−k−1)
• 定理7-6：设G是n(n>=3)阶m边的简单平面图，则m < = 3 n − 6 m<=3n-6m<=3n−6

案例：证明若G为简单平面图，则δ ( G ) < = 5 \delta(G)<=5δ(G)<=5

证明：当n<=6，结论为真。当n>=7时，如果δ > = 6 \delta>=6δ>=6，根据握手定理，2m>=6n，得到m>=3n，与定理7-6矛盾。

3. 平面图的判定

• 同胚：如果G1和G2是同构图，或者经过反复插入或删除2度顶点后得到的两个图同构，则称G1和G2同胚。

PS：上图来自引用3，他们删去或者反复插入2度顶点后显然同构，所以这些图同胚。

• 定理7-7【库拉托夫斯基（Kuratowski）定理】：G是平面图当且仅当G中不含与K 5 K_5K5​或K 3 , 3 K_{3,3}K3,3​同胚的子图。

应用库拉托夫斯基定理，通过同胚操作，可证明上图均为非平面图。

七. 图着色问题

对于图的着色问题，可以转化为对其对偶图的着色问题。

1. 对偶图

• 对偶图的定义：设G是某平面图的某个平面嵌入，构造G的对偶图G*如下：
  • 在G的面R i R_iRi​中放置G*的顶点v i ∗ v_i^*vi∗​
  • 若G中的边e在面R i R_iRi​与R j R_jRj​的公共边界上，做G ∗ G^*G∗的边e ∗ e^*e∗与e相交，即e ∗ = ( v i ∗ , v j ∗ e^*=(v_i^*,v_j^*e∗=(vi∗​,vj∗​)，且e ∗ e^*e∗不与其它任何边相交。
  • 若e只是面R i R_iRi​的一个面边界，则e ∗ e^*e∗是R i R_iRi​中G ∗ G^*G∗的顶点v i v_ivi​端点的环，即e ∗ = ( v i ∗ + v j ∗ ) e^*=(v_i^*+v_j^*)e∗=(vi∗​+vj∗​)

PS：上图来自东北大学离散数学MOOC，我们首先对每个面R1、R2、R3分别放置一个顶点，v 1 ∗ v_1^*v1∗​、v 2 ∗ v_2^*v2∗​、v 3 ∗ v_3^*v3∗​。对于v1-v2我们防止一条交叉边，同理对于v1-v4、v2-v3、v3-v4我们都放置一条边。值得注意的是，v2-v5这条边只是R3一个面的边界，我们所做的交叉只关联R3中的顶点v 3 ∗ v_3^*v3∗​，构成一个环。

• 定理8-1：设置G ∗ G^*G∗是连通平面图G的对偶图，n ∗ 、 m ∗ 、 r ∗ n^*、m^*、r^*n∗、m∗、r∗和n、m、r分别是G ∗ G^*G∗和G的顶点数、边数和面数。那么n ∗ = r ， m ∗ = m ， r ∗ = n n^*=r，m^*=m，r^*=nn∗=r，m∗=m，r∗=n，设G*的顶点v i ∗ v_i*vi​∗位于G的面R_i中，则d ( v ∗ ) = d e g ( R i ) d(v^*)=deg(R_i)d(v∗)=deg(Ri​)

2. 自对偶图

定义：设G是平面图G是对偶图，如果说G和G是同构的，就称G*为G的自对偶图。

轮图：在n-1阶圈内放置一个顶点，连接这个顶点与这个圈轮上的所有顶点，所得的n阶简单图称作n阶轮图，记做Wn。

n阶轮图都是自对偶图。

Ps：上图来自东北大学离散数学MOOC，上述轮图都是自对偶图。

3. 点着色

• 点着色：给G的每个顶点都涂上颜色，保证相邻的顶点的颜色都是不同的。
• k着色：能够用k种颜色对G进行点着色。
• 色数：χ ( G ) = k \chi(G)=kχ(G)=k，表示图G是k可着色的，但不是k-1可着色的。

PS：上图来自东北大学离散数学MOOC，我们可以分别求其色数。色数分别是2、3、4、5.

4. 着色方法

• Welch Powell着色方法：
  • 对G按照顶点的度数进行递减排序，排序不唯一。
  • 用第一种颜色对第一个结点进行着色，并按照排序将与第一个点不相邻的结点度都着上相同的颜色。
  • 用另一种颜色对尚未着色的点进行排序，重复上述过程。