生成一個無向圖的所有獨立集合的算法？

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 

凡行i列j的爲1，I參與的最大獨立集的頂點索引在第j列。

這意味着：

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