论文部分内容阅读
本文仅考虑有限、无向简单图.G(B,W;E)表示以B和W为顶点集,E为边集的二部图.如果|B|=|W|,则称G是一个均衡二部图.M是G的一个完美匹配.M-交错路(圈)是一条由匹配边和非匹配边交错出现的路(圈).如果G是具有2n个顶点的二部图,对任意l(2≤l≤n),都有一条长为2l的圈,则称G是泛偶圈的.如果对任意l(2≤l≤n),都有一条长为2l的M-交错圈,则称G是M-泛偶圈的. 匹配问题和泛圈问题都是图论研究的主要问题.对匹配和泛圈性的研究在一个多世纪以前就开始了.目前为止,已经得到很多关于图的哈密顿圈问题、含匹配的哈密顿圈问题,以及泛圈性问题的研究成果,但是关于含匹配的泛圈性问题还未得到关注。本文将匹配与泛圈性结合起来,得到以下结果:对于任意x∈B,y∈W,都有d(x)+d(y)≥3/2n,那么G是M-泛偶圈的.