最大獨立邊集

圖 圖 的獨立邊集（也稱為匹配）是邊的子集，使得子集中沒有兩條邊在 中共享一個頂點。最大獨立邊集是給定圖的所有獨立邊集中包含邊數最多的獨立邊集。

可以使用 Wolfram 語言 計算圖的最大獨立邊集，使用命令：FindIndependentEdgeSet[g]。

最大獨立邊集的大小被稱為匹配數或邊獨立數。

最大獨立邊集不等同於極大獨立邊集，極大獨立邊集僅僅是無法擴充套件到更大獨立邊集的獨立邊集。每個最大獨立邊集也是一個極大獨立邊集，但反之則不然。

給定圖圖的邊覆蓋，不在覆蓋中的所有邊定義了一個獨立集（Skiena 1990, p. 218）。Gallai (1959) 證明了最小邊覆蓋的大小加上最大獨立邊集的大小等於圖的頂點數。

花演算法可以用於在一般圖中找到最大獨立邊集，而更簡單的匈牙利最大匹配演算法可以用於二分圖。