动态图算法模型

更新协议 ​

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

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

操作序列与成本坐标 ​

序列 [ +ab,+bc,\ ?\operatorname{connected}(a,c),\ -bc,\ ?\operatorname{connected}(a,c) ] 只有 fully dynamic 模型允许，两个查询依次为 true、false。Incremental 禁止删除，decremental 不能从空图执行前两次插入。Offline 算法预先知道 (bc) 的活动区间；online 算法在第一次查询时没有这项未来信息。

若有 (u) 次更新、(q) 次查询，完整成本应写成 [ 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.