7

すべての可能な独立集合の中から最大値を見つける力ずくの方法以外に、2部グラフで最大の独立頂点集合を見つけるためのアルゴリズムは存在しないと思います。

考えられるすべての頂点セットを見つけるための擬似コードについて疑問に思っています。

4つの青い頂点と4つの赤い頂点を持つ2部グラフが与えられたとしましょう。現在私は

Start with an arbitrary blue,
  find all red that don't match this blue
  put all these red in Independent Set
  find all blue that dont match these red
  put these blue in Independent Set
  Repeat for next vertex in blue

Repeat all over again for all blue then all vertices in red.

最初のステップの後、すべての可能性をステップスルーするのではなく、一致しない次の色の頂点をすべて選択するため、この方法ではすべての可能な独立集合の組み合わせが得られるわけではないことを理解しています。

たとえば、一致するグラフがあるとします

B  R
1  1
1  3 
2  1
2  3
3  1
3  3
4  2
4  4

Start with blue 1
  Choose red 2 and 4 since they dont match
  Add 2, 4 to independent Set
  Choose 2 and 3 from blue since they dont with 2 or 4 from red
  Add 2 and 3 from blue to independent set as well.
Independent Set = 1,2,3 from blue 2,4 from red
Repeat for blue 2, blue 3, ... red n (storing the cardinality for each set)

このアルゴリズムを改善して、すべての可能性をより適切に検索する方法はありますか？|2部グラフの最大セット| =|赤| +|青| -|最大マッチング|。

問題は、特定の青に対して最初にすべての可能な赤を選択することによって、それらの赤が他のすべての可能な青に接続する場合、私のセットにはすべて1つの青と残りの赤しか含まれない可能性があるために発生します。

4

2 に答える 2

10

すべての可能な独立集合の中から最大値を見つける力ずくの方法以外に、2部グラフで最大の独立頂点集合を見つけるためのアルゴリズムは存在しないと思います。

最大の独立集合を見つけることは（結果の補集合をとることによって）最小の頂点被覆を見つけることと同等であり、ケーニヒの定理は、2部グラフの最小頂点被覆は最大マッチングと同等であり、それは多項式で見つけることができると述べています時間。すべての一致を見つけることについてはわかりませんが、指数関数的に多くなる可能性があります。

于 2011-12-21T17:23:45.743 に答える
1

アーロン・マクデイドが削除された回答で述べているように、最大​​の独立集合を見つける問題は、最大のクリークを見つけることと同じです。同等性は、グラフGで最大独立集合を見つけることは、Gの補集合で最大クリークを見つけることと同じであるということです。問題はNP完全であることが知られています。

あなたが言及する強引な解決策はかかりますがO(n^2 2^n)、これよりもうまくいくことができます。Robsonは、1986年の「最大独立集合のアルゴリズム」というタイトルの論文を持っています。この論文はO(2^{c*n})、定数をとるアルゴリズムを示しています0<c<1（私cは周り1/4にあると思いますが、誤解される可能性があります）。これは2部グラフに固有のものではありません。

2部グラフがある場合、注意すべき点の1つは、どちらかの側が独立したセットを形成することです。K_{b,r}で分割B x Rされ|B|=b、のすべての頂点からのすべての頂点へ|R|=rのエッジがあり、内にも内にもない完全2部グラフでは、最大の独立集合はifであり、それ以外の場合はです。BRBRBb>=rR

服用するBかR、一般的には機能しません。sdcvvcは、頂点{1,2,3,A,B,C}とエッジを使用した例に注目しました{A,1}, {A,2}, {A,3}, {B,3}, {C,3}。この場合、最大の独立集合はであり、パーティションまたは{1,2,B,C}のいずれよりも大きくなります。{A,B,C}{1,2,3}

Robsonのアルゴリズムは、大きい方から開始するBかR、そこから進むように改善される可能性がありますが、これによってどの程度の違いが生じるかはわかりません。

または、グラフの2部補集合でホップクロフト・カープアルゴリズムを使用して最大一致を見つけ、一致に使用された頂点を独立集合として使用することもできます。これにより、問題を解決するための多項式時間アルゴリズムが得られます。

于 2011-12-21T18:06:14.440 に答える