匹配生成多项式

图 中的一个 -匹配 是一个包含 条边的集合，其中任意两条边都没有公共顶点（即，大小为 的一个 独立边集）。令 为图 的 -匹配 的数量，其中 （因为由零条边组成的空集 始终是一个 0-匹配）并且 是图 的 边数。那么，匹配生成多项式直接编码了图 的 -独立边集 的数量，并由下式定义

(1)

其中 是图 的 匹配数。

匹配生成多项式对于图的不相交并是可乘的，因此对于图 和 ,

(2)

其中 表示图的并。

匹配生成多项式 与 匹配多项式 的关系为

(3)

（Ellis-Monaghan 和 Merino 2008）以及

(4)

匹配生成多项式与独立多项式密切相关。特别地，由于线图 中的独立边集对应于原始图 中的独立顶点集，因此图 的匹配生成多项式等于 线图 的独立多项式（Levit 和 Mandrescu 2005）。

图 具有完美匹配 当且仅当

(5)

其中 是图 的顶点数。

许多命名图的预计算匹配生成多项式将可以使用变量 通过以下方式获得GraphData[graph,"MatchingGeneratingPolynomial"][x]。

下表总结了一些常见图类的匹配生成多项式的闭合形式。这里， 是第二类合流超几何函数， 是拉盖尔多项式，而 是卢卡斯多项式。

图
完全图
完全二分图
圈图
空图
星图