全动态连通性

形式陈述 ​

在线模型与选定保证 ​

在全动态图算法模型理路动态图算法模型Dynamic graph algorithm model统一图更新序列、查询接口、对手权限以及更新和查询保证。中维护固定顶点集 $V$ 上的无向简单图，从空边集开始，记 $n=|V|\ge 2$，并持续回答图连通性理路图连通性Graph connectivity用顶点间是否存在路径定义无向图的连通性，并由此划分连通分量。查询。更新为 insert$(e)$ 或 delete$(e)$，查询 connected$(u,v)$ 必须在看不到未来操作的在线条件下立即回答。以下讲 Holm–de Lichtenberg–Thorup（HDT）确定性框架的一个标准实现：

其中 $m$ 是当前边数。这里显式为每个顶点建立各层的 Euler Tour Tree理路Euler Tour TreeEuler tour tree · ET-tree · 动态 Euler Tour Tree将无向树的 Euler 环游维护为可 split、join 的平衡序列，以支持动态森林的换根、连边、断边、连通性和分量聚合。记录，并选用支持最坏对数时间 split/join 的确定性平衡序列；$O(\log n)$ 份重叠森林产生了 $n\log n$ 的空间项。零或单顶点图可直接处理合法的平凡查询，不需要分层结构。已有非空初始图时，可逐边插入，并将相应成本计入预处理。原论文与后续实现可进一步改善查询或常数；这里固定上述版本，不把 connectivity、动态最小生成树和二边连通的不同界拼在一起。

删除树边为何困难 ​

只插边时，并查集可合并分量；删除一条非树边也不改变现有生成森林。困难发生在删除生成树边 $e$：森林立刻裂成 $A,B$ 两棵树，但原图是否断开取决于所有非树边中是否存在一条跨越割 $(A,B)$ 的 replacement edge。

从头扫描全部边能找到 replacement，却可能每次花 $\mathrm{\Theta }(m)$。HDT 的目标不是消除搜索，而是保证同一条失败候选只会在有限多个层级被重新扫描。

层级与森林不变量 ​

每条边 $e$ 有层级

令 $G_i$ 含所有层级至少 $i$ 的边。维护生成森林 $F_0$，并令 $F_i$ 恰由 $F_0$ 中层级至少 $i$ 的树边组成；要求每个 $F_i$ 都生成 $G_i$ 的各个连通分量，且

关键大小不变量是：$F_i$ 的每个连通分量至多含 $n/2^i$ 个顶点。新边从 level $0$ 开始。每个顶点把非树边按其精确层级存入邻接袋。在第 $i$ 层 ETT 中，额外保存分量大小、是否含 level-$i$ 树边，以及是否有顶点关联 level-$i$ 非树边的摘要。沿这些标记寻找下一条候选，每找到或移走一条只需 $O(\log n)$；空摘要允许跳过整段无候选区域，避免在每次删除中重扫全部顶点。

插入 $(u,v)$ 时，若 $u,v$ 在 $F_0$ 中不连通，就把边作为 level-0 tree edge 加入相应森林；否则记为 level-0 non-tree edge。删除 non-tree edge 只需从其边集合移除。

replacement 搜索与提升 ​

删除层级为 $i$ 的树边后，先在所有 $F_j$（$j\le i$）中 cut 这条边，再从层级 $i$ 逐层向下搜索。在当前层级 $h$，取删除端点在 $F_h$ 中所在的两棵树，选较小者 $A$。操作次序如下。

1. 先提升树边。 将 $A$ 内恰为 level-$h$ 的树边提升到 $h+1$，并加入 $F_{h+1}$。更高层树边原本已在其中，所以此后整个 $A$ 在 $F_{h+1}$ 中连通。
2. 再扫描非树边。 枚举与 $A$ 相邻的 level-$h$ 非树边。若另一端也在 $A$，将它提升到 $h+1$；第一步已经保证其两端在 $F_{h+1}$ 中连通，生成森林不变量得以保持。
3. 找到跨边即修复。 若候选边跨到另一侧，将它转为 level-$h$ 树边，并在所有 $F_j$（$j\le h$）中 link，两侧重新连通，搜索结束。
4. 本层耗尽才降层。 若没有跨边，继续处理 $h-1$；层级零也耗尽时，原图确实分裂成两个分量。

删除前，包含两侧的第 $h$ 层分量至多有 $n/2^h$ 个顶点，所以较小侧至多有 $n/2^{h+1}$ 个。将其树边提升，正好符合下一层的大小界。层级 $L$ 的分量只能是单点，没有可再提升的非自环边。

第一步必须在扫描非树边之前完成，而不是只在“本层没找到替代边”时执行。否则内部非树边先进入 $G_{h+1}$，其两端却可能还未在 $F_{h+1}$ 中连通；随后若找到跨边并提前结束，这个不变量就没有机会恢复。记录边层级、各层树边副本和精确层级邻接袋时，也必须同步更新。

摊还分析 ​

边的层级只增不减，最多从 $0$ 提升到 $L$，所以每条边一生至多被成功提升 $O(\log n)$ 次。每次提升只更新一个新增森林层或两个端点的邻接袋，花 $O(\log n)$；未被提升的成功替代边每次删除至多一条。把失败扫描及树边提升成本记到被提升的边，全部更新上的总提升成本为

其中 $m_{\mathrm{life}}$ 按插入次数计数：同一端点对删除后重新插入，开始新的边生命周期。删除和最终替代还需在至多 $O(\log n)$ 层各做常数次森林操作，总代价 $O({\log }^{2}n)$；每层空候选检查只需 $O(\log n)$。从空边集开始，把这些成本对整段更新求和，即得到 $O({\log }^{2}n)$ 的摊还更新界。

这不是单次最坏界：一次不幸的 tree-edge 删除可能检查许多候选，成本由那些候选以后不再停留在同一层这一事实偿还。若实现允许边层级下降，上述记账立即失效。