动态图算法模型

形式陈述 ​

更新协议 ​

在固定或变化的图公理库有限简单无向图Graph · Finite simple undirected graph · 图由有限顶点集与无序二元顶点子集组成的边集所确定的简单无向图。上接收边/点更新。Incremental 只插入，decremental 只删除，fully dynamic 两者皆有。在线算法必须在下一操作前回答，offline 算法可预知整段序列。

连通性展示了三者差异：只插边可用并查集；只删边若离线可逆序转为插入；全动态在线结构还要在树边删除后寻找替代边。每次查询前用静态 DFS 重算虽正确，却付出 $\mathrm{\Theta }(n+m)$ 级工作，只是动态接口的基线。

操作序列与成本坐标 ​

序列

$$+ab,+bc,?\mathrm{connected}(a,c),-bc,?\mathrm{connected}(a,c)$$

只有 fully dynamic 模型允许，两个查询依次为 true、false。Incremental 禁止删除，decremental 不能从空图执行前两次插入。Offline 算法预先知道 $bc$ 的活动区间；online 算法在第一次查询时没有这项未来信息。

若有 $u$ 次更新、$q$ 次查询，完整时间复杂度公理库时间复杂度Time complexity · Running time在固定计算模型与输入编码后，算法运行步骤数随输入规模增长的量级。账本应写成

$$P(n,m)+\sum _{i=1}^u{U}_i+\sum _{j=1}^q{Q}_j.$$

摊还更新时间控制合法操作前缀的平均工作；total update time 可能只对整个序列给界。查询很频繁时，不能把 query 工作藏入更新账。

Offline 动态连通可把每条边的活动区间放入时间 segment tree，用 rollback DSU 遍历；在线 fully dynamic 结构没有未来删除时间，两者不是同一保证。Sensitivity-$k$ 只允许至多 $k$ 次更新，也不同于无限操作序列。

直觉

动态图算法维护的不是一张最终图，而是更新与查询交错形成的状态轨迹。只知道最终边集会丢失每次查询发生时的图；能否预知整段轨迹、允许哪些更新，以及成本按单步、摊还还是整段结算，都会改变算法可利用的信息与保证。

例子与边界

随机对手 ​

Oblivious 对手在随机种子抽取前固定全部操作；adaptive 对手可依据已见答案选择下一条边。若结构公开哈希行为，自适应对手可能刻意制造碰撞，所以只对固定序列的期望界不能直接沿用。

对 oblivious 序列，可以先固定操作再对内部随机性取概率；对 adaptive 序列，量词顺序相反，往往需要重随机化或同时对所有可能查询成立的高概率事件。复杂度声明必须写明对手与概率来源。

图与更新边界 ​

每项结论要标明边更新还是点更新、图是否有向/加权、是否允许平行边，以及查询是连通、最短路还是其他性质。动态图研究离散事件后的状态，不等同于边权连续变化的数值优化。

推论与应用

该模型为动态连通、动态最小生成森林、动态最短路和动态图稀疏化提供共同的更新协议。选用具体结果时，必须把图类型、更新类型、查询接口、对手权限和概率量词逐项对齐；仅有相似的“每次更新多对数时间”不能跨模型替换。

参考资料

• Holm, de Lichtenberg, Thorup, “Poly-logarithmic Deterministic Fully-dynamic Algorithms,” JACM, 2001.
• Eppstein et al., “Sparsification,” JACM, 1997.