检查一个简单的无向图是否是三连通的
Check if a simple, undirected graph is triconnected
问题
给定一个简单的无向图G = (V, E)，其中|V| = n = 节点数和 |E| = m = 边数，检查G是否三连。也就是说，在随机删除任意两条边后，G 是否保持连通（存在从每个节点到所有其他节点的路径）。
所需时间复杂度：O(n^2(n + m))
我的解决方案
对 G 中的每个节点执行以下操作：
检查节点是否至少有3条边到3个不同的节点：O(1).
忽略节点，运行对剩余图进行深度优先搜索，检查是否仍然连通：O(n + m)
时间复杂度：O(n(n + m)) = O(n^2(n + m))。
我的解决方案正确吗？
不，考虑具有顶点 X 和 * 的图。
* *
/|\ /|\
*-+-X-+-*
\|/ \|/
* *
此图是 3 边连接的，但如果您删除 X，它会断开连接。
您通常使用最大流量检查连通性。您将容量 1 设置为每条边，选择两个节点并计算它们之间的最大流量。结果是两个节点之间完全不同的路径数（不同，因为没有共享边）。
为了确保整个图是 3 连接的意味着您需要选择每对节点并计算它们之间的最大流量。
Ford–Fulkerson 算法的最大流量复杂度为 O(m * max(f))，其中 max(f) 是最大流量。然而，由于该算法希望在每一步都增加流量，我们可以在流量 == 3 时立即停止（我们不关心是否有更多路径）。所以这使得复杂度为 O(m).
因为你对每一对节点都这样做，所以你得到了 O(n^2 * m) 的复杂度。由于 V <= E（尤其是在您进行快速边数检查之后）O(n+m) = O(m) 所以它的复杂性与所需的相同。
问题
给定一个简单的无向图G = (V, E)，其中|V| = n = 节点数和 |E| = m = 边数，检查G是否三连。也就是说，在随机删除任意两条边后，G 是否保持连通（存在从每个节点到所有其他节点的路径）。 所需时间复杂度：O(n^2(n + m))
我的解决方案
对 G 中的每个节点执行以下操作：
检查节点是否至少有3条边到3个不同的节点：O(1).
忽略节点，运行对剩余图进行深度优先搜索，检查是否仍然连通：O(n + m)
时间复杂度：O(n(n + m)) = O(n^2(n + m))。
我的解决方案正确吗？
不，考虑具有顶点 X 和 * 的图。
* *
/|\ /|\
*-+-X-+-*
\|/ \|/
* *
此图是 3 边连接的，但如果您删除 X，它会断开连接。
您通常使用最大流量检查连通性。您将容量 1 设置为每条边，选择两个节点并计算它们之间的最大流量。结果是两个节点之间完全不同的路径数（不同，因为没有共享边）。 为了确保整个图是 3 连接的意味着您需要选择每对节点并计算它们之间的最大流量。
Ford–Fulkerson 算法的最大流量复杂度为 O(m * max(f))，其中 max(f) 是最大流量。然而，由于该算法希望在每一步都增加流量，我们可以在流量 == 3 时立即停止（我们不关心是否有更多路径）。所以这使得复杂度为 O(m).
因为你对每一对节点都这样做，所以你得到了 O(n^2 * m) 的复杂度。由于 V <= E（尤其是在您进行快速边数检查之后）O(n+m) = O(m) 所以它的复杂性与所需的相同。