关于一致超图的导出匹配可扩张性

来源 :新疆师范大学 | 被引量 : 0次 | 上传用户:pocohao
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文我们所考虑的超图都是有限的,简单的。   设H是简单超图,如果H的一个匹配M满足:H|V(M)=M,那么我们就称这个匹配M为导出匹配。特别地,如果H的每一个导出匹配都包含于H的某个完美匹配中,那么我们就称H是导出匹配可扩张超图。更进一步地,我们称一个连通的超图H是n可扩张的,如果它满足:   (1)|X(H)|≥rn+r;   (2)H有完美匹配;   (3)对于H的每一个匹配M,如果|M|=n,则存在H的一个完美匹配M*,使得M包含于M*。   超图的匹配和扩张匹配在人员分配问题和最优分派问题上有重要的应用,特别是特殊的超图一图的问题。因此研究超图的匹配具有重要的意义。   图的导出匹配和n可扩张性最初由K.Cameron和M.D.Plummer在[4]和[3]中分别提出来。因此关于这方面图的性质,特别是特殊的图类,已被文献[6],[7],[8],[9],[10],[11],[15],[16],[18],[19]的作者所研究,受这些结果的启发,我们给出了超图的关于导出匹配和可扩张性的一些性质,关于超图的其他的一些性质(如关于他们积的一些性质)在这篇论文中也将被提及,下面是我们的主要结果:   (1)如果H是一个具有|X(H)|个定点的r一致超图,n为一个大于等于2的正整数,这里,如果|X(H)|是r的倍数,而且H是一个n可扩张的超图,那么H也是一个(n-1)可扩张的超图。   (2)如果H是一个n可扩张的超图,而且H不含有导出匹配M使得|M|>n,那么H就是导出匹配可扩张的超图。   (3)如果H是导出匹配可扩张超图,顶点集为X,而且满足:X*真包含于X,Y*真包含于X,X*∪Y*∈H,使得:d(x)=2,d(y)=2,其中对任意x,y,x∈X*,y∈Y*那么Hx(X*∪Y*)是导出匹配可扩张超图。   (4)对于任意超图H和任意一个正整数r,若令K<,n>是r一致完全超图,其中n=rk,k为一正整数,那么H×K<,n>是导出匹配可扩张超图。   (5)假设k1和k2是任意两个正整数, H1和H2分别是k1可扩张的和k2可扩张的两个超图,那么H1×H2是k1+k2+1可扩张的超图。
其他文献
本文主要针对几类离散系统分析了其分岔问题,并得到了一些较新颖实用的结果.全文共分五章. 第一章是综述,介绍离散系统之分岔问题的一般研究方法、研究现状及本文的工作.
本文提出了一种利用复杂系统组成设备的试验信息,对复杂系统平均寿命进行综合评估的方法。首先,考虑单个设备情况下的可靠度评估问题,在完全样本情形下利用枢轴量方法对不同设备
拓扑图论研究的一个重要内容为图在曲面上的嵌入的性质.回顾历史,拓扑图论学家们首先研究的是图的最小亏格.由于确定图的最小亏格是NP-困难的[25],因此求解图的最小亏格或者确定
小波理论因其独特的优势,一经出现便得到了广泛的应用。在实际应用中,人们总希望能够得到同时满足对称性、紧支性以及正交性的小波系统,而我们知道,除Haar小波以外的单小波无法同