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))。

我的解决方案正确吗？

标签： algorithmgraphcorrectness

Answer 1

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

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

该图是 3 边连接的，但如果您删除X，它会断开连接。