关于可平面图的边剖分的若干结果

来源 :山东大学 | 被引量 : 0次 | 上传用户:donny0325
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文考虑的图若无特殊声明均为简单、无向有限图。对于一个图G=G(V(G),E(G)),本文用V(G)和E(G)分别表示图的顶点集合和边集合。对任意的ν∈V(G),采用d<,G>(ν)表示顶点ν在G中的度数。△(G)和δ(G)分别表示图G的最大度和最小度。对V(G)的子集S,用G-S表示从G中删去顶点集合S及其关联的边所得到的子图。若S={ν},则令G-ν=G-{ν}。对E(G)的子集x,用G-X表示从G中删去边集合X所得的子图。若X={e},则G-{e}简记为G-e。若存在V(G)的两个不交子集X、Y,使得V(G)=X ∪Y,且G的所有边均一个端点在X内,另一个端点在Y内,则称G为二部图,记为G=(X,Y,E(G))。 若图G可以表示在平面上,并且任两条边仅在其端点处才可能相交,则称G是可平面图。图G的这种平面上的表示法称为G的一个平面嵌入,或称为平面图。对于一个平面图G,我们用F(G)来表示G的面集合。对于一个面f,我们把将f围起来的所有的边所构成的集合称为f的边界,并且称f关联于其边界上的所有的顶点和边。同样地,可以定义,的度dG(f)为f的边界上的边数。若G的两个面f<,1>和f<,2>有一条公共边e,则称面f<,1>和f<,2>相邻接于边e。若存在映射φ:E(G)→{1,2,…,κ},对于G中任意两条相邻接的边e<,1>和e<,2>,满足φ(e<,1>)≠φ(e<,2>),则称G是κ一边可染色的。这时对于任意的1≤i≤κ,φ<-1>(i)的边导出子图均是图G的一个匹配。我们把使得图G具有κ-边染色的最小正整数κ定义为G的边染色数,记作X(G)。 若图的每一个连通分支都是一条路,则称该图为一个线性森林。我们称映射ψ:E(G)→+{1,2,…,t)为图G的一个t-线性染色,如果对于任意的1≤α≤t都有,ψ<-1>(α)的边导出子图是一个线性森林。本文把使图G具有t-线性染色的最小正整数t称为G的线性荫度,记作lα(G)。 图的染色理论是图论的一个重要分支,是图论研究中最活跃的课题之一。根据一定的规则将一组目标划分为不同的种类,这是数学中的一个基本方法。不同的规则决定着该组中任意一对目标是否在同一个类中。图的染色理论就是研究这类问题的一门理论,它有着相当广泛的应用背景。各种形式的日程表问题,时间表问题以及排序问题,从根本上来说都可以归结为染色问题。对染色理论的研究最早可以追溯至1852年,即著名的“四色猜想”的提出。而图的边染色问题引起人们关注的时间相对较晚。但是,许多研究领域,如地图染色,匹配理论以及拉丁方,都与边染色问题有着紧密的联系。关于边染色的第一篇文章出现在1880年,由P.G.Tait在对“四色猜想”做进一步的研究时,证明出“任一2-边连通,3-正则的甲面简单图是3-边可染色的”与“四色猜想”足等价的。此后,关于边染色问题的研究又有了一些比较重要的结论,如Konigs Theorem,Shannons Theorem以及Vizings Theorem。图的边染色中,根据著名的Vizings Theprem,可以将简单图分为两类。图的分类问题就是判断一个图G究竟是第一类图,还是第二类图的问题。关于图的分类问题,虽然已有一些相关的结论,但是未解决的部分还有很多。而对于可平面图的边染色的分类问题,Vizing证明出任一△(G)≥8的可平面图G均是第一类图,而△∈{2,3,4,5}的可平面图中存在第二类图。于是Vizing在1968年的时候,提出了著名的可平面图猜想。 图G的线性荫度这一概念是由Harary在1970年提出的。接着在1980年,由Akiyama,Exoo和Harary等人给出了关于正则图的线性荫度的猜想;并且在这一猜想的基础上,产生了著名的线性荫度猜想(the Linear Arboricity Conjecture,简称为LAC)。在对线性荫度猜想进行研究时,J.Wu解决了可平面图条件下这个猜想的大部分情况,只余下△=7这一种情况仍未解决。 本文中主要研究的是可平面图的边染色及线性荫度方面的一些结果。 全文共分三章,第一章简单介绍一下图论中的一些基本概念,并给出边染色、线性荫度问题的历史背景和进展状况以及一些已有的相关结论。这一章是后面其他各章节的基础。 第二章我们主要讨论可平面图的边染色的一些情况。主要结论为:定理2.1.10.设G是最大度为5的可平面图。若G中不含长度为4的圈,或不含长度为5的圈,则G是第一类图。 第三章则讨论了可平面图的线性荫度的一些情况,其主要得出了33个定理。
其他文献
对于Kundu-Eckhaus(KE)方程,我们构造了其显示的达布变换(DT)解析表示。KE方程的解和n阶的达布变换Tn可以由只含有用初始的特征函数和种子解的行列式表示,而且通过对退化的特
近年来,单光子发射层析成像(Single Photon Emission Computed Tomography简记为SPECT)已成为核医学领域中不可或缺的一部分,对体内器官疾病的诊断起着重要作用,已被广泛应用
渗漏水事故是隧道工程最常见的危害形式,因此预防和处理渗漏水事故是隧道工程设计和施工技术的重要部分。本文结合温福线八仙仑隧道工程对渗漏水的处理情况,分析了渗漏水事故的
期刊
图的交叉数是在近代图论中发展起来的一个重要概念,主要研究如何把图画在一个平面上,使其交叉的数目最少。通常这项研究都采用纯数学方法证明。然而,确定一般图的交叉数是一个NP
期刊
期刊
介绍了该工程的空调系统设计,主要包括冷热源、水系统、风系统、防排烟系统、自控系统、室内游泳池及温泉休闲中心空调系统的设计。宴会厅、大堂、休闲厅、餐厅等大空间采用全
期刊
具有线性红利界限的经典风险模型最早是由Gerber(1974)首先提出的,他对经典风险模型做了如下修正:盈余一旦超过红利界限便发放红利,直至下一次索赔发生,这样就使得盈余一旦超过红
期刊
多媒体时代,教育方式已由传统的老师、学生二点式变为老师、学生和多媒体技术三点式。多媒体技术的使用为思想政治教育带来很多便捷,但也伴随着一些潜在的问题。本文通过对电