algorithm - 向图中添加随机边时，哪些桥边不再是桥边？

Question

随机边 e 被添加到图中。它恰好不是桥边。设 C 是 e 端点的连通分量。

给定 C 的所有桥边的列表 L(在添加 e 之前)，这是找到哪个桥的最快算法L 中的边在插入 e 后仍然是桥边？

Answer 1

如果允许预处理，有一个快速的方法:构造bridge-block forest ，其顶点是 2-连通分量，其边是桥。 (如果图是连通的，它就是一棵树。)当你添加一条边时，如果它连接了同一个 2-连通分量中的点，则什么也不会发生。如果您连接位于桥 block 森林的不同连接组件中的不同 2-连接组件中的点，则新边是一座桥(您假设不会发生)。如果将两个 2-connected 组件连接在同一个连接组件中，则找到这些 2-connected 组件之间桥接的唯一路径。这些不再是桥梁，并且路径上的所有 2-connected 组件都收缩到一个新的 2-connected 组件。任何不沿着这条路径的桥仍然是桥。

有评论说你最多消除一座桥。这是不正确的。您可以连接桥 block 森林中的任意两点，包括任意距离的点。添加这样一条边会消除任意多条边。

在您的评论中，您提到删除边缘。这可能什么都不做，但是如果你删除一个非桥接的 e，它可能会导致包含 e 的 2-connected 组件 C 进入任意长的路径，因此你需要重新计算 C 中的 2-connected 组件并将 C 替换为这条 2-连通分量的路径。将 C 连接到其他 2-连通分量的桥成为将新的 2-连通分量 C_!, ..., C_k 连接到 C 的邻居的桥。