Bron-Kerbosch算法用于在无向图中查找最大团。

Question

我正在尝试理解Bron-Kerbosch算法（带有枢轴）在无向图中查找最大团的方法。 我有一些问题：

1. 选择枢轴顶点是否有任何标准？ 我已经看到了一些实现，选择具有最多邻居的顶点进行优化，而其他人则只是选择前面的候选顶点作为枢轴顶点。 选择具有最多邻居的顶点如何帮助优化？

2. 通过选择枢轴顶点，在搜索团时有助于缩小要检查的候选顶点列表，从而减少递归调用的数量。没有枢轴的算法检查所有顶点以确定它们是否形成一个团，而具有枢轴的算法仅检查必须包括以形成最大团的顶点的P \ N（u）。 这样，如果发现非最大团，则算法可以立即回溯，而不是在永远不会形成最大团的顶点上不必要地执行递归。我的理解正确吗？

来自Wikipedia的伪代码：

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

*With Pivoting
algorithm BronKerbosch2(R, P, X) is
    if P and X are both empty then
        report R as a maximal clique
    choose a pivot vertex u in P ⋃ X
    for each vertex v in P \ N(u) do
        BronKerbosch2(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
        P := P \ {v}
        X := X ⋃ {v}

- tan

Answer 1

1. 在选择枢轴的时间和探索结果树的时间之间存在权衡。理论上，我们可以构建一个神谕来给我们提供最好的枢轴选择，但它可能需要比Bron-Kerbosch本身更长的执行时间。相反，选择第一个顶点非常快，但可能会导致比必要更大的树。

   优秀的分支策略是学术界一直关注的话题，因为无法达到完美。最早发现的策略之一是选择枢轴以最小化分支数。这比所有更简单的策略都要好。在这里，这意味着最小化P∖N(u)的大小，其中最大化N(u)的大小似乎是一个不错的代理。

2. 基本上是的。如果没有枢轴，即使我们选择了N(u)中的一个顶点，我们仍然可以在最后找到最大的团。思想是每个最大团都包括u或者一个既不是u也不是u的邻居的顶点，因此我们要尽早确定该顶点的身份（符合将强制决策移向搜索树根部的哲学）。

- David Eisenstat