论文部分内容阅读
设G是一个简单图，G的顶点集合是V(G)，边集合是E(G)以及块数是c。若G是连通图且对于任何一个顶点v∈V(G)，G-v都有完美匹配，则称图G是因子临界图。 图的最大匹配计数和完美匹配计数问题是图论和组合最优化中的一个重要问题。它有着广泛的应用[4，6，12]。但是，由[2]可知，一般图的完美匹配计数问题是NP-困难问题，所以最大匹配的计数问题也是困难的。 关于因子临界图的结构问题，Lovász和Plummer[3]给出了因子临界图的耳朵分解。从而人们利用这个耳朵分解得到一系列的成果（参见[6-11，14，15）。文献[6，14，15]中分别刻画了最大匹配数m(G)=|E(G)|，m(G)=|E(G)|-c+1，m(G)=|V(G)|，m(G)=|V(G)|+1以及m(G)=|V(G)|+2的因子临界图的耳朵分解结构。文献[4]给出了具有特殊耳朵分解结构的因子临界图的最大匹配数的计数公式。 本文的第二章在上述结果的基础上，进一步刻画了最大匹配数m(G)=|E(G)|+1的2-连通因子临界图的耳朵分解结构。