如何測試樹在線性時間內是否具有完美匹配？

Question

給出一個線性時間算法來測試一棵樹是否有完美匹配，即一組觸摸樹中每個垂直文本的邊緣。

這是從算法由S. Dasgupta，我似乎無法指出這個問題。我知道我需要以某種方式使用貪婪的方法，但我無法弄清楚這一點。幫幫我？

僞代碼很好;一旦我有了這個想法，我可以用任何語言輕鬆地實現。

該算法必須是線性的任何事情。 O（V + E）很好。

Answer 1

我想我有解決方案。由於我們知道該圖是樹，因此我們知道葉子節點的存在，具有一個邊緣且沒有子節點的節點。爲了將此節點包含在完美匹配中，該邊必須存在於最終解決方案中。

Ergo，我們可以找到連接到葉節點的所有邊，添加到解決方案，並從圖中刪除觸摸的邊。如果在這個過程結束時，我們留下的任何剩餘的節點都沒有涉及，那麼就不存在完美的匹配。

Answer 2

線性什麼？線性中的邊緣的數目，保持邊緣爲有序列表發生率，即每邊（v _我，v _Ĵ）在一些總次序。然後你可以比較兩個邊的O（n）。

Answer 3

我認爲這是在圖上確定漢彌爾頓路徑的簡單問題：通常發現漢密爾頓週期 http://en.wikipedia.org/wiki/Hamiltonian_path

http://en.wikipedia.org/wiki/Hamiltonian_path_problem

我認爲有互聯網上的許多解決這一問題，但是NP問題。

Answer 4

在「圖形」的情況下， 問題的第一步應該是找到連接的組件。

由於最終答案中的每條邊連接兩個頂點，它們最多隻屬於一個連接的組件。

然後，可以找到每個連接組件的完美匹配。