Graffiti.pc 第 387 号猜想：计算机提出的 2-控制数难题
说明：本文介绍 Graffiti.pc 第 387 号猜想的背景、定义和研究进展。一般情形的完整证明请见独立文章：Graffiti.pc 第 387 号猜想的证明：补图、多项式与线性相关。
作者：QingJun（卿俊）· MiniMax ｜ AI 协助整理
摘要
Graffiti.pc 第 387 号猜想认为：对每一个有限、简单、连通图 $G$，如果 $n$ 是顶点数，$m(G)$ 是度序列的上中位数，$\gamma_2(G)$ 是 2-控制数，那么
\[\boxed{\gamma_2(G)\le n-m(G)+1}.\]这条式子很短，背后却包含一个棘手的落差：$m(G)$ 只是度序列的一个统计量，而 2-控制数取决于整张图的邻接结构。计算机从有限图数据库中发现了这种关系；数学家此前证明它对二部图、树、正则图、若干无三角形图、分裂图等图类成立。
一般情形的证明已另文给出。它有两个核心转折：第一，把“在 $G$ 中至少有两个邻点”改写为“在补图 $\bar G$ 中至多有 $t$ 个邻点”；第二，把若干补图邻域编码成次数为 $t$ 的多项式，利用有限维向量空间中的线性相关性选出恰当的顶点集合。最终得到更强的结论：对任意有限简单图，不论是否连通，不等式都成立。
一、Graffiti：让计算机负责提出问题
Graffiti 是一种早期的计算机辅助数学猜想生成程序，由休斯敦大学的数学家 Siemion Fajtlowicz 开发，并在 1986 年公开介绍。它最著名的应用领域是图论。
程序的基本流程可以概括为四步：
- 建立一个包含路径、圈、树、完全图以及大量自动生成图的数据库；
- 对每个图计算顶点数、直径、独立数、控制数、度数等图不变量；
- 自动组合这些不变量，搜索在数据库所有样本上成立的等式或不等式；
- 过滤平凡、重复或已被其他关系蕴含的式子，把留下来的候选命题交给数学家。
Fajtlowicz 对早期 Graffiti 的描述非常直接：程序“认识”一些图，能够计算由图不变量组成的公式；只要已知图中没有反例，公式就暂时被视为猜想。真正困难的部分不是生成公式，而是避免输出成千上万条正确却无趣的关系。DIMACS 对这套方法的介绍也强调，反例会被重新加入数据库，让后续猜想经受更严格的检验。
Graffiti.pc 与“斑点狗启发式”
Ermelinda DeLaViña 在 2000—2001 年开发了 Graffiti.pc。长期目标是把类似 Graffiti 的系统带到 PC 平台，短期目标则是服务本科生研究。它由数据库构造程序、猜想生成程序和 Visual Basic 用户界面组成，主要使用 Dalmatian heuristic，可译作“斑点狗启发式”。
这个名字来自一个形象比喻：每条保留下来的猜想都应该在数据上“碰到一个不同的斑点”。对上界而言，一条候选式不仅要在全部已知图上成立，还要至少在某个图上比此前保存的上界更好；否则它即使正确，也没有提供新信息。DeLaViña 的发展史综述记录了 Graffiti.pc 的结构、数据库和启发式实现。
因此，Graffiti 与今天常说的“让大模型直接写证明”并不是一回事。它更像一个高速实验数学家：先从大量数值表格中发现模式，再把最值得解释的模式交给人。
“第 387 号”只是 Graffiti.pc 的猜想清单 Written on the Wall II 中的编号，不是第 387 个已经证明的定理，也与 Erdős 问题编号无关。
二、什么是 2-控制数
设 $G=(V,E)$ 是有限简单图，$N(v)$ 表示顶点 $v$ 的邻点集合。顶点子集 $D\subseteq V$ 称为一个 2-控制集，如果每个不属于 $D$ 的顶点都至少有两个邻点属于 $D$：
\[\forall v\in V\setminus D,\qquad |N(v)\cap D|\ge 2.\]所有 2-控制集中最小的顶点数叫作图的 2-控制数：
\[\gamma_2(G)=\min\{|D|:D\text{ 是 }G\text{ 的 2-控制集}\}.\]普通控制集只要求 $D$ 外的每个顶点至少连接一个选中顶点；2-控制把这个要求提高到两个。它可以理解为带冗余的服务点配置：一个服务点失效时，外部顶点仍可能得到另一个服务点支持。
这里有一个容易忽略的细节：定义只检查 $D$ 外的顶点。属于 $D$ 的顶点不必再有两个 $D$ 中的邻点。因此它不同于要求闭邻域中至少包含两个选中顶点的“双重控制”，也不同于用 $0、1、2$ 权重定义的整数 $\lbrace 2\rbrace$-控制。
对圈 $C_n$，一个顶点若不在 $D$ 中，它左右两侧的邻点都必须在 $D$ 中，所以 $V\setminus D$ 必须是独立集。由此立即得到
\[\gamma_2(C_n)=n-\alpha(C_n)=\left\lceil\frac n2\right\rceil.\]三、猜想中的“上中位数”
把 $G$ 的顶点度数按非递减顺序排列：
\[d_1\le d_2\le\cdots\le d_n.\]度序列的上中位数定义为
\[m(G)= \begin{cases} d_{(n+1)/2}, & n\text{ 为奇数},\\[4pt] d_{n/2+1}, & n\text{ 为偶数}. \end{cases}\]偶数个数据时，它不是两个中间数的算术平均，而是较大的那个中间数。例如度序列
\[1,2,2,4,5,5\]的上中位数是 $d_4=4$。
这个定义保证至少有 $\lceil n/2\rceil$ 个顶点的度数不小于 $m(G)$。换言之，$m(G)$ 衡量的不是“有没有一个超级枢纽”，而是图中至少一半顶点能达到怎样的连接水平。
需要留意符号冲突：不少图论文用 $m(G)$ 表示边数，而在第 387 号猜想的文献里，$m(G)$ 专指度序列上中位数。必须根据上下文判断。
四、第 387 号猜想的准确表述
对任意 $n$ 阶有限简单连通图 $G$，Graffiti.pc 猜想
\[\boxed{\gamma_2(G)\le n-m(G)+1}.\]也就是说，只要知道顶点数和度序列上中位数，就应该能够保证存在一个至多含 $n-m(G)+1$ 个顶点的 2-控制集。
2010 年，DeLaViña、Craig E. Larson、Ryan Pepper 和 Bill Waller 在 Congressus Numerantium 第 203 卷发表了《Graffiti.pc on the 2-domination number of a graph》，系统整理程序产生的近 50 条 2-控制数猜想和相关结果；期刊目录给出的页码为 15—32。卷期目录
有些在线 PDF 的文字层会把猜想公式中的“$\le$”错误抽取成“$>$”。同页前一句明确写的是 $\gamma_2\le n-(m(G)-1)$，后续定理也都在证明上界；2021 年论文又以“Graffiti.pc Conjecture 387”的名称无歧义地重述为 $\le$。因此网络搜索结果中偶尔出现的反向符号只是文字抽取错误。
五、为什么选择中位数，而不是最大度
普通控制数有一个经典的 Berge 型上界：
\[\gamma(G)\le n-\Delta(G),\]其中 $\Delta(G)$ 是最大度。人们自然会问，能否为 2-控制数写出相似关系。但星图立即说明，最大度在这里过于乐观。
考虑 $n\ge3$ 时的星图 $K_{1,n-1}$。中心顶点的度为 $n-1$，但所有叶子的度都为 1。度为 1 的叶子不可能在集合外获得两个选中邻点，所以每个叶子都必须属于任意 2-控制集：
\[\gamma_2(K_{1,n-1})=n-1.\]如果机械套用 $n-\Delta(G)+1$，右边只有 2，显然失败。问题在于最大度只看一个顶点，一个异常枢纽不足以代表全图的冗余覆盖能力。
上中位数避免了这个缺陷：星图的度序列中超过一半都是 1，所以 $m(G)=1$，猜想只给出较宽松但正确的上界 $\gamma_2(G)\le n$。
下面是几个直观例子：
| 图 $G$ | $m(G)$ | $\gamma_2(G)$ | 猜想给出的上界 |
|---|---|---|---|
| 完全图 $K_n$ | $n-1$ | $2$ | $2$ |
| 六边形 $C_6$ | $2$ | $3$ | $5$ |
| 星图 $K_{1,n-1}$（$n\ge3$） | $1$ | $n-1$ | $n$ |
| 完全二部图 $K_{2,r}$ | $2$ | $2$ | $r+1$ |
完全图还说明公式中的 $+1$ 不能统一删掉。对 $n\ge2$ 的 $K_n$，一个顶点不足以让集合外的顶点获得两个选中邻点，而任意两个顶点已经足够，因此
\[\gamma_2(K_n)=2=n-(n-1)+1.\]六、为什么它难证明
第 387 号猜想只使用度序列的一个统计量，但 2-控制是一个依赖邻接位置的全局优化问题。
“许多顶点度数很大”并不自动说明它们的邻域以合适方式重叠。两个非同构图可以拥有完全相同的度序列，却有截然不同的局部结构、公共邻点和最小 2-控制集。
把 $D$ 的补集记作 $U=V\setminus D$，2-控制条件可以改写为：对每个 $u\in U$，至少有两条从 $u$ 出发的边跨过割 $(U,V\setminus U)$。所以猜想等价于要求找到一个至少含 $m(G)-1$ 个顶点的集合 $U$，使其中每个顶点都有至少两个邻点留在集合外。
度中位数只告诉我们“有多少边从顶点发出”，却没有直接说明“这些边通向哪里”。从局部度统计中强制构造一个满足全部跨割条件的大集合，正是一般证明的主要障碍。
七、2010 年的第一批进展
2010 年论文利用了 2-独立数 $\alpha_2(G)$。如果一个顶点集 $I$ 所诱导的子图最大度小于 2，也就是每个顶点在 $I$ 内至多有一个邻点，就称 $I$ 为 2-独立集；最大此类集合的大小记作 $\alpha_2(G)$。
Favaron 的一般结果给出
\[\gamma_2(G)\le \alpha_2(G).\]DeLaViña 等人进一步证明，当 $\alpha_2(G)>n/2$ 时，
\[\alpha_2(G)\le n-m(G)+1.\]两式合并，便证明了第 387 号猜想在 $\alpha_2(G)>n/2$ 的情形成立。论文随后处理边界情形，并推出猜想对所有二部图成立。
这立即覆盖了全部树和偶圈。它也说明，程序发现的度中位数关系并不只是对小型数据库偶然成立，而是已经能够从成熟的 2-独立理论中得到大范围解释。
八、2021 年：从正则图推进到分裂图
柳忠伟和吴宝音都仍在 2021 年《数学进展》发表《图的 2-控制数的上界和一个 Graffiti.pc 猜想》，把第 387 号猜想作为主要研究对象。论文明确说明一般情形在当时仍未解决，然后给出以下进展。全文 PDF
1. 任意图上的较弱上界
对任意 $n$ 阶图，都有
\[\gamma_2(G)\le n-\delta(G)+1,\]其中 $\delta(G)$ 是最小度。由于
\[\delta(G)\le m(G)\le\Delta(G),\]这个结果比猜想弱，但给出了一个不需要额外结构的一般保证。
2. 上中位数接近最小度
如果连通图满足
\[m(G)\le\delta(G)+1,\]那么第 387 号猜想成立。直观上，这是度数分布较集中的情形：中间顶点的度不会比最低度高出太多。
3. 正则图
如果 $G$ 是 $k$-正则图，则 $m(G)=k$，论文证明
\[\gamma_2(G)\le n-k+1.\]而且等号仅在完全图 $K_n$ 中成立。对非完全的 $k$-正则图，还有更强的
\[\gamma_2(G)\le n-k.\]4. 无三角形图
若 $G$ 无三角形且 $\delta(G)\ge2$，则
\[\gamma_2(G)\le n-\Delta(G).\]因为 $\Delta(G)\ge m(G)$，这个上界甚至强于第 387 号猜想所要求的结果。它覆盖了包括奇圈在内的许多非二部图，因此是真正超出 2010 年二部图结果的一步。
最小度条件不能随意去掉：星图无三角形，却有 $\delta=1$，而它正是最大度型上界失败的典型例子。
5. 分裂图与阈值图
分裂图的顶点可以划分为一个团 $X$ 和一个独立集 $Y$。2021 年论文通过把团中顶点在 $Y$ 内的邻域转化为一个超图，证明第 387 号猜想对全部分裂图成立。
对分裂图的子类——阈值图——论文还求出了精确的 2-控制数。若 $\Delta_2(G)$ 表示第二大度数，则
\[\gamma_2(G)= \begin{cases} n, & \Delta(G)\le1,\\ n-1, & \Delta(G)\ge2\text{ 且 }\Delta_2(G)=1,\\ n-\Delta_2(G)+1, & \Delta_2(G)\ge2. \end{cases}\]在一般证明出现之前，主要已证范围可以压缩成下表：
| 条件或图类 | 已知结论 |
|---|---|
| 任意图 | $\gamma_2\le n-\delta+1$ |
| $\alpha_2(G)>n/2$ | 第 387 号猜想成立 |
| 二部图、树 | 第 387 号猜想成立 |
| $m(G)\le\delta(G)+1$ | 第 387 号猜想成立 |
| $k$-正则图 | 成立；非完全图还有 $\gamma_2\le n-k$ |
| 无三角形且 $\delta\ge2$ | 更强的 $\gamma_2\le n-\Delta$ |
| 分裂图 | 第 387 号猜想成立 |
| 阈值图 | 已知精确公式 |
九、从猜想到一般定理
一般情形的证明现已整理为独立文章：Graffiti.pc 第 387 号猜想的证明：补图、多项式与线性相关。
也可以直接查看或下载 英文证明 PDF（3 页，181 KB）。
证明得到的结论比原猜想稍强：如果 $G$ 是任意有限简单图，$m$ 是其度序列的上中位数，那么
\[\gamma_2(G)\le n-m+1.\]原猜想要求 $G$ 连通，而一般证明没有使用连通性。它先在补图中重述 2-控制条件，再用次数不超过 $t$ 的多项式编码邻域；一个极小线性相关族所强制的交叠性质，最终给出所需的 2-控制集。
十、不要与“消灭数猜想”混淆
2010 年论文在第 387 号猜想之后，还讨论了另一个关系：
\[\gamma_2(G)\le a(G)+1,\]其中 $a(G)$ 是 annihilation number，中文常译作消灭数或湮灭数。这个猜想与上中位数猜想使用的图不变量不同，研究状态也完全不同。
2019 年，Jun Yue、Shizhen Zhang、Yiping Zhu、Sandi Klavžar 和 Yongtang Shi 构造了一族连通仙人掌图，证明 $\gamma_2(G)-a(G)$ 可以任意大，从而推翻了消灭数猜想。反例论文
两条关系应当明确区分：
| 猜想 | 状态 |
|---|---|
| $\gamma_2(G)\le n-m(G)+1$，$m(G)$ 为度序列上中位数 | 第 387 号；已证明，完整论证见独立文章 |
| $\gamma_2(G)\le a(G)+1$，$a(G)$ 为消灭数 | 已于 2019 年被推翻 |
网上检索“Graffiti.pc 2-domination conjecture”时，两篇文献经常同时出现；如果忽略右边使用的是 $m(G)$ 还是 $a(G)$，很容易误报第 387 号也已经被反驳。
十一、这个证明带来的启发
第 387 号猜想的价值不只在于又多了一条图论不等式。它集中体现了计算实验、结构理论和自动猜想之间的分工。
计算机看到的是一张表：每一行是一张图，每一列是一个图不变量。它发现 $\gamma_2$、$n$ 与度序列上中位数之间存在异常稳定的关系，却不能仅凭有限样本解释原因。数学家随后发现，这条关系可以在二部结构、度数集中、无三角形结构和团—独立集分解中分别得到证明，但这些证明使用的机制并不完全相同。
一般情形需要一种更统一的思想：只依靠“至少一半顶点达到某个度数”这一粗糙信息，控制所有可能的邻域重叠方式。独立文章中的证明通过补图把 2-控制条件变成一个上界问题，再用多项式的根记录邻域成员。线性相关关系禁止某个顶点“只差一次就成为公共元素”，由此把看似杂乱的邻域重叠压缩成可控制的公共部分。
它也展示了 Graffiti 传统最有意思的地方：机器负责从数据中指出一块看似有规律的区域，而证明负责解释为什么有限样本中的规律会对所有图成立。这里，解释最终来自图论、补图变换与线性代数之间一次并不显然的连接。
主要文献
- Ermelinda DeLaViña, Some History of the Development of Graffiti, 2005.
- Ermelinda DeLaViña, Craig E. Larson, Ryan Pepper, Bill Waller, Graffiti.pc on the 2-domination number of a graph, Congressus Numerantium 203 (2010), 15–32.
- 柳忠伟、吴宝音都仍，图的 2-控制数的上界和一个 Graffiti.pc 猜想，《数学进展》50(3), 2021, 345–352，DOI: 10.11845/sxjz.2019140b。
- Jun Yue, Shizhen Zhang, Yiping Zhu, Sandi Klavžar, Yongtang Shi, The annihilation number does not bound the 2-domination number from the above, 2019.
评论