图性质测试模型

图性质与表示 ​

图性质通常是不依赖顶点标签的图集合：若 $G$ 满足性质，任何与 $G$ 同构的重标号图也满足。性质测试器只通过 oracle 接触图；同一抽象图采用不同图表示公理库图的表示Graph representation · Adjacency-list and adjacency-matrix representations依据图的类型与所需操作选择邻接表、邻接矩阵或边集表示的方法。时，可问问题、答案带宽和距离分母都会改变。

因此“图性质可用 $q(n,\epsilon )$ 次查询测试”不是完整句子。至少要声明 dense adjacency-matrix、bounded-degree adjacency-list，还是一般图 incidence-list 模型，以及图是简单、无向、有向或允许重边。

Dense adjacency-matrix 模型 ​

对 $n$ 顶点简单无向图，一次查询 $(u,v)$ 返回邻接 bit

$$A_G(u,v)=\mathbf{1}[\{u,v\}\in E(G)].$$

潜在无向边共有 $(\genfrac{}{}{0ex}{}{n}{2})$ 条。图间距离通常取需要增删的边数除以 $(\genfrac{}{}{0ex}{}{n}{2})$；$G$ 距性质 $\mathcal{P}$ 至少 $\epsilon$，表示任何变成 $\mathcal{P}$ 图的编辑都要改动至少 $\epsilon (\genfrac{}{}{0ex}{}{n}{2})$ 条边。

一次查询只返回一 bit，任意顶点对都可直接访问。模型适合边数为 $\mathrm{\Theta }(n^2)$ 的稠密图；若图只有 $O(n)$ 条边，它距空图在该归一化下仅为 $O(1/n)$，固定 $\epsilon$ 的 far 概念看不到这种稀疏差异。

无向简单图满足 $A_G(u,v)=A_G(v,u)$ 且对角为 $0$；查询两个方向不会提供两份独立信息。若 oracle 允许有向边或自环，输入空间和距离分母都要随之重定义。

Bounded-degree 邻接表模型 ​

固定最大度 $d$。一次查询 $(v,j)$，其中 $j\in [d]$，返回 $v$ 的第 $j$ 个邻居或空标记 $\mathrm{\perp }$。oracle 的邻居排列是表示的一部分，tester 不应假设按标签排序，除非模型明确保证。

表示共有 $dn$ 个邻接槽。距离可按需要修改的槽数除以 $dn$ 归一化；无向边通常占两个对称槽，合法编辑还要保持两端一致。复杂度会显式依赖 $d$，把 $d$ 隐藏进常数只适用于它确实固定的定理。

查询回答是一个顶点标签，含 $\mathrm{\Theta }(\log n)$ bit，却按一次 oracle access 计。它比 dense 模型的一 bit 回答更宽，同时不能直接询问任意边是否存在；要判断 $u$ 是否为 $v$ 的邻居，最坏需检查 $v$ 的全部 $d$ 个槽。

Edgeless 性质的两套 tester ​

考虑性质 $\mathcal{P}=$“没有边”。在 dense 模型中，若 $G$ 是 $\epsilon$-far，就至少有 $\epsilon (\genfrac{}{}{0ex}{}{n}{2})$ 条边。均匀抽一个无序顶点对，查询到边的概率至少 $\epsilon$；独立抽 $q\ge \lceil \ln 3/\epsilon \rceil$ 对并在发现边时拒绝，far 图误收概率至多 $1/3$，空图总被接受。

在 bounded-degree 模型中，均匀抽 $(v,j)\in [n]\times [d]$。若距离按非空邻接槽比例计且图 $\epsilon$-far，查询返回非 $\mathrm{\perp }$ 的概率至少 $\epsilon$；同样的重复次数得到单侧 tester。

两个算法的概率式相似，样本空间却不同。一个按 $(\genfrac{}{}{0ex}{}{n}{2})$ 个潜在边均匀抽样，另一个按 $dn$ 个槽抽样；同一含 $m$ 条边的图分别有距离

$$\frac{m}{(\genfrac{}{}{0ex}{}{n}{2})}\text{与近似}\frac{2m}{dn}.$$

当 $m=\mathrm{\Theta }(n)$、$d$ 为常数时，前者趋近 $0$，后者可以是常数。不能因为 tester 都写成“随机抽位置”就把结论横向复制。

一般图与适应性 ​

若不限制最大度，邻接表模型还需 degree query、neighbor query 以及按什么量归一化距离。高阶顶点可能占据大量边，均匀抽顶点与均匀抽边给出不同分布；算法必须说明采样对象。

邻居探索天然可能自适应公理库自适应与非自适应性质测试Adaptive property testing · Nonadaptive property testing按后续查询地址能否依赖此前 oracle 回答，区分自适应测试、非自适应测试与分批轮次。：先查询 $(v,j)$ 得到 $u$，再查询 $u$ 的槽。Dense 模型也能自适应，但顶点全集已知，许多固定小子图采样可预先列出全部边对。适应性结论仍需在同一 oracle 内比较。

模型边界 ​

不同模型中的“亚线性”分母不同。Dense 模型完整输入有 $\mathrm{\Theta }(n^2)$ bit，$O(n)$ 查询已亚线性；bounded-degree 表只有 $O(dn\log n)$ bit，同样 $O(n)$ 查询可能已接近全读。只按顶点数写 $o(n^2)$ 会掩盖这一差异。

图重标号不应改变性质，却会改变邻接表槽顺序。Tester 的正确性必须对每个合法排列成立，或把排列随机性明确纳入 oracle；假设有利顺序会偷渡额外结构。

最后，距离需要落在合法图表示之间。随意翻一个邻接矩阵 bit 可能破坏无向对称性，改一个邻接槽也可能让两端记录不一致；编辑计数应按边操作或成对槽修改定义，而不是把非法中间编码当作目标图。

参考资料

• Oded Goldreich, Shafi Goldwasser, and Dana Ron, “Property Testing and Its Connection to Learning and Approximation,” Journal of the ACM 45(4), 1998, pp. 653–750.
• Oded Goldreich and Dana Ron, “Property Testing in Bounded Degree Graphs,” Algorithmica 32, 2002, pp. 302–343.
• Oded Goldreich, Introduction to Property Testing, Cambridge University Press, 2017, Chapters 8–9.