偶數個頂點的高效完美匹配算法？

什麼是最有效的算法來檢測是否存在一個完美的匹配在偶數個頂點的圖中？偶數個頂點的高效完美匹配算法？

2014-01-21 Pratham Desai

Edmond的算法？ http://en.wikipedia.org/wiki/Matching_(graph_theory)#In_general_graphs –

@NiklasB Edmond的算法不僅可以檢測，還可以找到一種完美匹配的方法。是否還有其他一些算法時間複雜度較低的知識來了解存在？ –

我非常懷疑。通常，這些問題的決策變體與構建解決方案一樣難以解決。雖然我不能肯定地說。 –

編輯：正如NiklasB指出的，我給出的第一個答案是不正確的。

要更正一下，我下面說（見1一個更下段的深入討論）：首先，TUTTE矩陣是正規的變量的矩陣，所以其決定因素是在正規的變量項的多項式，而不是一個數字。由於T是一個形式矩陣，因此計算其行列式可能需要指數時間。但是，我們並不需要真正計算det（T），只是測試它是否爲0多項式。這意味着對於T中變量的每個數字賦值，det（T）將產生0.進一步可以證明，如果不存在完美匹配，對於變量賦值，det（T）將評估到一個非零變量。因此，我們可以用T中的變量替換隨機值並計算行列式。如果我們評估一個非零值，我們可以放心地說沒有匹配。否則，如果我們重複這個足夠多的次數，我們就會達到所需的信心，說存在完美匹配。

該算法仍然受到採取行列式的運行時限制。當前最有效的已知算法的運行時間爲O（n^2.373），在這種情況下爲O（| V |^2.373）。這是什麼意思？

Edmond's有O（| E | sqrt（| V |））。

對於某些類型的圖形，特別是密集圖形，這實際上可以打敗愛德蒙的，漸近地。但就像我提到的，這仍然是一個隨機算法，不是一個確切的算法。

編輯點評：它所具有的一個好處是它比Edmonds更容易圍繞實際的工具包裹頭部。在C中實施Edmond's是我大學生涯中最悲慘的夜晚之一。

ORIGINAL錯誤答案：可以使用TUTTE矩陣找到完美匹配的存在：http://en.wikipedia.org/wiki/Tutte_matrix

如果A（t）是一個曲線圖G（V，E）的TUTTE矩陣，則存在一個完美的如果det（A）！= 0，則匹配。您可以通過高斯消元在O（n^3）運算中找到一個行列式，在這種情況下，它將是O（| V | sqrt（| V |））。如果O（| E |）> O（| V |），這是對Edmonds的O（| E | sqrt（| V |））運行時間的改進。

來源

2014-01-21 19:48:55 gms7777

你如何到達行列式的'O（| V | sqrt（| V |））'？我會說'n = | V |'，因此即使對於密集圖，高斯消去的時間也比開花算法的運行時更差。或者我在這裏錯過了什麼？ –

哎呦。你其實是對的。我誤解了行列式的行列式（我認爲n =矩陣的總大小，而不是維數）。將更新我的答案以反映這一點 – gms7777

偶數個頂點的高效完美匹配算法？

回答

相關問題