匹配數

（上）匹配數 圖 , 有時也稱為邊獨立數，是最大獨立邊集的大小。等價地，它是匹配生成多項式的度

(1)

其中 是圖 的 -匹配的數量。符號 , , 或 有時也被使用。

匹配數也是最大極大獨立邊集的大小，而最小極大獨立邊集的大小被稱為下匹配數。

滿足

(2)

其中 是 的頂點數, 是向下取整函式。等式僅在完美匹配時成立，圖 有完美匹配 當且僅當

(3)

其中 是 的頂點數。

圖 的匹配數 等於其線圖 的獨立數 。

柯尼希-埃格瓦里定理指出，對於二分圖，匹配數等於頂點覆蓋數（即，最小最小頂點覆蓋的大小）。

如果圖 沒有孤立點，則

(4)

其中 是匹配數, 是最小邊覆蓋的大小, 而 是 的頂點數 (West 2000)。

許多命名圖的預計算匹配數可在 Wolfram 語言中使用GraphData[圖,"MatchingNumber"].