CHAP11平面图精品文档.ppt

上传人(卖家):晟晟文业 文档编号:4470793 上传时间:2022-12-12 格式:PPT 页数:50 大小:202.36KB
下载 相关 举报
CHAP11平面图精品文档.ppt_第1页
第1页 / 共50页
CHAP11平面图精品文档.ppt_第2页
第2页 / 共50页
CHAP11平面图精品文档.ppt_第3页
第3页 / 共50页
CHAP11平面图精品文档.ppt_第4页
第4页 / 共50页
CHAP11平面图精品文档.ppt_第5页
第5页 / 共50页
点击查看更多>>
资源描述

1、CHAP11平面图精品文档图中的边不要交叉4实际中的很多问题都涉及到一个图中的边是否会交叉的问题。例如:单面印刷电路板,集成电路的布线,交通设计问题;等等。4由此便抽象出平面图的概念:没有交叉(这里当然不是指在端点处的相互邻接)的边的图。4一个有交叉的边的图能不能转换成与之同构的平面图,显然是人们所关注的问题。4本章就是介绍平面图以及平面图的性质。2022-12-1211.1 平面图的概念2022-12-12平面图4定义11.1.1:设G是平面上由有限个点及以这些点为端点的有限连续曲线所组成的图形,如果G中任意两条线最多只在它们的端点处相交,称G为平面图。4例1,图不是平面图,和是平面图。20

2、22-12-12可平面图4上例中的图虽然不是平面图,但是却和图和图是同构的,这样的图称为可平面图。4可平面图:如果一个图G与一个平面图H同构,称G是可平面图;而称H是G的一个平面嵌入。4上例中的图是可平面图,图和图是图的两个平面嵌入。2022-12-12平面图的面4定义11.1.2:设G是一个平面图,平面被G的边所围成的区域称为面,这些边称为该面的边界;其中有限区域对应的面称为内部面,无限区域对应的面称为外部面(用f0表示)。4用G(p,q,r)表示一个p个顶点,q条边以及r个面的平面图。4一个面 f 所包含的边数称为 f 的次数,记为d(f),若边为割边,则计算两次。2022-12-12计算

3、下图中各面的次数:4d(f0)=3;4d(f1)=5。2431f1f0(a)f1f0(b)f24d(f0)=8;4d(f1)=3;4d(f2)=3.2022-12-12面的总次数为边数的两倍4定理11.1.1:对任何平面图G(p,q,r),有 d(fi)=2q,(i=1,2,r).4证明:由于G的每条非割边恰属于两个面,所以,在计算这两个面的次数时,该边计算两次,而割边只属于一个面,但由规定也计算了两次,故上式成立,即所有面的总次数为边数的两倍。4对比:d(vi)=2q,(i=1,2,p),即所有顶点的总度数为边数的二倍。2022-12-12平面图的同构4定义11.1.3:设G和H是两个平面图

4、。如果并且 f 是G中一个由途径uvwu围成的面当且仅当(u)(v)(w)(u)围成H的一个面 f ,则称G与H同构。有时可省略。4例1中图与图就是平面图同构。2022-12-12图的同构与平面图的同构4如果两个图是平面图同构,则必是两个同构的图。可是两个同构的图不一定是平面图同构。4例1中图与图和图是同构的图,但图却不是平面图,因而不可能和它们平面图同构。4下面两个平面图是图同构,但不是平面图同构:GH1345123456622022-12-12外平面图4定义11.1.4:图G称为外可平面图,如果它有一个平面嵌入H,使得G的所有顶点均在H的同一个面的边界上,这时,称H为外平面图。f1f1这是

5、外平面图这不是外平面图这是外可平面图2022-12-12极大平面图4定义11.1.5 设G是一个可平面图,如果对G中任意两个互不邻接的顶点u,v,G+uv成为一个 不可平面图,则称G是一个极大可平面图,极大可平面图的一个平面嵌入称为极大平面图。4说明:对一个不是极大的可平面图,可以添加一些边以得到一个极大可平面图。(如图)2022-12-12G是极大平面图当且仅当G的每个面都是三角形4(必要性)极大简单平面图的任何一个面都是三角形K3。4证明:(反证)设G是极大简单平面图。若G的某个面 f 不是K3,不妨设 f 由闭途径v1v2vnv1围成,且d(f)=n 4。为简单起见,不妨设n=4,即f

6、由闭途径v1v2v3v4v1围成。则 f 只有以下三种情况:v1与v3不邻接;v1与v3邻接,而v2与 v4不邻接;v1与v3邻接,而v2与 v4也邻接。4 下面我们对这三种情况分别予以讨论:2022-12-12极大平面图的面都是三角形证明:若v1与v3不邻接,则v1v2v3v4v1所围成内部面,v1v2v3v4 于是在该面内联 结v1和v3不破坏G的平面性,此与G的假设矛盾;若v1与v3邻接,v2与v4不邻接,则v1v2v3 v1 围成内部面,边v1v4及顶点v4必在此面的外部,v1v2v3v4 故联结v2和v4不破坏G的平面性,此与G的假设矛盾;2022-12-12极大平面图的面都是三角形

7、证明:若v1与v3邻接,且 v2与v4邻接,则v1v2v3v4v1所围成的区域是内部面。因此边v1v3,v2v4都在此面之外,因而必相交,此与G的可平面性矛盾。v1v2v3v4综合以上,知结论成立。2022-12-12(充分性充分性)若平面图若平面图G的每个面都是三角形,的每个面都是三角形,则是则是G是极大平面图。是极大平面图。4 证明:设平面图G的每个面都是K3,若G不是极大平面图.则G中存在u、vV(G),使得uvE(G),且G+uv仍为平面图。4设uv是G+uv中两个面fi和fj的公共边界.于是,G中fi和fj的面是一个面fk,显然,d(fk)3,由此G与的每个面是K3矛盾!2022-1

8、2-1211.2 欧拉公式2022-12-12 欧拉公式4定理:对任何一个简单平面图G(p,q,r)均满足:4 p q+r=2 .4证明:对面数r作归纳证明。4当r=1时,G是树,此时q=p 1,结论成立。4假设对G(p,q,r-1),r2,结论成立,设G是有r个面的平面图,G至少有一条回路。设e是某回路上的边,G e仍是连通平面图,它有p个顶点,q 1条边和r 1个面,由归纳假设有,p(q 1)+(r 1)=2。整理即得 p q+r=2。4由归纳法原理,欧拉公式成立。2022-12-12面等次平面图中边与点的关系4推论11.2.1:若简单平面图G(p,q,r)的每个面的次数均为m,则 q=m

9、(p 2)/(m 2)4证明:由定理11.1.1,2q=d(fi)=mr,解出r,代入欧拉公式,得 p q+(2/m)q=2 整理上式即得证。2022-12-12简单平面图边数的上界4推论11.2.2 对任何简单平面图G(p,q,r)(p 3),q 3p 6 .4证明:由于极大简单平面图的每个面都是K3,故将 m=3代入推论11.2.1中的式q=m(p 2)/(m 2)有 q=3(p 2)=3p 6.故对一般简单平面图有q 3p 6.2022-12-12K5是不可平面图4推论11.2.3 K5是不可平面图。4证明:若K5是可平面图,则由推论11.2.2知q 3p 6,于是 10=q 3p 6=

10、35 6=9,即:10 9,矛盾。故结论成立。2022-12-12无3次面的平面图边数的上界4推论11.2.4:若简单平面图G(p,q,r)的每个面均不是K3,则 q 2p 4 .4证明:由假设每个面的次数至少不小于44 2q=d(fi)4r4即 r q/2,从而由欧拉公式有 2=p q+r p q+q/2=p q/2 整理后得 q 2p 4 .2022-12-12K3,3是不可平面图4推论11.2.5:K3,3是不可平面图。4证明:因K3,3是二分图,故它不含K3,假设K3,3是可平面图,则由推论11.2.4知 9=q 2p 4=26 4=8,即:9 8,矛盾。故结论成立。2022-12-1

11、2简单平面图的最小度小于64推论11.2.6:任何简单平面图G(p,q,r)均有(G)6。4证明:若(G)6,则 4 q=(1/2)d(vi)(2q=d(vi)4 (1/2)p(G)(6/2)p 3p 6,4此与推论11.2.2(对任何简单平面图G(p,q,r)(p 3),都有 q 3p 6)矛盾。故结论成立。2022-12-12极大平面图的五个性质 4定理11.2.2:设简单平面图G(p,q,r)是极大平面图(p 4),于是 q=3p 6;r =2p 4;(G)3;G中至少有4个顶点的度不超过5.2022-12-12极大平面图的边数4证明:由定理11.1.2(极大简单平面图的任何一个面都是三

12、角形K3),将推论11.2.1中的式q=m(p 2)/(m 2)中的m用m=3 代入,即可得q=3p 6 ;2022-12-12极大平面图的面数证明:由性质有q=3p 6,将其代入欧拉公式得:p q+r=p (3p 6)+r=2 ,整理即得r =2p 4;2022-12-12极大平面图连通度不小于34证明:G的面都是K3,(G)2。4 假设(G)=2,则有顶点割S=u,v。其中的u和v都应该与G S的至少两个连通分支中的顶点在G中邻接。4不妨设在G的一个平面嵌入G 中与u邻接的点按环绕u的顺序依次为u1,ut。4而 u1,ut中除可能有一点是v外,其余的点分别属于GS的至少两个分支,必有两点u

13、i和ui+1分属G S的两个不同分支。2022-12-12极大平面图连通度不小于34证明:S是顶点割,ui和ui+1分别属于G S的两个不同分支。uvui+1uif14由ui和ui+1的取法可知,在uui和uui+1之间没有其它与u邻接的边,依据定理 11.1.2,在G 中u uiui+1是一个K3面,故ui和ui+1邻接。4从而在G S中,ui也和ui+1邻接,这与S是顶点割相矛盾。所以(G)3。2022-12-12极大平面图最小度不小于3证明:由定理7.1.1可知图的连通度不大于边连通度,而边连通度又不大于最小度,即(G)(G)(G);又由性质即可得极大平面图最小度不小于3,即(G)(G)

14、3。2022-12-12至少有4个顶点的度不超过5证明:设G的顶点集V=v1,v2,vp。若对i=1,2,p 3,均有d(vi)6,则由性质,对i=p2,p1,p,有d(vi)(G)3。于是,6p 21=2q 9?因为由性质,q=3p 6,于是6p 12=2q 2q d(vj)(这里j=p2,p-1,p)=d(vi)(这里i=1,2,p 3)6(p 3)=6p 18.此为矛盾,故结论成立。习题习题2022-12-1211.3 可平面性判定2022-12-12剖分图4定义11.3.1:设G是一个图,e=uv E(G),在G uv中增加一个新点w及边wu,wv.称此过程为对图G的一次剖分运算。如果

15、H是由G经过有限次剖分运算得到的,则称H是G的剖分图。4直观地说,剖分就是在图的某边上加个顶点。4右边就是K4的剖分。2022-12-12可平面图的充要条件4定理11.3.1(Kuratowski定理)一个图是可平面图的充分必要条件是它不包含K5或K3,3的剖分图.4该定理亦可描述为:一个图是可平面的当且仅当它没有一个可以收缩到K5或K3,3的子图。2022-12-12Petersen图的收缩和剖分Petersen图4例如:Petersen图不是可平面图,因为它含有K3,3的剖分。Petersen图含有K3,3的剖分Petersen图收缩为K5它也可以收缩为K5。2022-12-1211.4

16、平面图的面着色2022-12-12给平面图着色4对简单图G(p,q)只考虑顶点和边,其着色也只有点着色和边着色。4对简单平面图G(p,q,r)则还需要考虑面,其着色还由相应的面着色。4平面图着色的一个直接的重要的应用:地图着色。4用颜色来区分地图中的区域,需要多少种颜色呢?这就是著名的四色问题。2022-12-12面的邻接4定义1.4.1:设 f1 和 f2是平面图G的两个面。若 f1 和 f2的边界至少有一条公共边,则称f1与 f2是邻接的,否则称 f1与 f2不邻接。4三种邻接:点邻接:两个顶点有边相关联;边邻接:两条边有共同的端点;面邻接:两个面有共同的边。2022-12-12有公共顶点

17、的面不是邻接的面4注意:两个面如果在边界上只有一个或有限个公共点,则它们是不邻接的。如下左图中的面A与E,A与C,A与D都不是邻接的面。下右图中的面A与C,B与D也都不是邻接的面ABCDEFABCD2022-12-12面着色4定义11.4.2:设G是平面图,S=1,2,k,k1。若存在面集R(G)到S的满射r,则称r为G的k面着色,S为面色集。若对G中任意两个邻接面 f1和 f2,均有r(f1)r(f2),则称r是正常k面着色,并称G是k面可着色的。图G 的正常k面可着色中最小的k称为G的面色数,记为*(G)。4对比:色数(G):最小正常k(顶点)着色;边色数(G):最小正常k边着色;面色数*

18、(G):最小正常k面着色。2022-12-12对偶图4如果把每个面看作一个顶点,若两个面的边界有一条公共边,则看作两个顶点之间有一条边关联。这样就可以把一个平面图G中面与面之间邻接关系描述为另一个图G*中顶点与顶点之间的邻接关系。4这样对一个平面图G进行转换,所得到的图G*称为图G的对偶图4于是可将对平面图G的面着色转换为对其对偶图G*的点着色问题。2022-12-12对偶图的构造4对偶图的构造:在G的每个面内放一个顶点 f*,这些顶点就构成了G*的顶点集V(G*)。若G的两个面 f 和g有一条公共边e,则画一条以 f*和 g*为端点的边e*,e*仅穿过e一次,对于G中仅属于一个面的割边e,则

19、画一条以 f*为端点的环,穿过e一次。4如果一个图的对偶图就是它自己,则称为自对偶图。2022-12-12对偶图的举例自对偶图2022-12-12G与G*的关系4对任何一个平面图G,G*是唯一确定的:4p(G)*=r(G),q(G*)=q(G);4G*中的顶点 f*和 g*邻接当且仅当G中与 f*和 g*对应的两个面 f 和 g 邻接;4G*有多重边当且仅当G的某两个面至少有两条公共边;4G*有环当且仅当G中有割边。4可将对平面图G的面着色转换为对其对偶图G*的点着色问题:(G*)=*(G)。2022-12-12四色问题4定理11.4.1:所有平面图都是4面可着色的当且仅当所有平面图都是4可着

20、色的.4与四色问题等价的问题:对一个简单平面图G,是否(G)4?4 1976年,美国的Appel,Haken,Koch 借助计算机证明了四色问题.2022-12-12五色问题(一)4定理11.4.2(Headhood,1890):对任何平面图G,(G)5.4证明:对顶点数p作归纳证明。4 归纳基础:当p 5时,结论显然成立。4 归纳步骤:假设对所有顶点数小于 p 的平面图,结论成立。设G为p+1个顶点的平面图,由推论11.2.6,(G)5。4 考虑(p1)阶平面图G v,由归纳假设G v有正常5着色。2022-12-12五色问题(二)4证明:G v有正常5着色。4 若d(v)5,则中至少有 一

21、种颜色i在v的所有邻接点上不出现。令(v)=i,(u)=(u),uv,于是,是G的一个正常5着色。4 若d(v)=5,且的5种颜色均在v的邻接点上出现。不妨设与v邻接的5个点按照环绕v的方向依次为v1,v2,v5,且(vi)=i,i=1,2,5。4 考虑由顶点集V1,3=u|uV(G v)且(u)=1或3所导出的G v的子图G1,3。2022-12-12五色问题(三)4证明:考虑G v的点导出子图G1,3。v1v2v3v4v5v4 若v1和v3属于 G1,3的不同连通分支,则在v1所在的分支中交换颜色1和3,得到Gv的另一个正常5着色。此时,因(v1)=3,(vi)=i,i=2,3,4,5,所以可令(v)=1,从而得到G的一个正常5着色。2022-12-12五色问题(四)v1v2v3v4v5v4证明:若v1和v3属于G1,3的同一个连通分支,则考虑由顶点集 V2,4=u|uV(Gv)且(u)=2或4 所导出的Gv的子图G2,4。v2和v4必属于G2,4的不同连通分支,?4若v1和v3连通,则(v1v3)通路,于是在G中vv1+v3v构成回路C,使得v2和v4分别在C的内部和外部。若v2和v4连通,则连接v2和v4的通路必定与C相交,这与G是平面图矛盾。C4于是对v2,v4也作类似调整,即可得到G的一个正常5着色。即(G)5.4由归纳法原理,定理得证。2022-12-12

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 办公、行业 > 各类PPT课件(模板)
版权提示 | 免责声明

1,本文(CHAP11平面图精品文档.ppt)为本站会员(晟晟文业)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!


侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|