邻接表与有界度模型：从 \(\sqrt{nm}\) 生成树到 \(n^{1/3}\) 性质测试

邻接矩阵把任意非边查询也计为一次；邻接表 oracle 则直接返回某顶点的第 \(i\) 个邻居。对稀疏图，这会从根本上改变复杂度：MST 可达 \(\Theta(\sqrt{nm})\)，exact connectivity 可达 \(\Theta(n)\)；若只测试图是否远离二分图或扩展图，在有界度模型中量子查询甚至可降到 \(O(n^{1/3})\)。

1. Array / adjacency-list oracle

设图有 \(n\) 顶点、\(m\) 条无向边。Oracle 接收

\[ (v,i),\qquad1\le i\le d_v, \]

返回第 \(i\) 个邻居及可选边权：

\[ O_L|v,i,0\rangle =|v,i,\operatorname{nbr}(v,i)\rangle. \]

数组总槽位 \(\sum_vd_v=2m\)。通常还给 degree oracle 或用特殊空标记补齐。相同边在两个端点列表出现，算法必须处理重复。

有界度模型进一步承诺 \(d_v\le d=O(1)\)，输入规模 \(O(dn)\)。性质测试中的“\(\epsilon\)-far”表示至少修改 \(\epsilon dn\) 个邻接槽才能获得目标性质。

2. Borůvka 的 \(\sqrt{nm}\) MST 分析

当前分量 \(C\) 的邻接槽总数

\[ D(C)=\sum_{v\in C}d_v. \]

在这些槽中用 quantum minimum finding 寻找最轻出边，成本

\[ O(\sqrt{D(C)}). \]

若一轮有 \(c\) 个分量，Cauchy--Schwarz：

\[ \sum_C\sqrt{D(C)} \le\sqrt{c\sum_CD(C)} =\sqrt{2mc}. \]

Borůvka 每轮让 \(c\) 至少减半，从 \(c=n\) 求和得到

\[ \sum_tO(\sqrt{mn/2^t}) =O(\sqrt{mn}). \]

相应 lower bound 也为 \(\Omega(\sqrt{nm})\)，所以 array 模型下最优。稀疏 \(m=O(n)\) 时变成 \(\Theta(n)\)；dense \(m=\Theta(n^2)\) 时回到 \(n^{3/2}\)，与邻接矩阵一致。

3. 为什么无权 connectivity 可进一步精炼

若只需判断连通，不必比较边权。算法维护生成森林，对每个活跃分量在其邻接槽中 Grover 搜索一条出边；找到后合并。通过把成功搜索成本记到新加入的顶点/分量规模，并让失败搜索只在分量尺度翻倍时发生，可把重复扫描 amortize 到

\[ \Theta(n) \]

查询，而不是机械套用所有加权 minimum。该界在 array 模型匹配 lower bound。

这不表示可以输出所有 \(m\) 条边；算法只需 \(n-1\) 条生成树边。若任务要求列出全图，输出规模仍为 \(\Omega(m)\)。

4. Property testing 与 exact decision 的区别

Exact bipartiteness 必须发现哪怕一个隐藏奇环；property tester 只承诺：

  • 图是二分图；或

  • 至少修改 \(\epsilon dn\) 个槽才能变二分。

后者意味着坏结构在许多局部随机游走中留下统计信号。Goldreich--Ron 型 tester 从随机起点发出许多长度 \(L=\operatorname{poly}(1/\epsilon)\) 的游走。若图远离二分，某些终点可由同一起点通过偶长和奇长路径同时到达。

把随机游走种子 \(s\) 映到

\[ F(s)=(\text{终点},\text{路径奇偶}), \]

寻找“终点相同、奇偶不同”的碰撞。经典要生成约 \(\sqrt n\) 个样本才有生日碰撞；量子 element-distinctness/碰撞子程序对相干 walk-seed oracle 搜索，结合 derandomized walk family，将查询降到

\[ O(n^{1/3}) \]

（固定 \(d,\epsilon\)，省略 polylog/精度因子）。

5. Expansion testing

扩展性要求小集合有大量出边。差扩展图含 bottleneck，随机游走混合慢，多个种子更容易落到相同终点；好 expander 的终点近均匀，碰撞率较低。量子算法同样把经典 random-walk collision statistic 交给 element distinctness/量子计数，得到 \(O(n^{1/3})\) 上界。

该问题还有 \(\Omega(n^{1/4})\) 量子下界，排除了指数加速但留下 \(1/4\) 与 \(1/3\) 指数空隙。性质定义必须固定允许的 expansion gap；无 gap 的精确 spectral expansion 判定不是同一任务。

6. 时间、空间与可逆随机游走

查询一个随机游走终点需要相干执行 \(L\) 次 neighbor oracle，并保留或可逆清除随机选择。若直接存所有路径会消耗 \(O(L\log n)\) 空间；伪随机种子、可逆迭代和嵌套数据结构可把空间降到 polylog，同时保持

\[ \widetilde O(n^{1/3}) \]

在固定性质参数下的时间尺度。

邻接表顺序可能由 oracle 任意排列；算法不能假定同一顶点邻居已排序。多重边、自环与无向对称槽也应在输入承诺中明确。

7. 小例子

路径图 \(P_n\) 有 \(m=n-1\)，MST 就是自身，\(\sqrt{nm}=\Theta(n)\)。完全图有 \(m=\Theta(n^2)\)，array 与 matrix 模型 MST 都为 \(\Theta(n^{3/2})\) 查询。

奇环 \(C_{2r+1}\) 不是二分图，但只删除一条边即可变二分；当 \(r\) 随 \(n\) 大时，它未必是常数 \(\epsilon\)-far。因此 property tester 不保证以常数查询发现单个长奇环，这正体现 promise 的作用。

8. 小结与习题

  • 邻接表总搜索空间是 \(2m\) 个槽，适合稀疏图。

  • Borůvka 分量槽数的平方根求和给出 \(\Theta(\sqrt{nm})\) MST。

  • Exact connectivity 可通过只找任意出边和 amortization 达到 \(\Theta(n)\)。

  • 有界度性质测试把远离承诺转成大量随机游走碰撞，量子复杂度 \(O(n^{1/3})\)。

  1. 推导一轮 Borůvka 的 \(\sqrt{2mc}\) 上界。

  2. 比较 \(m=n,n^{3/2},n^2\) 时 MST 查询指数。

  3. 解释单个长奇环为何不一定满足常数 far promise。

  4. 设计从 walk seed 到 endpoint/parity 的可逆 oracle。

参考文献