algorithm - 以最有效的方式检查无向图中的 3 个给定顶点是否属于一个循环

Question

是否可以执行某种预处理以高效(快速)地回答问题？

图是连通的，无向的，没有自环，也没有平行边(一个环至少由3个节点组成)。

请注意，这是一个是/否查询，意味着我只需要知道这样的循环是否存在，哪个并不重要。

编辑:到目前为止我的进展(基于 Nursultan 提示)和我阻止的地方:

我通过连接点将图表分成子组件，然后将它们最初分离的每个子组件中的连接点加倍。这来自以下观察:3 个给定的顶点可能属于一个循环当且仅当它们都属于没有关节点的组件。我还没有证明这一点，但我想不出一个反例。

假设上面的观察是正确的(这似乎很有可能)，现在的问题是查询中给定的 3 个顶点可能都是关节点，在这种情况下它们都属于几个组件，在最坏的情况下可能导致缓慢的 O(n) 查询时间复杂度。

另一个似乎有助于解决所描述的最坏情况的观察是:最多有 1 个子图，2 个给定的关节点可能同时属于该子图(如果需要，我可以证明这一点)，观察很容易导致最坏情况的预处理空间和时间为 O(n^2)(n 是顶点数)，与恒定时间查询相比，但是 O(n^2) 预处理时间太慢(O(n^2) 空间也太贪心了)。可以改进预处理吗？权衡一下 log(n) 查询时间开销就可以了。

Answer 1

让我们把你的图分成几个子图，它们具有这个属性:

Every vertice in each subgraph belongs to some cycle and using this cycle you can travel to any vertice from this subgraph.

所以你可以通过检查三个顶点是否属于某个子图来检查它们是否属于一个循环。它可以在 O(log V) 中完成

那么我们如何划分这样的图呢？

1. 将您的图划分为子图 (http://www.geeksforgeeks.org/bridge-in-a-graph/)
2. 移除所有被认为是桥的边
3. 现在您有几个组件。属于同一个组件的每个顶点，插入同一个集合。

注意:正如@ALTN 提到的，这不是正确的解决方案。因此，也许您还必须在关节点中划分每个子​​图。 http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/