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]