完全偶图的定向图

摘要

设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方体等。

目录

封面

目录

中文摘要

英文摘要

第一章 引言

§ 1 .1研究背景及研究现状

§ 1 .2研究内容及意义

§ 1 .3本文的主要结论

第二章预备知识

第三章完全偶图的定向图

§ 3 .1准备工作及必要条件的证明

§ 3 .2充分条件的算法证明

§3.3 主要结论

第四章 总结与展望

§ 4 .1研究结论

§4.2 本文的创新之处

§4.3 有待进一步研究的问题

参考文献

攻读学位期间取得的研究成果

致谢

个人简况及联系方式

声明