algorithm - 检查一个简单的无向图是否是三连通的

Question

问题

给定一个简单的无向图 G = (V, E)，其中 |V| = n = 节点数和 |E| = m = 边数，检查G是否三连。也就是说，在随机删除任意两条边后，G 是否保持连通(存在从每个节点到所有其他节点的路径)。所需时间复杂度:O(n^2(n + m))

我的解决方案

对于 G 中的每个节点，执行以下操作:

1. 检查节点是否至少有 3 条边到 3 个不同的节点:O(1)。

2. 忽略节点并对剩余的图运行深度优先搜索以检查它是否仍然连接:O(n + m)

时间复杂度:O(n(n + m)) = O(n^2(n + m))。

我的解决方案是否正确？

Answer 1

不，考虑具有顶点 X 和 * 的图。

  *   *
 /|\ /|\
*-+-X-+-*
 \|/ \|/
  *   *

这个图是三边连通的，但是如果你删除 X，它就会断开连接。