《17平面图及图的着色》由会员分享，可在线阅读，更多相关《17平面图及图的着色（25页珍藏版）》请在金锄头文库上搜索。
1、17.1 平面图的基本概念 一、平面图及平面嵌入 定义 17.1 如果图 G 能以这样的方式画在曲面 S 上，即除顶点处外无边相交，则称 G 可嵌入曲面 S.若 G 可嵌入平面，则称 G 是可平面图或平面图。画出的无边相交的图称为 G 的平面嵌入。无平面嵌入的图称为非平面图。 K 1(平凡图 )，K 2，K 3， K4 都是平面图，其中，K 1， K2，K 3 本身就已经是平面嵌入，K4 的平面嵌入为图 17.1 中(4)所示。K 5e (K5 删除任意一条边)也是平面图，它的平面嵌入可表示为图 17.1 中(5).完全二部图 K1,n(n1), K2,n(n2),也都是平面图，其中标准画法画
2、出的 K1,n 已经是平面嵌入，K 2,3 的平面嵌入可由图 17.1 中(6)给出。图 17.1 中(1) ，(2)，(3)分别为 K4, K5e, K 2,3 的标准画法。请观看演示动画： (1)变(4) (2)变(5) (3)变(6) 图 17.1下文中所谈平面图，有时是指平面嵌入，有时则不是，这要看是研究平面图什么性质而定，请读者根据上下文加以区分。当然有时也特别指出平面嵌入。 现在就应该指出，在研究平面图理论中居重要地位的两个图，这就是完全图 K5 和完全二部图 K3,3，它们都不是平面图(将由定理 17.10 的推论得到证明)。还有两个非常显然的事实，用下面定理给出。 定理 17.
3、1 若图 G 是平面图，则 G 的任何子图都是平面图。 由定理 17.1 立刻可知，K n(n4)和 K1,n(n1)的所有子图都是平面图。 定理 17.2 若图 G 是非平面图，则 G 的任何母图也都是非平面图。 推论 Kn(n5)和 K3,n(n3)都是非平面图。 本推论由 K5，K 3,3 不是平面图及定理 17.2 得证。 还有一个明显的事实也用定理给出。 定理 17.3 设 G 是平面图，则在 G 中加平行边或环后所得图还是平面图。 本定理说明平行边和环不影响图的平面性，因而在研究一个图是否为平面图时可不考虑平行边和环。 二、平面图的面与次数 定义 17.2 设 G 是平面图(且已是
4、平面嵌入) ，由 G 的边将 G 所在的平面划分成若干个区域，每个区域都称为 G 的一个面。其中面积无限的面称为无限面或外部面，面积有限的面称为有限面或内部面。包围每个面的所有边组成的回路组称为该面的边界，边界的长度称为该面的次数。 常记外部面为 R0，内部面为 R1，R 2，R k，面 R 的次数记为 deg(R). 定义 17.2 中的回路组应该这样理解：组中元素可能是圈，可能是简单回路，也可能是复杂回路，或以上元素之并。 图 17.2 所示图是某图的平面嵌入，它有 5 个面。R 1 的边界为圈 abdc，deg(R 1)4.R 2 的边界也是圈，此圈为 efg，deg(R 2)3，R 3
5、 的边界为环 h，deg(R 3)1.R 4 的边界为圈 kjl，deg(R 4)3.外部面 R0 的边界由一个简单回路 abefgdc 和一个复杂回路 kjihil组成，deg(R 0)13. 图 17.2定理 17.4 平面图 G 中所有面的次数之和等于边数 m 的两倍，即 deg(Ri)=2m其中 r 为 G 的面数。 证 本定理中所说平面图当然是指平面嵌入。 eE(G)，若 e 为面 Ri 和 Rj(ij)的公共边界上的边时，在计算 Ri 和 Rj 的次数时，e 各提供 1.而当 e 只在某一个面的边界上出现时，如图 17.2 中的边 i，则在计算该面的次数时，e 提供 2.于是每条边
6、在计算总次数时，都提供 2，因而 deg(Ri)=2m. 三、极大平面图及性质 定义 17.3 设 G 为简单平面图，若在 G 的任意不相邻的顶点 u，v 之间加边(u，v)，所得图为非平面图，则称 G 为极大平面图。 从定义不难看出，K 1，K 2，K 3，K 4，,K 5-e(K5 删除任意一条边)都是极大平面图。还可以容易地证明下面两个定理。 定理 17.5 极大平面图是连通的。 定理 17.6 设 G 是 n(n3)阶极大平面图，则 G 中不可能存在割点和桥。 极大平面图的最大特点由下面定理给出。 定理 17.7 设 G 为 n(n3)阶简单连通的平面图， G 为极大平面图当且仅当 G
7、 的每个面的次数均为 3. 证 本定理的充分性留在第二节的最后证明，下面只证必要性。 图 17.3因为 G 为简单平面图，所以 G 中无环和平行边。由 定理 17.5 和 17.6 可知，G 中无割点和桥。于是 G 中各面的次数大于或等于 3，下面只需证明 G 各面的次数不可能大于 3.假设面 Ri 的次数 deg(Ri)=s4,见图 17.3 所示。 在 G 中，若 v1 与 v3 不相邻，在 Ri 内加边(v 1，v 3)不破坏平面性，这与 G 是极大平面图矛盾，因而 v1 与 v3 必相邻，由于 Ri 的存在，边(v 1，v 3)必在 Ri 外。类似地，v 2 与v4 也必相邻，且边(v
8、 2，v 4)也必在 Ri 外部，于是必产生(v 1，v 3)与(v 2，v 4)相交于 Ri 的外部，这又矛盾于 G 是平面图，所以必有 s3，即 G 中不存在次数大于或等于 4 的面，所以 G 的每个面为 3 条边所围，也就是各面次数均为 3. 在图 17.4 所示的各平面图中，只有(3)是极大平面图。 图 17.4四、极小非平面图 定义 17.4 若在非平面图 G 中任意删除一条边，所得图为平面图，则称 G 为极小非平面图。 请读者验证，K 5 和 K3,3 都是极小非平面图。 17.2 欧拉公式 一、欧拉公式及其推广 欧拉在研究多面体时发现，多面体的顶点数减去棱数加上面数等于 2.后来
9、发现，连通的平面图的阶数，边数，面数之间也有同样的关系。 定理 17.8 (欧拉公式) 对于任意的连通的平面图 G，有 n-m+r=2其中，n，m，r 分别为 G 的顶点数，边数和面数。 证 对边数 m 作归纳法。 (1) m0 时，由于 G 为连通图，所以 G 只能是平凡图，结论显然成立。 (2) 设 mk(k1)时成立，当 mk+1 时，对 G 进行如下讨论。 若 G 是树，则 G 是非平凡的，因而 G 中至少有两片树叶，设 v 为树叶，令 G=G-v，则 G仍然是连通图，且 G的边数 m=m-1=k，由归纳假设可知 n-m+r=2式中 n， m，r 分别为 G的顶点数，边数和面数。而 n
10、=n-1，r=r，于是 n-m+r=(n+1)-(m+1)+r=n-m+r=2若 G 不是树，则 G 中含圈，设边 e 在 G 中某个圈上，令 G=G-e，则 G仍连通且m=m-1=k，由归纳假设有 n-m+r=2而 n=n， r=r-1，于是 n-m+r=n-(m+1)-(r+1)=n-m+r=2下一页 欧拉公式中，平面图 G 的连通性是不可少的。对于非连通的平面图有下面定理成立。 定理 17.9(欧拉公式的推广) 对于具有 k(k2)个连通分支的平面图 G，有 n-m+r = k+1其中 n，m，r 分别为 G 的顶点数，边数和面数。 证 设 G 的连通分支分别为 G1，G 2，G k，并
11、设 Gi 的顶点数，边数，面数分别为 ni，m i，r i，i=1，2，k.由欧拉公式可知: n i-mi+ri = 2，i=1， 2，k(17.1)易知，m= mi，n= ni，由于每个 Gi 有一个外部面，而 G 只有一个外部面，所以 G 的面数 r = ri-k+1,于是，对(17.1) 的两边同时求和得 2k= (ni-mi+ri)= ni - mi + ri= n-m+r+k-1经过整理得 n-m+r = k+1将定理 17.9 称为欧拉公式的推广。由欧拉公式及其推广可以得到平面图的另外一些性质。 二、平面图的边数 m 与顶点数 n 的关系 定理 17.10 设 G 是连通的平面图，
12、且每个面的次数至少为 l(l3)，则 G 的边数m 与顶点数 n 有如下关系： m (n2)证 由 定理 17.4 可知: 2m = deg(Ri) lr(17.2)由欧拉公式可知: r = 2+m-n(17.3)将(17.3)代入 (17.2)得 2ml(2+m-n)经过整理得 m (n2)推论 K5 与 K3,3 都不是平面图。 证 若 K5 是平面图，由于 K5 中无环和平行边，所以每个面的次数均大于或等于l3，由 定理 17.10 可知边数 10 应满足 10 (5-2) = 9这是个矛盾，所以 K5 不是平面图。 类似地，若 K3,3 是平面图，由于 K3,3 中最短圈的长度为 l4
13、，于是边数 9 应满足 9 (6-2) = 8这又是矛盾的，所以 K3,3 也不是平面图。 下一页 定理 17.11 设 G 是有 k(k2)个连通分支的平面图，各面的次数至少为 l(l3)，则边数 m 与顶点数 n 应有如下关系： m (n-k-1)利用欧拉公式的推广形式容易证明此定理。 定理 17.12 设 G 是 n(n3)阶 m 条边的简单平面图，则 m3n-6证 设 G 有 k(k1)个连通分支。若 G 为树或森林，则 mnk3n6(n3).若 G不是树也不是森林，则 G 中必含有圈。又因为 G 为简单图，所以各圈的长度均大于或等于 3，因各面次数至少为 l(l3).又 =1+ 在
14、l=3 时达到最大值 3，由定理17.11 可知 m (n-k-1)3(n-2)=3n-6定理 17.13 设 G 是 n(n3)阶 m 条边的极大平面图，则 m=3n-6证 由于极大平面图是连通图，由欧拉公式得: r=2+m-n(17.4) 又因为 G 是极大平面图，由 定理 17.7 的必要性可知，G 的每个面的次数均为 3，所以: 2m = deg(Ri) =3r(17.5) 将(17.4)代入 (17.5)，整理后得 m = 3n-6.三、简单平面图 G 中， (G)5 定理 17.14 设 G 是简单平面图，则 G 的最小度 5. 证 若 G 的阶数 n6，结论显然成立。因而仅就 n
15、7 讨论。若 6，由握手定理可知 2m= d(vi)6n因而 m3n，这与 定理 17.12 相矛盾。 本定理在图着色理论中占重要地位。 在本节结束之前，来证明定理 17.7 的充分性： 由定理 17.4 可知: 2m = deg(Ri) =3r(17.6)又因为 G 是连通的，由欧拉公式可知: r = 2+m-n(17.7)将(17.7)代入 (17.6)，经过整理得 : m = 3n-6(17.8)若 G 不是极大平面图，则 G 中一定存在不相邻的顶点 u，v，使得 GG(u，v)还是简单平面图，而 G的边数 m=m+1，n=n.由(17.8) 可知， m3n-6这与 定理 17.12 相
16、矛盾。17.3 平面图的判断 一、库拉图斯基的两个定理 为了讨论平面图的判别法，还需要给出下面两个定义。 定义 17.5 设 e=(u，v) 为图 G 的一条边，在 G 中删除 e，增加新的顶点 w，使u，v 均与 w 相邻，称为在 G 中插入 2 度顶点 w.设 w 为 G 中一个 2 度顶点，w 与u，v 相邻，删除 w，增加新边(u，v) ，称为在 G 中消去 2 度顶点 w. 定义 17.6 若两个图 G1 与 G2 同构，或通过反复插入或消去 2 度顶点后是同构的，则称 G1 与 G2 是同胚的。 在图 17.5 中，(1) 与 K3 同胚, (2) 与 K4 同胚。 图 17.5定理 17.
