無向グラフ G の最小支配集合を見つけるには、貪欲なアルゴリズムを次のように使用できます。
アルゴリズムは通常、最適解を見つけません。それは ln(Delta) 近似です。(Delta が G の頂点の最大次数の場合)
今、貪欲なアルゴリズムが最適解を見つけられない簡単な例を探しています。私が見つけた唯一のものは、セット カバーの問題の関連するインスタンスです。( http://en.wikipedia.org/wiki/Set_cover_problem#Greedy_algorithm右側の画像) これをグラフに変換すると、最低でも 14 個の頂点と多数のエッジが発生します。
誰かが小さな例を知っていますか?
前もって感謝します
