论文部分内容阅读
设G是一个简单图,具有顶点集合V(G)和边集合E(G)。在连通图G中,如果对任意的υ∈V(G),G-υ有完美匹配,则称G是因子临界图。因此一个因子临界图有奇数个顶点且最小度不小于2。
图的最大匹配计数和完美匹配计数问题是图论和组合最优化中的一个热点研究问题,它有广泛的应用。例如,在化学领域,二部图的完美匹配数是[3,4]中所研究的Kekulé结构数。但是由[2]知:一般图(甚至二部图)的完美匹配计数问题是NP—困难问题,所以最大匹配的计数问题也是困难的。2005年,刘岩老师刻画了最大匹配数m(G)≤|V(G)|+1的因子临界图的结构。2007年,杨春侠刻画了最大匹配数m(G)=|V(G)|+2的因子临界图的结构。本文的第二章在刘岩和杨春侠所做的结果的基础上进一步刻画了最大匹配数m(G)=|V(G)|+3的2-连通的因子临界图的结构。第三章刻画了最大匹配数m(G)=|V(G)|+3的因子临界图的结构。