论文部分内容阅读
度因子问题是图论的重要分支之一.因子的存在性与顶点次数有着密切的联系.图有hamilton圈的一些条件被推广到k-因子问题的研究.图的因子分解是比较困难的问题。一个图什么时候有1-因子分解至今没有解决,只对某些图给出了充分必要条件.目前,人们已经研究了许多与图的因子和因子分解相关的问题,且至今已有相当丰富的研究成果.正交因子分解问题是近年来提出的新问题,它在组合设计中有重要应用价值.目前,这方面仍仍有许多没有解决的猜想和问题.
本文主要研究了图的因子与各种参数之间的关系,图有某种因子的一些充分条件以及关于图的因子分解和正交因子分解的几个结果。
本文第一章主要讨论了均衡二部图的2-因子问题,第二章研究了图的(g,f)-因子分解问题和正交因子分解问题.
在实际生活中,有些问题用图的概念来解决不是很适合,需要有向图的概念.我们在无向图中得到的结果有的可以推广到有向图中,有的却不能.本文第三章研究了有向图的(路,圈)-因子分解问题.
本文的主要工作如下:
(1)本文证明了如果G是2n阶均衡二部图,对任意正整数k≥2,若n≥4k-3,且最小度δ(G)≥n+2(k-1)/2,则对G的任意一个完美匹配M,G中存在一个包含M的所有边的恰含k个分支的M-2-因子。而且若G满足|X|=|Y|=n≥sk,其中s≥3,k≥1,是两个正整数,如果σ<,1,1>(G)≥[(1-<1-3>)n]+1,则G有一个2-因子至少含k个长至少为2s的圈.
(2)本文证明了若G是一个(mg+k,mf-k)-图,其中1 ≤k存在具有最小边数和最大边数的(路,圈)-因子,并给出了K<,m,n>的上述(路,圈)-因子分解.