完全偶图的定向图

来源 :山西大学 | 被引量 : 0次 | 上传用户:monishibi
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
设G为无向图,V(G)为顶点集,E(G)为边集。图G的定向图是把图G的每条边(χ,γ)用弧χγ或γχ代替,得到的有向图(即定向图D无二圈和环)。在给无向图定向的过程中,可使定向图满足各种条件,得到具有不同性质的定向图.国内外读者均有深入的研究,Buhler等人研究了超立方体的定向图D,给出了满足D中的顶点的入度或者为a或者为b的部分充分条件和必要条件。然而,本文研究了完全偶图的定向图D,给出了满足D中的顶点。  本研究分为四个部分:第一章介绍了本文的研究背景,研究现状,研究内容及意义和主要结论.国内外读者在定向图满足强连通性,强直径,入度,独立弧数。第二章介绍了本文将要用到的有关图的一些基本概念和术语。第三章介绍了本文的主要研究内容,给出了完全偶图的定向图的顶点的入度只有两个的充分必要条件。用[a,b]n表示把定向为有向图D,使得D中顶点的入度或者是a或者是b的一个图类,并称kn,n是[a,b]n可实现的,简称[a,b]n是可实现的。本文得到的主要结论如下:设n为正整数,a,b∈{0,1,2,...,n},若Kn,n是[a,b]?可实现的当且仅当存在正整数s和t满足下面两个方程。第三章第1节中,本文证明了结论中的必要条件。第2节中,证明了结论中的充分条件,其中用到了算法思想和分类讨论的思想。第四章介绍了本文的创新之处,研究结论和有待进一步研究的问题。本文的创新之处在于,对完全偶图后得到的定向图的顶点的入度不是多个,而是只有两个,使得到的图类简单明了。以后,我们还可以研究其他无向图的定向图,如星图,fc元n方体等。
其他文献
本文研究了几类拟解析系统的中心,等时中心与极限环分支,全文由四章组成。 在第一章,我们对多项式微分系统的等时中心与极限环分支的历史背景与现状进行了概述。 在第二章
国民体质状况和健康水平是一个国家综合国力的重要组成部分,推行体质监测制度是全民健身计划纲要中的重要内容,为保障监测工作规范化和科学性,国家体育总局制定和颁布了《国
本文共包含以下五章内容。第一章简单介绍了本文的研究背景以及主要的研究内容。第二章介绍B样条曲线的定义、性质。第三、四、五章分别介绍了王文涛等提出的带形状参数的均
断裂现象始终是同材料与结构中的孔洞、缺口或裂纹相关联的,在材料的这种宏观不连续部分最明显的特点是应力分布极不均匀,这种现象叫做应力集中。缺陷(孔洞、裂纹、位错等)和应
在声学、电磁学、地震学及其他许多应用领域的大规模的波传播问题的研究中,通常需要在一个长度比波长还要大许多的区域中求波场的分布,在激光的传输和光晶仪器的设计等问题研究
学位