支配集貪婪近似最壞情況示例

Question

要找到無向圖G的最小支配集，您可以使用如下的貪婪算法： 以空集D開始。在D爲支配集之前，添加一個頂點v最大數量的未被覆蓋的鄰居。

該算法一般不會找到最優解，它是一個ln（Delta）近似。 （如果Delta是G中頂點的最大度數）

現在我正在尋找一個貪婪算法找不到最優解的簡單示例。我發現的唯一一個是集封面問題的相關實例。 （http://en.wikipedia.org/wiki/Set_cover_problem#Greedy_algorithm圖片在右邊） 將這一個翻譯成圖形將導致最少14個頂點和很多邊緣。

有沒有人知道一個小例子？

預先感謝

Answer 1

考慮以下圖：

貪婪方法將選擇B，則d和G.同時，E和F形成支配集。