algorithm - 依次计算图中所有 k 个顶点的团

Question

是否存在用于计算无向图中所有k 团的顺序算法？

对于 k-cliques，我的意思是：在无向图中通过边相互连接的顶点集的数量。

在这里可以找到更详细的集团描述。https://en.wikipedia.org/wiki/Clique_(graph_theory)

Answer 1

您可以使用Bron–Kerbosch 算法列出图中的所有派系。考虑它最简单的实现（来自维基百科的伪代码）：

BronKerbosch1(R, P, X):
    if P and X are both empty:
        report R as a maximal clique
    for each vertex v in P:
        BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
        P := P \ {v}
        X := X ⋃ {v}

在每个递归调用中，集合R包含一个团，同时遍历图中的所有团。因此，您可以更改算法以在其大小为时打印团k并减少递归，因为任何递归调用只会产生更大的团。

BronKerbosch1(R, P, X, k):
    if |R| = k:
        report R as a k-clique
    else
        for each vertex v in P:
            BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
            P := P \ {v}
            X := X ⋃ {v}

在实现具有旋转和顶点排序的优化版本时，您可以使用相同的想法。