求无向图中最大团的BronKerbosch算法

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}

Answer 1

1. 在选择轴的时间和探索结果树的时间之间有一个折衷。假设我们可以构建一个甲骨文来为我们提供最佳的枢轴选择，但它可能需要比Bron Kerbosch本身更多的执行时间。相反，选择第一个顶点的速度非常快，但可能会导致生成比需要大得多的树

   鉴于不可能达到完美，良好的分支策略一直是学术界感兴趣的话题。首先发现的策略之一是选择支点以最小化分支的数量。这往往比所有简单的策略都更有效。这意味着最小化P的大小∖ N（u），最大化N（u）的大小似乎是一个不错的代理

2. 基本上，是的。在不旋转的情况下，即使我们在N（u）中选择一个顶点，我们仍然可以在最后找到一个最大团。我们的想法是，每个最大团都包含u或一个既不是u也不是u的邻居的顶点，因此我们很早就确定了该顶点的身份（这与将强制决策移向搜索树根的理念一致）