python - 在无向图中寻找最大团的 Bron-Kerbosch 算法

Question

我正在尝试理解 Bron-Kerbosch 的算法(带旋转)以在无向图。我有一些问题:

1. 选择枢轴顶点有什么标准吗？我已经看到一些实现选择具有最多邻居的顶点进行优化，而其他实现则简单地选择预期顶点中的第一个顶点作为枢轴顶点。选择具有最多邻居的顶点如何帮助优化？

2. 通过选择一个枢轴顶点，它有助于缩小在搜索 cliques 期间要检查的预期顶点列表，从而减少递归调用的次数。没有旋转的算法检查所有顶点以确定它是否形成一个团，而有旋转的算法只检查 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. 在选择枢轴所花费的时间与探索结果树所花费的时间之间存在权衡。假设我们可以构建一个 oracle 来为我们提供最佳的枢轴选择，但它可能会比 Bron--Kerbosch 本身花费更多的执行时间。相反，选择第一个顶点非常快，但可能会导致树比所需的大得多。

   鉴于不可能达到完美，良好的分支策略是学术界长期关注的话题。最早发现的策略之一是选择枢轴以最小化分支数量。这往往比所有更简单的策略都更有效。这意味着最小化 P ∖ N(u) 的大小，为此最大化 N(u) 的大小似乎是一个不错的代理。

2. 基本上，是的。没有旋转，即使我们在 N(u) 中选择一个顶点，我们仍然可以在最后找到一个最大的团。这个想法是每个最大集团都包含 u 或既不是 u 也不是 u 的邻居之一的顶点，因此我们尽早 promise 该顶点的身份(符合将强制决策移向搜索树根的哲学) .