第七章_平面图

1、平面图一个图G如果能以这样的方式画在平面上;除顶点处外没有边交叉出现,则称G为平面图.画出的没有边交叉出现的图称为G的一个平面嵌入或G的一个平图.图中,(2)是(1)(K4)的平面嵌入,所以(1)是平面图. (2)是平面图. (3),(5)都不是平面图,即K5和K3,3都不是平面图.平面图中的一些概念设G是一个连通的平面图(指G的某个平面嵌入),G的边将G所在的平面划分成若干个区域,每个区域称为G的一个面.其中面积无限的区域称为无限面或外部面,常记成R0.包围每个面的所有边所构成的回路称为该面的边界,边界的长度称为该面的次数,R的次数记为deg(R).对于非连通的平面图G有k(k2)个连通分支

2、,则G的无限面R0的边界由k个回路围成.图(1)所示为连通的平面图,共有3个面R0,R1,R2.R1的边界为回路v1v3v4v1,deg(R1)=3.R2的边界为回路v1v2v3v1,deg(R2)=3.R0的边界为复杂回路v1v4v5v6v5v4v3v2v1,deg(R0)=8.例abcdefghijklmR1R2R3R4R0图(2)与(3)都是(1)的平面嵌入,它们都与(1)同构。图(2),deg(R0)=3;图(3),deg(R0)=4.定理 在一个平面图G中,所有面的次数之和都等于边数n的2倍, 即(r为面数) 1deg()2riiRm极大平面图、极小非平面图设G为一个简单平面图,如果

3、在G中任意不相邻的两个顶点之间再加一条边,所得图为非平面图,则称G为极大平面图.若在非平面图G中任意删除一条边,所得图为平面图,则称G为极小非平面图.例K5, K3,3是极小非平面图， K5任意删除一条边后所得图是极大平面图性质 极大平面图有以下性质;v (1)极大平面图是连通的;v (2)任何n(n3)阶极大平面图中,每个面的次数均为3.v (3)任何n(n4)阶极大平面图G中,均有(G)3.欧拉公式设G为任意的连通的平面图,则有 n-m+r2成立.其中,n为G中顶点数,m为边数,r为面数.证明证明 对边数m作归纳法.v (1)m0时,G为孤立点,此时n1,r1,结论自然成立.v (2)设m

4、k-1(k1)时结论成立,要证明mk时结论成立.证明v首先,若G为树,任取一树叶v并删除它,得GG-v, G中有nn-1个顶点mm-1条边,rr,由归纳假设有下式成立; n-m+r2,即 (n-1)-(m-1)+r2,整理后得 n-m+r2. 证明v其次,G不是树,证明则G中必有初级回路.设C为一初级回路,e在C上.令GG-e,由于e在C上,所以,G仍连通,在G中,nm,mm-1,rr-1,利用归纳假设可得 n-m+r2. 欧拉公式的推广v对于任意的p(p2)个连通分支的平面图G,有 n-m+rp+1成立.定理v设G是连通的平面图,且每个面的次数至少为l(l3),则 (2)2lmnlv证明.

5、2mlr,v n-mr2,vln-lm2m ln-lmlr2l,v lm-2mln-2lv (2)2lmnl推广v设G是p(p2)个连通分支的平面图,每个面的次数至少为l(l3),则(1)2lmnplK5和K3,3vK5和K3,3都不是平面图.若K5是平面图,则每个面的次数至少为3.但是由前面的定理有; 103(5-2)9这是矛盾的,因而K5不是平面图. 类似地,K3,3也不是平面图. 定理6v设G为连通的简单的平面图,则G中至少存在一个顶点v,有d(v)5. v证明.v假设任意顶点v,d(v)6.v 6n2m,3r2mv 3nmv n-mr2v 63n-3m3rm-3m2m0 这不可能.消去

6、 插入v 在图(1)中,从左到右的变换称为消去2度顶点w.图(2)中从左到右的变换称为插入2度顶点w.同胚 初等收缩v如果两个图G1和G2同构,或经过反复插入或消去2度顶点后同构,则称G1与G2同胚.v图G中相邻顶点u,v之间的初等收缩由下面方法给出;删除边(u,v),用新的顶点w取代u,v,使w关联u,v关联的一切边(除(u,v)外).库拉图斯基定理v一个图是平面图当且仅当它不含与K5同胚子图,也不含与K3,3同胚子图.v另一种叙述形式; 一个图是平面图当且仅当它没有可以收缩到K5的子图,也没有收缩到K3,3的子图.agcdefhibj收缩边(a, f), (b, g), (c, h), (

7、d, i), (e, j)，所得图为K5。或者令G=G-(j, g), (d, c)，则G与K3,3同胚例abcdefg令G=G-(d, f), (g, c)，易知G与K5同胚。令G=G-(a, e), (a, f), (b, g), (g, f)，则G与K3,3同胚对偶图v设平面图G,G有r个面,n个顶点,m条边.用如下的方法构造G*;v (1)在G的面Ri中任取一个顶点vi*作为G*的顶点,G*的顶点集V*v1*,v2*,.,vr*,对偶图v(2)若面Ri和Rj的边界中有公共边ek,连接对应顶点vi*和vj*,得G*的边ek*与ek相交.当ek只在G的一个面Rj的边界中出现时,以Ri中的顶

8、点vi*为顶点做环ek*,ek*为G*中一个环.设G*的边集为E*,由于G*的边数与G的边数相同,则E*e1*,e2*,em*,称G*为G的对偶图.例(a)(b)对偶图v对于任意的连通的平面图G,有n*=r,m*=m,r*=n成立,其中,n,m,r分别为G的顶点数、边数和面数.n*,m*,r*分别为G的对偶图G*的顶点数、边数和面数.v同构平面图的对偶图,不一定是同构的.G的对偶图G*的对偶图G*不一定与G同构.染色图 v一个图用彩色将每个顶点着色一个图用彩色将每个顶点着色,相邻顶点染不相邻顶点染不同颜色同颜色.v一个平面图用彩色将每个面着色一个平面图用彩色将每个面着色,相邻面染不相邻面染不同

9、颜色同颜色.只要换成其对偶图即可只要换成其对偶图即可.v平面图平面图G最少用最少用k种颜色染色种颜色染色,就称为就称为k色图色图.vk称为称为chromatic number of G.记做记做(G)v四色定理四色定理:任何一个平面图都是四色任何一个平面图都是四色图图.染色多项式 v用用n种颜色染一个图种颜色染一个图,有多少不同的有多少不同的方法方法,记做记做P G(n)vPG是一个多项式函数是一个多项式函数,称为称为chromatic polynomial of G.v例例4. v设设L4是是4个顶点的一条线个顶点的一条线.用用x种颜种颜色色,第一点第一点,x种方法着色种方法着色,第二点第二

10、点x-1种方法着色种方法着色.第三第四点都是第三第四点都是x-1.vPL4(x)=x(x-1)3. (L4)2.v例例5vP Kn(x)=x(x-1)(x-2)(x-n+1)=xn.v(Kn)n.v定理定理1. 设设G1,G2,Gm是是G的连的连通分量通分量,则则vP G(x) = P G1(x) P G2(x)P Gm(x).v(G)max(G1), (G2),(Gm)v例例6. vG是两个不相连三角形是两个不相连三角形,PG(x)= x2(x-1)2(x-2)2.v例例7. vG是是n个不相连顶点个不相连顶点,PG(x)=xn.Ge是是G去掉去掉e导出的子图导出的子图,Ge是将是将e的的两

11、端点粘合得到的图两端点粘合得到的图.定理定理2. PG(x)PGe(x)-PGe(x)v证明证明. v设设e的端点为的端点为a,b.G着色必须将着色必须将ab着着不同色不同色. Ge着色必须将着色必须将ab着同色着同色.Ge着色着色a,b可着同色可着同色,可着不同色可着不同色.vPGe(x)PG(x)+PGe(x).例 如下图 vPGe(x)=x2(x-1)2(x-2)2,vPGe(x)= x (x-1)2(x-2)2,vPG(x)= PGe(x)-P Ge(x)v=x2(x-1)2(x-2)2-x (x-1)2(x-2)2vx (x-1)3(x-2)2,v(G)=3, G是是3色图色图.ev

12、定理定理3.v设设G是简单图是简单图,G已染色已染色,相邻顶点颜相邻顶点颜色不同色不同.G中染色中染色两种颜色的顶两种颜色的顶点导出子图为点导出子图为G.交换交换G中一个中一个连通分量中染色连通分量中染色和和,G仍然保持仍然保持相邻顶点不同颜色相邻顶点不同颜色.v证明证明.G中任意相邻两点中任意相邻两点a,b. vb G,或或a,bG,或或aG且且b G,a,b染色仍然不同染色仍然不同.v定理定理4(五色定理五色定理)vG是任意一个平面图是任意一个平面图,则则(G)5.v证明证明.对对G的顶点个数归纳的顶点个数归纳.G中至少中至少有一点有一点a,D(a)5.归纳假设去掉归纳假设去掉a,导出导出

13、的子图的子图G可以用可以用5重颜色着色重颜色着色.v如果如果a只与只与G中中4个点相邻个点相邻,a可以用第可以用第五种颜色着色五种颜色着色. v如果如果a与与G中中5个点相邻个点相邻,但但5点中点中有重复颜色有重复颜色,a可以用第五种颜色着可以用第五种颜色着色色.v假设假设a与与G中中5个点相邻个点相邻,5点着色点着色各不相同各不相同,5点分别是点分别是b1,b2,b5. v设设b1着色着色,b2着色着色,而而b1,b2,不不在在G的同一个连通分量中的同一个连通分量中.由引由引理理3,交换交换b3所在分量中颜色所在分量中颜色和和,可以使可以使b1,b3着色相同着色相同.这时这时a可可着色着色.v设设b1着色着色,b3着色着色,而而b1,b3在在G的同一个连通分量中的同一个连通分量中.这