论文部分内容阅读
具有重要的理论意义的因子问题,一直是图论中的热点话题之一,且至今已有相当丰富的研究成果.关于分数因子的研究也是最近几年提出的新问题.国外数学家在匹配概念的基础上提出因子、分数因子的概念.设夕和t厂是定义在V(G)上的两个整数值函数,且对每个x∈y(G)有0≤g(x)≤f(x),设F是图G的一个生成子图,若对每个x∈y(G)有9(x)≤dF(x)≤f(x),则称F为图G的一个(g,f)-因子.若9(x)=a,f(x)=6,则称上述因子为(a,b)-因子.若a=6=k,则称(a,6)-因子为k-因子.设h是定义在图G的边集E(G)上的一个函数,使得对任意的e∈E(G)有h(e)∈[0,1],令d<,G><,h>(x)=∑<,e∈E<,x>>h(e),其中E<,x<={e|e=xy∈E(G)),则称d<,G><,h>(z)x是G中顶点x的分数度.若h满足对任意的x∈V(G),有g(x)≤d<,G><,h>(x)≤f(x),则称h是G的一个分数(g,h)-表示函数.令E<,h>={e∈E(G)|h(e)≠0},设G<,h>是G的生成子图,若E(G<,h>)=E<,h>,则称G,,h>是G的一个分数(g,f)-因子.类似可定义分数(a,b)-因子,分数k-因子.
在第一章中,我们给出了本文所用的术语、记号.
在第二章中,给出了二分图存在分数k-因子的一个充要条件.
在第三章中,给出了二分图中包含圈和对集的一个证明.
在第四章中,研究了二分图中一个与韧度相关的参数与k-因子存在性的关系.本文主要结果如下:
定理2.1 设G=(X,Y;E)为二分图, G有分数k-因子当且仅当对任意的S? X,T?y,有?其中P<,j>(G)=|{x|d<,G>(x)=j}|.
定理2.2设G=(x,y;E)为二分图,a,6为两个非负整数,且a≤6.若对任意的S?X,T?y,有?