匹配数

（上）匹配数 图 , 有时也称为边独立数，是最大独立边集的大小。等价地，它是匹配生成多项式的度

(1)

其中 是图 的 -匹配的数量。符号 , , 或 有时也被使用。

匹配数也是最大极大独立边集的大小，而最小极大独立边集的大小被称为下匹配数。

满足

(2)

其中 是 的顶点数, 是向下取整函数。等式仅在完美匹配时成立，图 有完美匹配 当且仅当

(3)

其中 是 的顶点数。

图 的匹配数 等于其线图 的独立数 。

柯尼希-埃格瓦里定理指出，对于二分图，匹配数等于顶点覆盖数（即，最小最小顶点覆盖的大小）。

如果图 没有孤立点，则

(4)

其中 是匹配数, 是最小边覆盖的大小, 而 是 的顶点数 (West 2000)。

许多命名图的预计算匹配数可在 Wolfram 语言中使用GraphData[图,"MatchingNumber"].