最小頂點覆蓋使用會合的中間人

Question

我學習會合的中間人算法，發現下面的練習：

給定n個節點的圖形（N < = 30），找出具有最少數量的頂點的集合，使得圖中的每個邊在該集內至少有一個節點。

我不知道該怎麼做，只是暗示我是

複雜度爲O（3 ^（N/2））

可以嗎解釋這個想法？

Answer 1

從圖中取出邊緣(u1, v1)，刪除與它共享頂點的所有邊。取出另一個(u2, v2)，...繼續，直到圖的其餘部分沒有邊。

你結束了一個多對頂點

(u1, v1), (u2, v2), ..., (uk, vk) 

頂點其餘的是：

w1, w2, ..., wm 

呼叫第一組頂點配對頂點，而第二組不成對的頂點。請注意，2k + m = n，原始圖形中不成對頂點之間沒有邊。

頂點覆蓋物必須包含其中的u1,v1或both。每對(uj, vj)有3種選擇。考慮所有的3^k方法將成對的頂點包含到頂點封面。

對於每個這些配置的，未配對的頂點wi將被包括到蓋當且僅當其近鄰中的至少一個不是在蓋（請注意，各wi的鄰居的被配對的頂點，所以是否他們被包括在內是已知的）。

對於每個成對頂點的3^k選擇的，包括根據上述標準的不成對的頂點，然後驗證配對的頂點之間的每個邊緣具有從蓋的入射頂點，如果是的話，它是一種候選蓋設置 。以最小尺寸的候選覆蓋集作爲輸出。

上述算法的整體複雜度爲O(3^(n/2)E)，其中E是圖中邊緣的數量。