论文部分内容阅读
本文我们所考虑的超图都是有限的,简单的。
设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可扩张的超图。