对于简单图来讲,它的每个内部面至少要由三条边围成,每条.ppt

对于简单图来讲,它的每个内部面至少要由三条边围成,每条.ppt

ID:52344771

大小:466.50 KB

页数:32页

时间:2020-04-04

对于简单图来讲,它的每个内部面至少要由三条边围成,每条.ppt_第1页
对于简单图来讲,它的每个内部面至少要由三条边围成,每条.ppt_第2页
对于简单图来讲,它的每个内部面至少要由三条边围成,每条.ppt_第3页
对于简单图来讲,它的每个内部面至少要由三条边围成,每条.ppt_第4页
对于简单图来讲,它的每个内部面至少要由三条边围成,每条.ppt_第5页
资源描述:

《对于简单图来讲,它的每个内部面至少要由三条边围成,每条.ppt》由会员上传分享,免费在线阅读,更多相关内容在PPT专区-天天文库

1、对于简单图来讲,它的每个内部面至少要由三条边围成,每条边最多为两个面的边界。定理6.1:若连通平面图G有n个顶点,e条边和f个面,则n-e+f=2---称为欧拉公式证明:对边数进行归纳证明:对于一条边的连通平面图,第一个n=2,f=1,e=1,n-e+f=2,成立第二个n=1,f=2,e=1,n-e+f=2,成立假设对于一切m-1条边的连通平面图,欧拉公式均成立。现考察m条边的连通平面图。(1)若G有一个度数为1的顶点,则删去该顶点及其关联边,便得到一个连通平面图G'。删去度数为1的顶点不影响连通性。而且度数

2、为1的顶点不在回路上,因此不会增加和减少回路数。因此面数不变。(2)若G中没有度数为1的顶点,则删去一个有界面边界上的任一条边,因为删去回路上的一条边不影响连通性,因此得到一个连通平面图G'。对于平面图,嵌如平面的画法可以有多种,但不管怎样,面数总是相等的。必须强调的是:欧拉公式只适用于连通平面图,即任何一个连通平面图一定满足欧拉公式,不满足欧拉公式的连通图一定不是平面图。但是面数确定是比较困难的。推论6.1:若G是n3的平面简单图,则e3n-6。证明:显然只要对连通平面简单图证明即可。设G是n3的连通

3、平面简单图,G的每个面由三条或更多条边围成,因此边的总数s大于或等于3f(这里边的总数包括重复计算在内)。即s3fs=4+3+3+6=16另一方面,因为每条边至多是两个面的公共边,也就是说每条边至多被计算两次,即s2e,由此定理我们可以证明K5是非平面图,因为K5是连通的,n=5,e=10,若K5是平面图,则由推论应该有e3n-6即103*5-6=9,矛盾,所以K5不是平面图。在这里要注意:对于n3的平面简单图,一定成立e3n-6。若e>3n-6,则一定不是平面图。但对于简单图,即使满足e3n-

4、6,也不一定是平面图。例如,K3,3,n=6,e=9,3n-6=3*6-6=12>9=e,成立,但K3,3不是平面图。推论6.2:若平面图的每个面由四条或更多条边围成,则e2n-4证明:因为每个面由四条或更多条边围成,因此边的总数s大于或等于4f,即s4f证明K3,3不是平面图例:小于30条边的连通平面简单图中存在顶点度数不超过4的顶点。证明:若所有顶点度数都大于4,即G中所有顶点度数都5。二、平面图的特征找出一个图是平面图的充分必要条件的研究曾经持续了几十年,直到1930年库拉托斯基(Kuratows

5、ki)给出了平面图的一个非常简洁的特征。首先介绍剖分的概念:给定图G的一个剖分是对G实行有限次下述过程而得到的图:删去它的一条边{u,v}后添加一个新的点w以及新的边{w,u}和{w,v}。也就是说在G的边上插入有限个点便得到G的一个剖分。下图中给出了K5的一个剖分。定理:(1)若图G的一个子图是Kn的剖分,则G中至少有n个顶点度数大于等于n-1;(2)若图G的一个子图是Kn,n的剖分,则G中至少有2n个顶点度数大于等于n。例:G=(V,E),

6、V

7、=7,若G中含有K5的剖分,则不含有K5或K3,3的剖分.定

8、理6.3(库拉托斯基定理):图G是平面图当且仅当它的任何子图都不是K5或K3,3的剖分。上例中G是非平面图,而是平面图此定理告诉我们:(1)一个图是平面图,则不含有K5的剖分,也不含有K3,3的剖分。(2)若图G不含有K5的剖分,也不含有K3,3的剖分。则G一定是平面图。(3)若图G含有K5的剖分,则G一定不是平面图;若图G含有K3,3的剖分,则G一定不是平面图。(4)若图G不是平面图,则或者G含有K5的剖分,或者G含有K3,3的剖分。库拉托斯基定理虽然很漂亮,但是在具体判定一个图是不是平面图时,这个定理并不

9、能起作用。因此以后仍有许多这方面的研究工作。在这里几何对偶常简称为对偶。由定义可知,若G是连通平面图,则G*也是连通平面图,而且G和G*的顶点数,面数和边数有下列简单的关系。定理6.4:设G是有n个顶点,e条边,f个面的连通平面图;又设G的几何对偶G*有n*个顶点,e*条边,f*个面,则n*=f,e*=e,f*=n。由于平面图G的对偶G*也是平面图,同样可对G*作几何对偶,记为G**。若G是连通的,则G**与G之间有一个特别简单的关系,如下所述。定理6.5:G是连通平面图当且仅当G**同构于G。由定义6.3的

10、过程可知,平面图G的任何两个几何对偶必同构。又平面图G1与G2同构,但未必G1*与G2*同构。关键是嵌入方式不同。6.2顶点着色定义6.4:设G是一个没有自环的图,对G的每个顶点着色,使得没有两个相邻的顶点着上相同的颜色,这种着色称为图的正常着色。图G的顶点可用k种颜色正常着色,称G为k-可着色的。使G是k-可着色的数k的最小值称为G的色数,记为(G)。如果(G)=k,则称G是k色的。如下图(a

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。