检查一个简单的无向图是否是三联的

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-+-*
|/ |/
*   *

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

Answer 2

您通常使用最大流量检查连接。将每个边的电容设置为 1，选择两个节点并计算它们之间的最大流量。结果是两个节点之间完全不同的路径数量(与无共享边不同(。 为了确保整个图形是 3 个连接的，这意味着您需要选择每对节点并计算它们之间的最大流量。

福特-富尔克森算法的最大流量复杂度为 O(m * max(f((，其中 max(f( 是最大流量。但是，由于该算法希望在每一步都增加流量，因此我们可以在流量 == 3 时立即停止(我们不在乎是否有更多路径(。因此，这使得复杂性为O(m(。

由于你对每对节点都这样做，所以你会得到O(n^2 * m(的复杂度。由于 V <= E(尤其是在您进行快速边沿计数检查之后(O(n+m( = O(m(，因此它与所需的复杂性相同。