两类图的结构

来源 :山西大学 | 被引量 : 0次 | 上传用户:fenderchu
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本研究内容涉及图论的两个方面:强连通的弧-准传递有向图的结构;两类变换图是平面图的充要条件。有向图D是局部半完全的,如果它的每一个顶点的内邻集和外邻集都分别诱导出一个半完全有向图。受此启发,1993年,Bang-Jensen给出了弧-局部半完全有向图的定义,证明了半完全二部有向图中哈密尔顿路和圈的结论,以及这些问题的多项式时间可解决性都可以推广到弧-局部半完全有向图中。并且刻划了强连通的弧-局部半完全有向图的结构。第一章中,我们称不包含H3和H4作为诱导子图的有向图为弧-准传递有向图,即:若有z,w∈V(D)-{x,y},满足x→z,z→w,w→y或x→z,w→z,w→y,则x和y一定是相邻的顶点或者是同一个顶点.它可以看作是准传递有向图定义的推广.本文的第一章主要讨论了强连通的弧-准传递有向图的结构。无向图G的全图T(G)是以V(G)∪E(G)为顶点集的图,且T(G)中的两个顶点相邻当且仅当它们在G中相邻或关联。按照类似的方法,BaoYin Wu给出了G的变换图Gzyz的定义.根据这个定义,G的变换图Gxyz共有八类.目前关于这几类变换图已经有很多的结果,如关于它们的直径,连通性以及平面性等等。第二章得到了变换图G--+和G-+-的平面性的充要条件。本文的主要结果叙述如下:定理1.3.3设D是一个强连通的弧-准传递有向图,则D是半完全的或是半完全二部的,或D(≌)M或D(≌)M;推论2.3.1设G是一个图,则G--+是平面图当且仅当n≤3或G同构于2K1+K2,K1+K1,2,K1,3或K1+C3;定理2.3.2设G是一个图,则G-+-是平面图当且仅当n≤4且G(≌)K4-e。
其他文献
学位
学位
学位
该文对于Kothe半单纯环,半质环,有1结合环的交换性进行了研究,给出了一些新的交换性条件.
学位
本文主要给出了单位球上Bloch空间、a-Bloch空间、Besov空间、加权Bergman空间、Dirichlet型空间以及Qp空间的一些新刻画;研究了Hardy空间、加权Bergman空间、混合范数空间、
本文主要介绍了算子半群理论的基础知识,讨论了强连续有界线性算子半群的范数连续性,第三章作为算子半群理论的应用讨论了人口发展系统解的存在唯一性。由[1]知,最终范数连续半
论文研究了三维弹性体有摩擦接触问题的多极边界元法,引入点-面摩擦接触模式,并结合数学规划新思想,建立了三维带摩擦弹性体接触问题的数学规划模型,同时引入最优化理论知识和数