完全偶图的定向图

发布时间：2017-06-22 10:14

  本文关键词：完全偶图的定向图，由笔耕文化传播整理发布。

【摘要】：设G为无向图,V(G)为顶点集,E(G)为边集.图G的定向图是把图G的每条边{x,y}用弧xy或yx代替,得到的有向图(即定向图D无二圈和环).在给无向图定向的过程中,可使定向图满足各种条件,得到具有不同性质的定向图.国内外读者均有深入的研究,Buhler等人研究了超立方体的定向图D,给出了满足D中的顶点的入度或者为α或者为b的部分充分条件和必要条件.然而,本文研究了完全偶图的定向图D,给出了满足D中的顶点的入度只有两个的充要条件.本文共分四章.第一章介绍了本文的研究背景,研究现状,研究内容及意义和主要结论.国内外读者在定向图满足强连通性,强直径,入度,独立弧数等方面进行了研究.本文对完全偶图的定向图在入度方面进行了研究.第二章介绍了本文将要用到的有关图的一些基本概念和术语.第三章介绍了本文的主要研究内容,给出了完全偶图的定向图的顶点的入度只有两个的充分必要条件.用[α,b]n表示把Kn,n定向为有向图D,使得D中顶点的入度或者是α或者是b的一个图类,并称kn,n是[α,b]n可实现的,简称[α,b]。是可实现的.本文得到的主要结论如下：设n为正整数,α,b∈{0,1,2,…,n},若Kn,n是[a,b]n可实现的当且仅当存在正整数s和t,满足下面两个方程：第三章第1节中,本文证明了结论中的必要条件第2节中,证明了结论中的充分条件,其中用到了算法思想和分类讨论的思想.第四章介绍了本文的创新之处,研究结论和有待进一步研究的问题.本文的创新之处在于,对完全偶图后得到的定向图的顶点的入度不是多个,而是只有两个,使得到的图类简单明了.以后,我们还可以研究其他无向图的定向图,如星图,k元n方体等.
【关键词】：完全偶图 定向 入度 算法
【学位授予单位】：山西大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 中文摘要6-8
• Abstract8-10
• 第一章 引言10-13
• 1.1 研究背景及研究现状10-11
• 1.2 研究内容及意义11-12
• 1.3 本文的主要结论12-13
• 第二章 预备知识13-15
• 第三章 完全偶图的定向图15-33
• 3.1 准备工作及必要条件的证明15-17
• 3.2 充分条件的算法证明17-31
• 3.3 主要结论31-33
• 第四章 总结与展望33-34
• 4.1 主要结论33
• 4.2 本文的创新之处33
• 4.3 有待进一步研究的问题33-34
• 参考文献34-37
• 攻读学位期间取得的研究成果37-38
• 致谢38-39
• 个人简况及联系方式39-40
• 承诺书40-41

【共引文献】

中国硕士学位论文全文数据库 前1条

1 武艳艳;几类有向图的强直径和强半径[D];山西大学;2013年

  本文关键词：完全偶图的定向图，由笔耕文化传播整理发布。

，

本文编号：471480