论文部分内容阅读
在连通图G中,如果对任意一个顶点v,G—v有完美匹配,则称图G是因子临界图.设G’是G的子图,若P是G中一条奇长的路或圈,且除了端点外,其余的内点都不是G’的顶点,则称P是G的相对于G’的耳朵.设P=v1v2…vk是G的路,若d(v1)≥3,d(v1)≥3且P是偶长的悬挂路,或P的任意悬挂的子路P(vi,vj)也是偶长的,dG(vi)≥3,dG(vj)≥3,则称P是一条拟偶悬挂路.
Gallai-Edmonds的图分解理论告诉我们,任意图都可分解成有完美匹配的图,二部图和因子临界图,所以,因子临界图是图的重要组件之一。而有完美匹配的图,是由二部图和双临界图构成的,并且,双临界图在结构和匹配上与因子临界图都有着密切的联系[1-5],所以,研究因子匹配图,对有完美匹配的图有很大的借鉴意义。
图的最大匹配计数和完美匹配计数问题是图论和组合最优化中的一个重要问题,它有着广泛的应用[1,2,6].例如,在化学领域,二部图的完美匹配数足[6]中所研究的Kekulé结构数.但是由[3]知:一般图(甚至二部图)的完美匹配计数问题是NP-困难问题,所以最大匹配的计数问题也是困难的.近年来,关于最大匹配计数问题主要的研究结果是给出最大匹配数的上、下界,并刻划达到界的极图的结构[2,7,8].
在因子临界图的结构方面,人们已经做了不少研究[4,9,10],其中,最重要的结论是Lovász和Plummer[9]给出的因子临界图的耳朵分解结构,迄今为止,耳朵分解在各类图的应用上已经有了蓬勃的发展[11-16]。本文的研究对象是有特殊耳朵分解的因子临界图.该耳朵分解的表述如下:
Lovász[9]证明了每个因子临界图G都有一个耳朵分解,即从奇圈C开始的G的耳朵分解可以用G=C+P1+…+Pk来表示,Pi是G相对于Gi-1的耳朵,令G0=C,Gi-1=C+P1+…+Pi-1,1≤i≤k.本文所研究的因子临界图G,满足对于G的任意一个度不小于3的点v,G—v有唯一的一个完美匹配.在第三章中,我们刻画了满足该性质的因子临界图的结构,即它的耳朵分解；在第四章中,我们得到了该类因子临界图的最大匹配数.从而解决了此类因子临界图的最大匹配计数问题.