按顺序计算图中所有 k 个顶点的团

Question

是否存在顺序算法来计算无向图中的所有 k-cliques？

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

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

Answer 1

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

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 时打印 clique 并减少递归，因为任何递归调用只会产生更大的 cliques。

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}

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

按顺序计算图中所有 k 个顶点的团

Counting all cliques of k vertices in a graph sequentially

algorithm

recursion

graph

clique

social-networking