減少二分配匹配

Question

給定一個具有n個頂點和m個邊的無向圖，是否有一種簡單的方法來說明是否可以從圖中刪除邊以便最終每個頂點的度數爲1？

Answer 1

什麼你要找的是尋找一個完美匹配在一般圖（完美匹配定義的算法是一組邊這樣的那個所有頂點在圖中被本組恰好一度觸及）。顯然，完美匹配只存在於偶數個頂點的圖中。

要找到這種匹配是否存在，您可以使用一種算法來查找最大匹配（圖中最大可能的匹配）並檢查它是否完美。 The blossom algorithm用於查找一般圖中的最大匹配。