7

グラフGが与えられた場合、Gの最大独立集合を見つけることが保証されていない欲張りアルゴリズムに従うのはなぜですか。

Greedy(G):
S = {}
While G is not empty:
    Let v be a node with minimum degree in G
    S = union(S, {v})
    remove v and its neighbors from G
return S

このアルゴリズムが失敗するグラフの簡単な例を誰かに見せてもらえますか？

4

1 に答える 1

9

これが最も簡単な例かどうかはわかりませんが、失敗した例は次のとおりです：http: //imgur.com/QK3DC

最初のステップでは、B、C、D、またはFを選択できます。これらはすべて次数2であるため、Bとその隣接ノードを削除するとします。これにより、FとDは次数1になり、Eは次数2になります。次の2つの手順で、FとDを削除し、最大の設定サイズ3になります。

代わりに、最初のステップでCとその隣接ノードを削除したとします。これにより、F、A、およびEが残り、それぞれ次数のサイズは2になります。次にこれらのいずれかを取得すると、グラフは空になり、ソリューションには2つのノードしか含まれません。これは、これまで見てきたように、最大​​ではありません。 。

于 2012-12-17T20:55:29.820 に答える