“在全动态图算法模型中维护固定顶点集 $V$ 上的无向简单图，从空边集开始，记 $n= V \ge2$，并持续回答图连通性查询。更新为 insert$(e)$ 或 delete$(e)$，查询…”
形式陈述
更新协议
先固定状态类型和合法更新：基础情形是有限简单无向图，也可以明确扩展为带权、有向或带独立边身份的多重图；顶点集是否固定同样属于输入协议。算法在这种状态上接收边或点更新。Incremental 只插入，decremental 只删除，fully dynamic 两者皆有。在线算法必须在下一操作前回答，offline 算法可预知整段序列。
连通性展示了三者差异：只插边可用并查集；只删边若离线可逆序转为插入；全动态在线结构还要在树边删除后寻找替代边。每次查询前用完整静态 DFS 重新标记全部连通分量虽正确，却付出
操作序列与成本坐标
序列
只有 fully dynamic 模型允许，两个查询依次为 true、false。Incremental 禁止删除，decremental 不能从空图执行前两次插入。Offline 算法预先知道
若有
摊还更新时间控制合法操作前缀的平均工作；total update time 可能只对整个序列给界。查询很频繁时，不能把 query 工作藏入更新账。
Offline 动态连通可把每条边的活动区间放入时间 segment tree，用 rollback DSU 遍历；在线 fully dynamic 结构没有未来删除时间，两者不是同一保证。Sensitivity-
直觉
动态图算法维护的不是一张最终图，而是更新与查询交错形成的状态轨迹。只知道最终边集会丢失每次查询发生时的图；能否预知整段轨迹、允许哪些更新，以及成本按单步、摊还还是整段结算，都会改变算法可利用的信息与保证。
例子与边界
随机对手
Oblivious 对手在随机种子抽取前固定全部操作；adaptive 对手可依据已见答案选择下一条边。若结构公开哈希行为，自适应对手可能刻意制造碰撞，所以只对固定序列的期望界不能直接沿用。
对 oblivious 对手，操作序列独立于结构的随机种子，可以先固定整段序列再取期望。对 adaptive 对手，应先固定一套根据已见信息选择下一操作的策略，再对结构和策略的随机性分析；产生的操作序列可能与内部状态相关。这不是简单交换两个量词。保证必须声明对手能观察答案、运行时间还是内部随机位，并证明在这份观察权限下，每个新选择之后所用的概率条件仍成立。
图与更新边界
每项结论要标明边更新还是点更新、图是否有向/加权、是否允许平行边，以及查询是连通、最短路还是其他性质。动态图研究离散事件后的状态，不等同于边权连续变化的数值优化。
推论与应用
该模型为动态连通、动态最小生成森林、动态最短路和动态图稀疏化提供共同的更新协议。选用具体结果时，必须把图类型、更新类型、查询接口、对手权限和概率量词逐项对齐；仅有相似的“每次更新多对数时间”不能跨模型替换。
OMv到有向可达的归约固定矩阵弧，只通过源边插删表示当前向量，再逐行查询。小块重组显式支付每份结构的多项式预处理及合并费用，给出更新与查询不能同时真次线性的条件下界；结论仍须保留全动态、有向、在线和概率接口。
参考资料
- Holm, de Lichtenberg, Thorup, “Poly-logarithmic Deterministic Fully-dynamic Algorithms,” JACM, 2001.
- Eppstein et al., “Sparsification,” JACM, 1997.