# 诱导网格森林无法总是通过补点变成树 讨论补记：2026-10-12。固定道路位置并保留全部四邻接边时，森林不一定能通过添加格点变成一棵树。这种障碍不仅存在于小例：一张方形网格中可以同时有线性数量的树，每棵都有线性个点，任意两棵都无法补点连成诱导树。本文记录问题、构造、证明与示例。英文版见 [English](tree-extension.en.md)。 ## 1. 问题的准确含义 用 $n$ 表示网格边长，用 $R=|F|$ 表示道路格数。讨论中用户所说的“大写 N 级别”指本文的边长 n；其他研究文档的大写 N 通常指道路格数。这里的“线性数量”给出的是 $\Theta(n)$ 构造，不只是一个大 O 上界。 对整数格点集合 S，令 G(S) 包含 S 中所有曼哈顿距离为一的点对作为边。问题是：对任意使 G(F) 为森林的道路集合 F，是否总存在有限集合 S，使 $$ F\subseteq S,\qquad G(S)\text{ is a tree}? $$ 这与“原森林能否由同一嵌入下的一棵诱导网格树删除顶点得到”等价。原有道路不能移动、删除或缩放；补点后产生的四邻接边也不能选择性忽略。下文甚至允许把网格任意扩大。 如果只讨论抽象图，答案是可以：增加一个新顶点，并向每个分量各选一个顶点连边，就得到树。如果保留网格位置但允许自由删边，也可以在连通的较大矩形网格中把原森林扩充成生成树。这两种操作都不同于本题只允许添加道路格的诱导图模型。 | 问题 | 结论 | | --- | --- | | 任意诱导四连通网格森林都能由一棵诱导网格树删点得到吗？ | 不能；一个 5×5 的两分量反例已经足够。 | | 障碍能否发生在两棵都达到线性大小的树之间？ | 能；两棵甚至都可以是简单路径，并有线性个直接相邻两侧的禁止桥接格。 | | 这样的树的数量也能达到线性级别吗？ | 能；同时有线性棵、每棵线性大小，而且任取两棵都无法补点连成诱导树。 | | 扩大网格、绕远路能否解决下面的构造？ | 不能；必须经过的格点本身就禁止填入，与外部空间大小无关。 | ## 2. 一个禁止补点的基本事实 设 A 是必须保留的一棵树，空格 x 与 A 中两个不同顶点 u、v 相邻。A 中已有唯一的 u 到 v 路径，填入 x 后，这条路径加上两条新边就形成环。 因此，**任何包含 A 的诱导树都不能包含 x**。这不是“某一种补点顺序会失败”，而是任何最终超图都不可能是树；同时添加其他点也不会消除已经存在的环。 只要这样的禁止格点把另一个分量与 A 分开，就不可能连接它们。后面的构造都使用这个事实。 ## 3. 5×5 的反例 下面每个字符代表一个格点。A 是一条 13 点路径，B 是一个孤立点，× 和 · 都是空格；× 特别标出 B 的四个邻格。 ```text · A A A · · A × A A · × B × A · A × A A · A A A · ``` A 与 B 不相邻，原图确实是两个分量的诱导森林。每个 × 都与至少两个 A 顶点相邻，因此都不能填入。B 向外走的第一步却必须经过某个 ×，所以 B 永远无法连接到 A。 这个例子可以放在任意更大的网格内部，论证仍然成立。这里仅称它为一个小反例，不声称它在边长或道路数意义下最小。 ## 4. 两棵线性大小的树也可以互相隔离 ### 4.1 带缺口的阶梯路径 以原点为中心，令 $$ \rho(x,y)=|x|+|y|. $$ 对整数 $t\ge2$，先构造阶梯环 $$ C_t=\{(x,y):\rho(x,y)=t\} \cup\{(x,y):\rho(x,y)=t+1,\ xy\ne0\}, $$ 再删除同一侧连续的三个点： $$ P_t=C_t\setminus\{(-1,-t),(0,-t),(1,-t)\}. $$ 如果把第一个坐标视为行、第二个坐标视为列，缺口就在最左侧。两层半径上的点沿四个象限依次交替连接，C_t 是一个诱导简单环：每个点度数为二，且整环连通。两层各有 $4t$ 个点。删去连续三个点后，得到一条诱导简单路径，满足 $$ |P_t|=8t-3,\qquad P_t\subseteq[-t,t]^2. $$ ### 4.2 两条路径的参数族 取整数 $k\ge5$，令 $$ n=2k+1,\qquad A=P_k,\qquad B=P_{k-3}. $$ 两条路径都放得进边长为 n 的网格，而且 $$ |A|=8k-3=4n-7,\qquad |B|=8k-27=4n-31. $$ A 的点半径至少为 k，B 的点半径至多为 k 减二，所以它们之间没有四邻接边。两棵树的大小都是 $\Theta(n)$。 ![边长为 11 的例子，外层路径 A 有 37 个点，内层路径 B 有 13 个点，16 个叉号格点组成无法填入的分隔圈。](../../assets/two-growing-tree-obstruction.svg) 图中两条路径本身都有缺口；真正阻止连接的是空格中的整圈 ×，而不是某条道路构成了环。 ### 4.3 缺口为什么不能成为通道 考虑空格圈 $$ X_k=\{(x,y):\rho(x,y)=k-1\}. $$ 非坐标轴上的圈内点有两个向外的邻点，均位于 A 的半径 k 那一层。坐标轴上的点原本有三个这样的邻点；即使面对路径缺口，也只少了一个，仍有两个。删除的另两个缺口点半径为 k 加一，不会与这圈格点相邻。 所以 X_k 中每个点都因第 2 节的事实而禁止填入。另一方面，四邻接移动每一步都使半径增加或减少一；从 B 的半径区域走到 A，必然经过 X_k。扩大网格也不改变这个必经条件。 这证明两条线性大小的路径无法补点连成诱导树。禁止格点数量为 $$ |X_k|=4k-4=2n-6. $$ 除四个坐标轴点和缺口旁的两个点以外，其余禁止格点还直接邻接 B。因此，同时邻接两棵树、却一填入就成环的格点恰有 $$ 4k-10=2n-12=\Theta(n). $$ 例如图中的边长为 11，两棵路径分别有 37、13 个点，禁止圈有 16 个点，其中 10 个直接邻接两棵路径。这把单个小障碍扩展成了线性规模的阻隔。 ## 5. 线性数量的树可以同时存在 取正整数 s，令 $$ n=12s+1,\qquad t_i=6s-3i\quad(0\le i\le s),\qquad T_i=P_{t_i}. $$ 也就是从半径 6s 开始，每次减三，一直嵌套到半径 3s。所有路径都位于同一张边长为 n 的网格中。相邻层之间的半径差足以避免四邻接边，因此这些路径恰好是森林的全部分量。 树的数量为 $$ s+1=\frac{n+11}{12}=\Theta(n). $$ 每棵树的大小为 $$ |T_i|=48s-24i-3,\qquad 2n-5\le |T_i|\le4n-7. $$ 因此每个分量都有 $\Theta(n)$ 个点，既没有靠孤立点凑数量，也没有嵌套到只剩常数大小的内层。总道路数为 $$ R=\sum_{i=0}^{s}|T_i|=(s+1)(36s-3)=36s^2+33s-3=\Theta(n^2). $$ ![边长为 25 的网格内嵌套三条阶梯路径，分别有 93、69、45 个点；两圈叉号分别阻断外层与所有更内层之间的连接。](../../assets/nested-tree-obstructions.svg) 对每个非最内层的路径，取 $$ X_i=\{(x,y):\rho(x,y)=t_i-1\}\qquad(0\le i