论文部分内容阅读
分数图论是一个相对年轻的分支.第一部关于分数图论的书籍是ClaudeBerge于1987年写的分数图论[17].图的因子的研究已超过100年。在1891年J.Peterson发现一个关于1-因子的充分条件：每一个2-边连通3-正则图有1-因子[18].W.Tutte在1947年给出一个普通图G有1-因子的充分必要条件[19].而在1952年，W.Tutte给出一个图G有f-因子的判定定理[20]。在1970年，Lovász得到一个图G有(g，f)-因子的充分必要条件[16].从那时起，关于图的因子理论不断涌现.分数因子理论已广泛应用在某些领域，如网路设计、组合拓扑、决定列表等.例如，在通信网络方面，如果我们允许把大型的数据包分割成若干部分由不同的渠道发送到不同的终端，那么电子网络的运送效率会大大提高.如何可行和有效的传送数据包这个问题可以视为如何找到一个满足某些特殊条件的分数因子。 本文所涉及的图均为连通、无向的简单图.设G是一个图，V(G)是顶点集，E(G)是边集.如果去掉任意k个顶点后的子图仍然有一个分数完美匹配，则G称为分数k-因子-临界的.当k=1时，我们称分数1-因子-临界图为分数因子-临界图.图G如果含有一个k-匹配而且图G的每一个k-匹配M都包含在图G的一个分数完美匹配f中而且对于每个e∈M有f(e)=1，则称图G是一个分数k-可扩图。 本文分为四章，主要给出一个图是分数k-因子临界图的领域并条件，并且该条件是最佳的.同时利用分数匹配数μf(G)我们给出一个图是分数k-因子临界图的一个充要条件.除此之外，通过一个图G的连通度k(G)和独立集数α(G)，我们给出图G是分数k-可扩图的一个新的充分条件，并且该条件是最佳的.主要结果有以下： 定理1:设图G是一个有n个顶点的图，k是一个正整数且满足δ(G)≥k+1.如果对任意两个不相邻的点u，v∈V(G)，均有｜NG(u)∪NG(v)｜≥1/2(n+k)，那么G是分数k-因子临界图。 定理2:设设图G是一个k-连通图且｜V(G)｜≥3.那么图G是一个分数k-因子临界图当且仅当对所有的T()V(G)且｜T｜=k(k≥1)有μf(G)=μf(G-T)+k/2。 定理3:设图G的顶点数｜V(G)｜=n.k是一个整数且满足k≤(n-2)/2.如果k(G)≥α(G)+2k，那么G是一个分数k-可扩图。