平面图及着色.ppt

《平面图及着色.ppt》由会员分享，可在线阅读，更多相关《平面图及着色.ppt（57页珍藏版）》请在课桌文档上搜索。

1、第四章 平面图,第一节 平面图定义1 如果图G能示画在曲面S上且使得它的边仅在端点处相交，则称G可嵌入曲面S。如果G可嵌入平面上，则称G是可平面图，已经嵌入平面上的图 称为G的平面表示。可平面图G与G的平面表示 同构，都简称为平面图。(球极投影),定理1 图G可嵌入球面图G可嵌入平面。,例1 Q3是否可平面性？,定义2(平面图的面,边界和度数).设G是一个平面图，由G中的边所包围的区域，在区域内既不包含G的结点，也不包含G的边，这样的区域称为G的一个面。有界区域称为内部面，无界区域称为外部面。包围面的长度最短的闭链称为该面的边界。面的边界的长度称为该面的度数。,例2 指出下图所示平面图的面、面

2、的边界及面的度数。,解:面f1,其边界1e15e24e43e72e101,d(f1)=5.面f2,其边界1e102e87e91,d(f2)=3.面f3,其边界2e73e67e82,d(f3)=3.面f4,其边界3e44e57e63,d(f4)=3.外部面f5,其边界1e15e24e36e34 e57e91,d(f5)=6.,定理2 对任何平面图G，面的度数之和是边数的二倍。证明:对内部面而言,因为其任何一条非割边同时在两个面中,故每增加一条边图的度数必增加2.对外部面的边界,若某条边不同时在两个面中,边必为割边,由于边界是闭链,则该边也为图的度数贡献2.从而结论成立.定理3 设G是带v个顶点，

3、e条边，r个面的连通的平面图，则 v-e+r=2。（欧拉公式）证明:(1)当n=e=1时,如下图,结论显然成立.,v=2,e=1,r=1,v=1,e=1,r=2,(2)下用数学归纳法证明.假设公式对n条边的图成立.设G有n+1条边.若G不含圈,任取一点x,从结点x开始沿路行走.因G不含圈,所以每次沿一边总能达到一个新结点,最后会达到一个度数为1的结点,不妨设为a,在结点a不能再继续前进.删除结点a及其关联的边得图G,G含有n条边.由假设公式对G成立,而G比G多一个结点和一条边,且G与G面数相同,故公式也适合于G.若G含有圈C,设y是圈C上的一边,则边y一定是两个不同面的边界的一部分.删除边y得

4、图G,则G有n条边.由假设公式对G成立而G比G多一边和多一面,G与G得顶点数相同.故公式也成立.,推论1 设G是带v个顶点，e条边的连通的平面简单图，其中v3，则e3v-6。证明:由于G是简单图,则G中无环和无平行边.因此G的任何面的度数至少为3.故2e=d(f)3r(1)其中r为G的面数.由欧拉公式v-e+r=2所以r=2-v+e,代入(1)中有:2e3(2-v+e)即e3v-6。,推论2 设G是带v个顶点，e条边的连通的平面简单图，其中v3且没有长度为3的圈，则e2v-4。证明:因为图G中没有长度为3的圈,从而G的每个面的度数至少为4.因此有2e=d(f)4r(1)其中r为G的面数.由欧拉

5、公式v-e+r=2所以r=2-v+e,代入(1)中有:2e4(2-v+e)即e2v-4。例3 K5和K3.3都是非平面图。解:图K5有5个顶点10条边,而3*5-6=9,即109,由,推论1知,K5是非平面图.显然K3,3没有长度为3的圈,且有6个顶点9条边,因而92*6-4,由推论2知K3,3是非平面图.推论3 设G是带v个顶点，e条边，r个面的平面图，则 v-e+r=1+w。其中w为G的连通分支数。证明:由欧拉公式有:vi-ei+ri=2(i=1,2,w)从而有 vi-ei+ri=2w又 vi=v,ei=e,ri=r+(w-1)(外部面被重复计算了w-1次.).所以有:V-e+r+(w-1

6、)=2w整理即得:v-e+r=1+w.,推论4 设G是任意平面简单图，则（G）5。证明:设G有v个顶点e条边.若e6,结论显然成立;若e6,假设G的每个顶点的度数6,则由推论1,有6v 2e 6v-12矛盾,所以（G）5.例4 平面上有n个顶点，其中任两个点之间的距离至少为1，证明在这n个点中距离恰好为1的的点对数至多是3n-6。证明:首先建立图G=,其中V就取平面上给定的n个点(位置相同),当两个顶点之间的距离为1时,两顶点之间用一条直线段连接,显然图G是一个n阶简单图.,由推论1,只要证明G为一平面图时即知结论成立.反设G中存在两条不同的边a,b和x,y相交于非端点处o,如下图(a)所示,

7、其夹角为(0).若=,这时如下图(b),显然存在两点距离小于1,与已知矛盾,从而0.由于a到b的距离为1,x到y的距离为1,因此a,b,x,y中至少有两个点,从交点o到这两点的距离不超过1/2,不妨设为a,x,则点a与x之间的距离小于1,与已知矛盾,所以G中的边除端点外不再有其它交点,即G为平面图.再据推论1,知结论成立.,第2节 库拉图斯基定理与极大平面,定义1 设G是一个平面图，通过除G的一条边x、y,并增加一个新结点a和两条边x、a与a、y（所获得的任何图也是平面图），这样的操作称为初等细分。若可以从相同的图G通过一系列初等细分来获得图G1和G2，称G1和G2是同胚的.如下图G1,G2,

8、G3是同胚的.,定理1一个图G是非平面的，当且仅当它包含一个同胚于K3.3或K5的子图。（证略）例1 说明彼得森图不是平面图。解:删去下图(a)皮得森图的结点b,得其子图(b)H.而H胚于K3.3,所以皮得森不是平面图.,(c)K3,3,说明:库拉图斯基给出了平面图的充要条件,但用它并不能判别一个图是否是平面图的有效算法.定义2设G是阶大于等于3的简单可平面图，若在任意两个不相邻的结点vi,vj之间加入边vi,vj，就会破坏图的平面性，则称G是极大平面图。极大平面图的平面表示称为三角剖分平面图.定理2.极大平面图的判别定理:v阶简单平面图G是极大平面图的充要条件是:（1）G中每个面的度数都是3

9、（2）G中有e条边r个面，则3r=2e（3）设G带有v个顶点，e条边，r个面则 e=3v-6,r=2v-4.,证明:必要性:因G是简单图,故G中没有环和平行边,故不存在度数为1或2的面.假设G存在度数大于3的面f,不妨设为内部面,如下图G,显然v1与v3不相邻,在面f内加入面v1,v3,图G的平面性显然没有改变,这与图G是极大平面图矛盾.因此图G的每个面的度数为3,所以有3r=2e且e=3v-6,r=2v-4(欧拉公式)充分性显然.,定理2 设G是简单平面图，则G有平面表示，使 中每条边都是直线。,证明:只要对极大平面图G来证明定理即可(简单平面图是极大平面图的子图).当v=3时,G是三角形,

10、定理显然成立.假设定理对所有阶数小于v的极大平面图成立,并设G是三角剖分图.选取xV(G)使x不是外部剖面边界上的点.取边x,y.则边x,y仅是某两个内部三角形的公共边.不妨设这两个三角形分别为z1xy和z2xy.如图(b)所示.收缩边x,y,且结点x和y收缩为P,得图G(图c).显然G是平面图,且有E(G)=E(G)-3=3(V(G)-1)-6=3V(G)-9=3V(G)-6,即G是v-1阶极大平面图,由归纳假设,G,有平面表示,使 的每条边都是直线.考虑 中边Pz1和Pz2,将它分裂成两个三角形(图(b)和图(c).这样得到的图 就是G的平面表示,而且每条边都是直线段.定理得证.,凸多面体

11、,平面图的理论与多面体的研究密切相关:事实上,由于每个凸多面体P可以与一个连通可平面图G对应,G的顶点和边是P的顶点和棱,那么G的每个顶点的度至少为3.由于G是一个平面图,则P的面就是G的面,并且G的每一条边落在两个不同面的边界上.一个多面体P的顶点,棱和面的数目分别用V,E和F来表示,而且,这些分别是连通图G的顶点,边和面的数目.故欧拉公式可写成V-E+F=2,这就是著名的Euler凸多面体公式.为方便起见,用Vn和Fn分别表示凸多面体P的n度点和n度面的数目,则n3且,多面体的一些性质定理,定理3 每个凸多面体都至少有一个n度面,其中3n5.证明:设F3=F4=F5=0,则即有F1/3E,

12、又即V 2/3E,所以E=V+F-2 1/3E+2/3E-2=E-2.矛盾.所以结论成立.,正多面体 每个面且每个多面角都相等的凸多面体。定理4 只有五个正多面体:四面体、立方体、十二面体、八面体、二十面体.证明:设P是正多面体且G是对应的平面图,对任何凸多面体均有:因为P是正多面体,所以存在两个正整数h(3)和k(3)使F=Fh且V=Vk,因此,有-8=(h-4)Fh+(k-4)Vk,且hFh=2E=kVk,因3h5.,(1)当h=3时,有12=(6-k)Vk,由3k5.当k=3时,V3=4,F3=4,此时P是四面体.当k=4时,V4=6,F3=8,此时P是八面体当k=5时,V5=12,F3

13、=20,此时P是十二面体(2)当h=4时,有8=(4-k)Vk,所以k=3,V3=8,F4=6,即P是立方体.(3)当h=5时,有20=(10-3k)Vk,所以k=3,V3=20,F5=12,即P是十二面体.,例2 对哪些n,存在n条棱的凸多面体？,解:以多面体的顶点为图的顶点,以多面体的棱为图的边,得到一个平面图G,若p(G),q(G),f(G)分别表示G的顶点数,边数和面数,则p(G)4,f(G)4,且每个面的度数是3,由Euler公式易得q(G)6,即没有棱小于6的凸多面体.四面体是棱数为6的凸多面体.若有7条棱的凸多面体,则存在满足上述条件,q(G)=7的平面图,由Euler公式p(G

14、)+f(G)=q(G)+2=9,但G的每个面的度数至少是3,故2q(G)=G(m)3f(G)(m为G的面),即f(G)(2/3)*q(G)=14/3又f(G)为整数,所以f(G)4,同理p(G)4,所以p(G)+f(G)8,矛盾.所以7条棱的凸多面体不存在.,现对k4,以k边形为底的棱锥即有2k条棱的凸多面体进行讨论.若把底为k-1边形的棱锥中,底角处的一个三角面“锯掉一个尖儿”,得到的是一个有2k+1条棱的凸多面体,总之,当n 6,n7时,才有n条棱的凸多面体.,第三节 图的平面性检测,定义1 图G的H片:设H是G的子图，在E(G)-E(H)上定义二元关系R如下：xRy在G-E(H)中存在一

15、条链W使得:（1）W的第一条边为x，最后一条边为y；（2）W中只有两个端点属于H(即W的内部点不属于H).R是E(G)-E(H)上的等价关系。R确定E(G)-E(H)上的一个划分设为S=S1、S2、Sm由Si导出的 G-E(H)的子图 B1、B2、Bm 称为G的H片。,定义2.若H1和H2都是图G的子图，称V（H1）V（H2）为H1和H2在G中的接触点集。记作VG(H1,H2).定义3 设H是可平面图G的子图，是H的平面表示，若存在G的平面表示,使 称 是G容许的。,若B是G的H片，f是 的面而且VG（B,H），称B在f内可画出，其中 是f的边界。定理1设 是G容许的，则对 的每一个片B，其中

16、 证明:若 是G容许的,则存在G的一个平面表示.显然,H的片B所对应的 的子图必然限制在 的一个面中,因此.,图G的平面检测的DMP算法,DMP算法是由Demoucron,Malgrange,Pertuiset提供的.在介绍该算法前,先对图G进行如下预处理:(1)若G不连通,分别检测每一个连通分支.当且仅当所有的连通分支都是平面图,G就是平面图.(2)若G有割点,分别检测每一块.当且仅当每一块是平面图.(3)删去G中的环.(4)用一条边代替G中2度点和与之相关联的两条边.(5)删去平行边.反复交错使用(4)与(5),直到不能使用为止.在做了上述简化后,在简单图G中利用(6)和(7)两个基本判断

17、法:(6)若e3v-6或5,则G不是平面图.若不满足(6)和(7),则需进一步检测.,DMP算法（1）设G1是G中的圈，求出G1 的平面表示。令i=1.（2）若E（G）-E（Gi）=，则停止。若E（G）-E（Gi），则确定G的所有Gi片，对每个Gi片B，求出集（3）若存在Gi片B使 则停止，此时知G是非平面图。若存在Gi片B使 则令f=;若不存在这样的片B，则令B是任何一个Gi片并任取。(4)选取一条xy路Pi B使x,yVG（B，Gi）,令Gi+1=GiP,并把Pi画在的 面 f内得Gi+1的一个平面表示，用i+1代替并转入第2步。,例1利用DMP算法检测图G的平面性,第四节 平面图的着色,

18、定义1设G是无孤立结点的连通的平面图，且G有K个面F1，F2，Fk(包括外部面).则按下列过程作G的对偶图G.（1）在G的每个面内设置一个结点vi(1ik)。（2）过Fi与Fj的每一条公共边ek作一条仅作一条边vi,vj与ek相交。（3）当且仅当ek只是Fi的边界时，vi恰有一自回路与ek相交。这样所得的图G*称为图G的对偶图.若G*与G同构,称G是自对偶的.如下图G的对偶图为图中虚线.,定义2 图的着色是对该图的每个顶点都指定一种颜色，使没有两个相邻的顶点指定为相同的颜色。如果这些顶点选自于一个有k种颜色的集合，而不管k种颜色是否都用到，这样的着色称为k着色。定义3 图G的色数是着色这个图G

19、所需要的最少颜色数。记作(G)。图G的色素也称为图G的点色素.从定义可知,对于G的任何子图H,均有x(H)x(G).若G是n阶完全图,若G是n阶完全图,则x(G)=n;若G是至少有一边的二分图,则x(G)=2;若G是长为奇数的圈,则x(G)=3.当x(G)3时,G的特征至今尚未清楚,在下一节,将给出G的色素x(G)的一个上界.,定理1 设u和v是图G中两个不相邻的顶点,则(G)=min(G+u,v),(Gu,v),其中Gu,v是把G中结点u与v重合成一个新结点，且G中分别与u与v关联的边都与该新结点关联。证明:记e=u,v,（1）设x(G)=k,并考虑G的K着色.假设顶点u与v染不同的颜色,则

20、G的k着色也是G+e的k着色.此时x(G+e)k=x(G).现假设顶点u和v的染色相同,则G的一个k染色可得到Ge的一个染色.故(Ge)k=x(G).又在G的k染色中,或者u与v染为不同的颜色,或者为相同的颜色,故min(G+u,v),(Gu,v)x(G).,（2）G是G+e的子图,显然x(G)x(G+e).设(Ge)=k1,并把结点u和v重合所得的新结点记为y,则在Ge的k1着色中,把分配给y的颜色分配给G中u和v(u,v不相邻),即可得到G的一个k1着色.故 x(G)k1=x(Ge)所以x(G)min(G+e),(Gu,v).综（1）（2）所述,有(G)=min(G+u,v),(Gu,v)

21、.四色问题:连通简单平面图的色素不超过4.四色问题是盖思里于1852年提出,后经众多数学家尝试证明,均以失败告终.1976年,美国数学家阿佩尔和黑肯宣布借助用计算机证明,但时间超过了1000小时,其可靠性仍在置疑之中.,定理2（五色定理）连通简单平面图G的色数为不超过5.,证明:对图的顶点数n作归纳.n5时,结论显然.若n-1个顶点时结论成立.下证有n个顶点时结论也成立.由于G是平面图,则(G)5.故在G中至少存在一个顶点v0,其度数d(v0)5.在图中删去顶点v0得图G,由归纳假设知G的色素为5.然后将v0又加回去,有两种情况:(1)d(v0)5或d(v0)=5但和v0邻接的5个结点的颜色数

22、小于5.则v0极易着色,只要选择与四周顶点不同的颜色着色即可.,(2)d(v0)=5且和v0邻接着的5个结点着的颜色的是5种颜色,如下图(a)所示.称G中所有红黄色顶点为红黄集,称G中所有黑白色顶点为黑白集.故又有两种可能.(i)v1和v3属于红黄集导出子图的两个不同块中,如下图(b)所示.将v1所在块的红黄色对调,并不影响G的正常着色.然后将v0着上红色,即的图G的正常着色.,(a),(b),(ii)v1和v3属于红黄集导出子图的同一块中,则v1和v3之间必有一条属于红黄集的路P,P加上结点v0可构成圈C:v0v1pv3v0,如下图所示.由于C的存在,将黑白集分成两个子集,一个在C内,一个在

23、C外.于是问题转化为(i)的类型,对黑白集按(i)型的办法处理,即得图G的正常着色.,(b),(c),(a),例1求下图G和H的色数,a:红,b:蓝,c:绿,d:红,e:绿，f:蓝,g:红(3色),例2.由n(n3)个顶点v1,v2,vn以及边v1,v2,v2,v3,vn-1,vn vn,v1 组成的图称为圈图,记作Cn,试问圈图的Cn的色数是多少。（分n为奇数，或偶数）例3.Kn和Km,n的色数分别是多少？解:由于Kn的每两个顶点都相邻,而当两个相邻的顶点必指定不同的颜色,故Kn的色素为n.Km,n的色数为2.用一种颜色着色m个顶点,用另一种颜色着色n个顶点.,第五节 图着色的应用,贮藏问题

24、:某工厂生产n种化学制品c1,c2,cn,其中某些制品是互不相容.若它们相互接触,则会发生化学反应甚至引起爆炸,为安全起见,该工厂必须把仓库分成若干隔间,以便把不相容的化学制品储藏在不同的隔间,试问该仓库至少应分成几个隔间?解:构建简单图G=,其中V(G)=c1,c2,cn 边ci,cjE(G)化学制品ci与cj互不相容.易知,仓库的最少隔间数等于图G的色素x(G).,电视频道分配问题,某地区内有n家电视发射台T1,T2,Tn.主管部门为每家电视发射台分配一个频道.为排除干扰,使用同一频道的电视台之间的距离必须大于指定的正数d,试问该地区至少需要多少频道?构建简单图G=,其中V(G)=T1,T

25、2,Tn 边Ti,TjE(G)Ti与Tj之间距离d.易知,需要的最少频道等于图G的色素x(G).,考试安排问题,某高校有n门选修课程v1,v2,vn需要进行期末考试.同一学生不能在同一天里参加两门课程的考试.问学校的期末考试需要几天?构建简单图G=,其中V(G)=v1,v2,vn 边vi,vjE(G)vi与vj被同一同学选修.故考试需要的最小天数等于图G的色素x(G).,变址寄存器,在有效的编译器里,当把频繁使用的变量暂时保存在中央处理单元而不是保存在常规内存时,可以加速循环的执行.对于给定的循环来说,需要多少个变址寄存器?可以这样建立模型:设图里的每个顶点表示循环里的一个变量.若在循环执行期

26、间两个顶点所表示的变量必须同时保存在变址寄存器里,则这两个顶点之间有边.因此,所需要的变址寄存器数就是该图的色数.,顺序着色算法,到目前为止,还没有一个有效算法来确定色素.顺序着色算法是一个求x(G)的有效算法:设G=是简单无向图，V=x1,x2xn用N(xi)表示与xi相邻的全部顶点集合；对顶点xi着色C，记为(xi)=C.i:=1c:=1若对yN(xi),(y)C,则令(xi)=C并转入第5步。C:=C+1并转入第3步。若in，则i:=i+1并转回第2步，否则停止.,定理1设G是简单连通图，顺序着色法产生G的顶点的一个(G）+1着色，所以(G)（G）+1(不证),证明:顺序着色法用语言描述

27、就是一次考虑每一顶点,将尚未指定给与其邻接的顶点的最小颜色指定给该顶点,特别是决不能将两个相邻顶点指定为相同的颜色,因此顺序着色算法确实产生一个顶点着色.最多存在个顶点与xi邻接,故在x1,x2,xi-1中最多有个顶点xi邻接.所以,当算法对顶点xi着色时,在颜色1,2,+1中至少有一种颜色尚未指定给与xi邻接的顶点并且算法将这些颜色中最小的指定给xi,于是顺序着色算法产生图G的顶点的一个+1着色.,例1试用顺序着色法求图G的色数。,定理1给出了连通简单图G的色数的上界.1941年R.L.Brooks证明了下面的定理.定理2.设G是一个连通简单图,其顶点的最大度为.若G既不是完全图Kn,也不是

28、奇数圈图Cn,则x(G).,第六节 边着色,定义1 图G的边着色对G的每一条边都指定一个颜色，使得没有两个相邻的边都为同一种颜色。如果这些颜色都取自一个有K种颜色的集合，而不管这K种颜色是否都用掉，这样的边着色称为K边着色。定义2 图G的边着色数是着色这个图G需要的最少颜色数。记为(G).,边着色转化为点着色的方法：,边着色可以转化为相应的点着色,即在边着色图中,将所有的边对应地转化成点着色图中的结点,结点转化成相应的边.因此,由点着色性质定理不难得到如下定理.定理1 若G是非空连通的简单图，G的最大顶点度为,则(G)+1。（不证）图的分类:据定理1,所有非空图集可以分成两类,若(G)=(G)

29、,则G为第一类图,否则称为第二类图.,定理2 任意二分图G是第一类图。（不证）K着色问题:已知一个图G和k种颜色的集合:1,2,k,则存在图G的多少k-着色?定义3.图G的不同K着色的数目，称为图G的色多项式。记作f(G,k).说明:(1)若k0的最小k 即为G的色数.(2)设mi是i种颜色对图G的顶点进行着色的不同方案数.用k(ki)种颜色对图G进行着色,每取i种,颜色时,共有miCki种不同的着色方案,故有:f(G,k)=m1Ck1+m2Ck2+mnCkn,其中n为图G的顶点数.显然,f(G,k)是k的多项式.图的两种基本运算:(1)Guv 设u,v是图G的不邻接的两个顶点,把u,v收缩成

30、一个顶点x,并把G中凡与u,v关联的边均使之与x关联,这样所得的新图。记作Guv.(2)G:e 把图G的一条边删去并使它的两个端点重合,也即边e被收缩.这样得到的新图。记作G:e.,定理3.设u,v是G的两个不相邻的顶点则 f(G,k)=f(G+u,v,k)+f(G:uv,k)推论 设e=u,v是图G的边，则f(G,k)=f(G-e,k)-f(G:e,k)说明:定理3表明,若G是有P个顶点和q条边的图,则有一个q+1条边的图G1=G+u,v(u与v不相邻接)和一个有P-1个顶点的图G2=Guv,使f(G,k)=f(G1,k)+f(G2,k).对G1和G2依次类推,直到只出现完全图为止.因此,一

31、个图的色多项式f(G,k)是f(Kn,k)型的表达式的和.,完全图的色多项式,例1.对三阶完全图K3而言,有f(K3,k)=k(k-1)(k-2).解:由于对K3中的任何指定一个顶点,可以用k种颜色中的任何一种进行着色;对K3的第二个顶点,可以用k-1种颜色中的任何一种进行着色;对K3的第三个顶点,可以用k-2种颜色中的任何一种进行着色.一般地,对于P阶完全图，有f(Kp,k)=k(k-1)(k-2)(k-p+1),例1三阶完全图K3 有f(K3,k)=k(k-1)(k-2)例2求图G的色多项式。,f(G,k)=k5+3k4+k=k(k-1)(k-2)(k-3)(k-4)+3k(k-1)(k-

32、2)(k-2)(k-3)+k(k-1)(k-2)=k5-7k4+18k3-20k2+8k,定理4.n阶图G的色多项式f(G,k)，其首项为kn，常数项为零，此外系数的符号为正负相间.证明:对边数进行归纳证明.显然,当=0时,定理成立.这是因为n个顶点的空图的色多项式为kn.假设定理对少于条边的图成立 设e是G的一条边,则G-e是有n个顶点-1条边的图,Guv是有n-1个顶点和至少有-1条边的图.由归纳假设,存在非负整数系数a1,a2,an-1和b1,b2,bn-2使得:f(G-e,k)=kn-an-1kn-1+an-2kn-2+(-1)na1k,和f(Guv,k)=kn-1-bn-2kn-2+bn-3kn-3+(-1)n-2 b1k再由推论,有f(G,k)=f(G-u,v,k)-f(Guv,k)=kn-(an-1+1)kn-1+所以结论成立.,