點覆蓋

習題預習

1. 給定一個圖形，找出最小的點集合，使得圖形中的每一條邊都至少經過其中一個點。

2. 在一個無向圖中，找到包含所有奇數度數節點的最小點集合。

3. 在一個有權重的無向圖中，找到一個點集合，其權重之和最小，使得每一條邊都至少經過其中一個點。

4. 在一個有向圖中，找到一個點集合，使得每一條邊的起始點或終止點都被包含，且點的數量最小。

5. 在一個二分圖中，找到一個點集合，使得每一條邊都至少經過其中一個點，且點的數量最小。

說明知識

Vertex Cover是一種圖論中的問題，目的是找到一個最小的集合，可以覆蓋一張無向圖中所有的邊。換句話說，就是找到一些點，讓這些點所相連的邊涵蓋了整個圖。

例如，下圖中，有一個六個節點的無向圖，其中的所有邊都用虛線標記。如果要找到一個Vertex Cover，可以選擇以下三個點：1、3和5。這三個點所連接的邊（用實線表示）可以涵蓋整個圖中的所有邊。

在這個例子中，這個Vertex Cover的大小為3，因為我們只需要三個節點就可以完全涵蓋整個圖了。Vertex Cover問題是一個NP完全問題，因此通常需要使用近似算法進行求解。

彙總重點

1. Vertex Cover是一種圖論問題，旨在找到最小的點集，使得該點集中的所有點都至少與一條邊相鄰。

2. Vertex Cover對於許多現實問題都有應用，例如電路板佈線、城市交通網絡設計等。

3. Vertex Cover問題屬於NP完全問題，很難在多項式時間內找到最優解。

4. Vertex Cover問題有許多求解方法，包括暴力枚舉、貪心算法、近似算法和各種精確算法。

5. 對於一個無向圖G=(V,E)，其中V表示所有的頂點集合，E表示所有的邊集合，一個點集C是V的一個子集，如果對於任意的(u,v)∈E，都有u∈C或v∈C，那麼C稱為G的一個點覆蓋。

6. Vertex Cover問題的最小值可以用最小割問題轉化求解。

7. 在實際應用中，Vertex Cover問題有時會被轉化為其他問題求解，例如整數線性規劃和布爾滿足性問題。

8. Vertex Cover問題在計算機科學理論、算法和複雜性理論中都有廣泛的應用，是研究和設計高效算法的重要題材之一。

知識測驗

1. 假設你有一個無向圖，每個節點都有一個權重。你的目標是找到一個最小的vertex cover，使得這些節點的權重總和最大。求最大權重總和。

答案：使用動態規劃，令MCV(i)為圖的前i個節點的最小vertex cover大小，W(i)為第i個節點的權重。則MCV(i)可表示為以下兩種情況的較小值：

1. 第i個節點被選中，那麼前i-2個節點就一定要成為vertex cover，所以MCV(i-2) + W(i)。

2. 第i個節點沒有被選中，那麼前i-1個節點就一定要成為vertex cover，所以MCV(i-1)。

3. 給定一個圖，你需要從其中去掉k個節點，使得剩下的子圖是一個獨立集。求k的最小值。

答案：該問題等價於在原圖上求最小vertex cover。可以用二分圖匹配求解。

3. 給定一個無向圖，每條邊都有一個權重。求一個最小的vertex cover，使得所有邊都至少有一個端點在vertex cover中。

答案：最小無權二分圖匹配問題的變形，可以使用Konig定理轉化為最大權二分圖匹配問題。

4. 給定一個無向圖，圖中每個節點有顏色。求一個最小的vertex cover，使得每種顏色的節點至少有一個端點在vertex cover中。

答案：給每種顏色分別做出一個子圖，然後對每個子圖求一個最小完美匹配，最後將所有匹配的端點集合合併即可得到最小vertex cover。

5. 給定一個無向圖，每個節點有一個預算和一個收入。你需要選擇一個vertex cover，使得所有選中的節點的總預算不超過收入總和，並且收入總和最大。求最大收入。

答案：可以將問題轉化為線性規劃求解，令x_i為節點i是否被選中，則目標函數為max{c_ix_i}，約束條件為∑{b_ix_i}<=∑{b_i}，x_i∈{0,1}。使用整數規劃技巧將x_i限制為整數，然後使用線性規劃求解即可。