An introduction to matching polynomials
An introduction to matching polynomials
复制标题
DOI：
10.1016/0095-8956(79)90070-4
复制
发表时间：
1979-08
期刊：
影响因子：
--
通讯作者：
E. Farrell
中科院分区：
文献类型：
--
作者：
E. Farrell
图G的一个匹配是G的一个生成子图，其中每个分支都是G的一个结点或一条边。对于每一个匹配M，我们可以关联一个单项矩阵<$（M）=<$αwα，其中w α是与分量相关联的权重，乘积是M中所有分量的乘积。G的匹配多项式是多项式M（M），其中求和是对G中的所有匹配进行的。由于匹配的边是图的独立边，所以匹配多项式的项的系数表示G中各种基数的独立边的集合的数目。
A matching of a graphGis a spanning subgraph ofGin which every component is either a node or an edge ofG. With every matchingM, we can associate a monomialΠ(M) =Παwαwherewαis a weight associated with the component and the product is taken over all components inM. The matching polynomial ofGis the polynomialΣΠ(M), where the summation is taken over all matchings inG. Since the edges of a matching are independent edges of the graph, the coefficients of the terms of the matching polynomial represent the number of sets of independent edges of various cardinalities inG.