graph-theory - 無向グラフのすべての独立したセットを生成するアルゴリズム?

Question

無向グラフのすべての独立した集合を生成するアルゴリズムが必要です。

例えば：

'Bron-Kerbosch'アルゴリズムを使用しようとしましたが、結果の解釈方法がわかりません。

入力：

A = [1 2; 1 5; 2 3; 2 5; 3 4; 4 5; 4 6]

望ましい出力:

B = [1 3 6; 1 4; 2 4; 2 6; 3 5 6]

結果をどう解釈するか？

ありがとうございました！

Answer 1

解き方がやっと分かった……。

入力：

A = [1 2; 2 3; 3 4; 4 5; 4 6]

隣接行列に変換する:

 0     1     0     0     1     0
 1     0     1     0     1     0
 0     1     0     1     0     0
 0     0     1     0     1     1
 1     1     0     1     0     0
 0     0     0     1     0     0

BK_MaxIS 出力:

 1     1     0     0     0
 0     0     1     1     0
 1     0     0     0     1
 0     1     1     0     0
 0     0     0     0     1
 1     0     0     1     1

列 j の行 i が 1 の場合、頂点 i は、列 j によってインデックス付けされた最大独立集合に参加します。

つまり、次のことを意味します。

B = [1 3 6; 1 4; 2 4; 2 6; 3 5 6]