《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.