独立边集

图 的独立边集（也称为匹配）是边的子集，其中子集中没有两条边共享 的顶点（Skiena 1990，第 219 页）。图中大小为 的独立边集的计数通过其匹配生成多项式进行编码。

图中独立边集的数量有时称为 Hosoya 指数。

最大尺寸的独立边集称为最大独立边集，而无法通过在图中添加任何其他边来扩展到另一个独立边集的独立边集称为极大独立边集。

最大独立边集可以在Wolfram 语言中使用以下代码计算：FindIndependentEdgeSet[g].

图中最大独立边集（即任何最大独立边集）的大小称为其匹配数（或边独立数）。