1

無向グラフの最大セットを見つけようとしていますが、そのために使用しているアルゴリズムは次のとおりです。

1) エッジの数が最小のノードを選択します 2) その隣接ノードをすべて削除します 3) 残りのノードから、エッジの数が最小のノードを選択します 4) グラフ全体がカバーされるまで手順を繰り返します

これが正しいかどうか誰か教えてもらえますか？そうでない場合、グラフ内の最大独立集合を計算するこの方法が間違っているのはなぜですか?

4

3 に答える 3

2

あなたが説明したことは、最大の独立したセットを選択します。これは次のように確認できます。

  1. これにより、独立したセットが生成されます。矛盾して、そうではなかったと仮定します。次に、作成したセットに追加されたエッジによって接続された 2 つのノードが必要になります。それらのいずれかが最初に選択されたものを取ります (それを u と呼び、もう一方を v とします) 次に、それがセットに追加されると、ノード v を含むすべての隣接ノードがセットから削除されます。がセットに追加され、矛盾が生じています。

  2. これにより、最大独立集合が生成されます。矛盾して、そうではなかったと仮定します。これは、アルゴリズムによって生成された独立集合に追加できるが、追加されなかったノード v があることを意味します。このノードは追加されていないため、アルゴリズムによってグラフから削除されたに違いありません。これは、すでにセットに追加されているノードに隣接している必要があることを意味します。しかし、これは不可能です。なぜなら、ノード v を生成された独立集合に追加するには、結果を独立集合でなくする必要があるからです。矛盾があります。

お役に立てれば！

于 2013-02-08T01:53:46.540 に答える
0

どのグラフにも明確な最大独立集合はありません。たとえば、3 つのノードにわたるサイクルを考えると、各ノードは最大の独立したセットを形成します。アルゴリズムは、最大のカーディナリティを持つことを保証せずに、グラフの最大の独立したセットの 1 つを提供します。

一方、グラフ内の最大独立集合を見つけることは NP 完全であるため (その問題は最大クリークを見つける問題を補完するため)、おそらく効率的なアルゴリズムはありません。

于 2013-02-08T01:51:24.307 に答える
0

コメントで状況を明確にした後、あなたの解決策は正しいです。さらに良いことに、この論文http://courses.engr.illinois.edu/cs598csc/sp2011/Lectures/lecture_7.pdfの系 3 によれば、サブセットの順序を 適切に近似 できます。Greedy gives a 1 / (d + 1) -approximation for (unweighted) MIS in graphs of degree at most d

于 2013-02-08T02:00:53.283 に答える