论文部分内容阅读
图的最大匹配计数和完美匹配计数问题是图论和组合最优化中的一个重要问题，它在一些领域有着广泛的应用.例如，在化学领域，二部图的完美匹配数是[4]中所研究的Kekulé结构数.在物理领域，二聚物问题本质上等价于求解图的完美匹配数[5，6，7].
图G的线图表示为L(G)，定义如下，V(L(G))=E(G)，如果e和f在G中有公共端点，那么在线图L(G)中两个顶点e和f相邻.Dong和Yan已经证明对于每一个连通图G都满足M(L(G)≥2|E(G)|-|V(G)|+1，并且得到了满足M(L(G))=2|E(G)|-|V(G)|+1的连通图G的充分必要条件[1]，这里M(L(G))表示线图L(G)的完美匹配个数.本文，我们进一步考虑线图的完美匹配计数问题.我们构造了所有满足M(L(T)=2|E(T)|-|V(T)|+1的树T，得到了满足M(L(G))=2|E(G)|-|V(G)|+1+2的连通图G的充分必要条件，并且构造出所有满足M(L(G))=2|E(G)|-|V(G)|+1+2的连通图G.