# 诱导四邻接网格森林不一定能通过补点扩充成树

[English](tree-extension.en.md) · [完整构造与证明](../examples/tree-extension.zh.md) · [引用](../../../../../CITATION.md) · [研究目录](../README.md)

任意抽象森林都可以通过增加连接扩充成树，但固定在整数网格上的诱导森林存在额外限制：在保留所有原顶点及全部四邻接边、仅允许添加格点的条件下，有些森林无法成为任何诱导网格树的子图。即使允许任意扩大网格，这种障碍仍然存在。

检索词：诱导网格森林、森林扩充成树、树删除顶点、禁止桥接格点、四连通网格图；induced grid forest, induced tree extension, vertex addition, vertex-deleted grid tree, nonextendable forest, forbidden separator。

## 模型与准确结论

对有限整数格点集 $F\subset\mathbb Z^2$，令 $G(F)$ 包含曼哈顿距离为一的全部顶点对之间的边。问题是：若 $G(F)$ 为森林，是否总存在有限格点集 $S\supseteq F$，使 $G(S)$ 为树？

答案是否定的。这等价于问：原森林是否一定能由同一嵌入下的一棵诱导网格树删除顶点得到？模型不允许移动、缩放或删除原顶点，也不允许选择性忽略新产生的四邻接边。

| 规模 | 已给出的反例 |
| --- | --- |
| 小例 | 5×5 网格中，一条 13 点路径和一个孤立点无法补点连接成诱导树 |
| 两个大分量 | 两条各有线性个顶点的路径，之间存在必须经过而又不能填入的格点圈 |
| 多个大分量 | 边长为 $n$ 的网格中，有 $\Theta(n)$ 棵树，每棵有 $\Theta(n)$ 个顶点；任取两棵，即使移除其余分量，也无法补点连成诱导树 |

这里的线性规模相对于网格边长，而非总道路顶点数。嵌套构造的总道路数为 $\Theta(n^2)$。

## 障碍为什么成立

若某个空格同时邻接一棵已保留树中的两个不同顶点，填入它就会与树中现有的唯一路径组成环。因此，任何最终包含该树的诱导树都不能包含这个空格。

构造让这类禁止格组成分隔圈，另一个分量被圈在内部。任何连接路径都必须进入分隔圈，因而无法实现；外部有多少空间都不改变这个必经条件。逐层嵌套开缺口的阶梯路径，就得到线性数量的两两障碍。

![边长为 25 的网格内有三条嵌套路径，分别含 93、69、45 个顶点；叉号圈是不能填入的分隔圈。](../../assets/nested-tree-obstructions.svg)

完整证明给出坐标公式、禁止圈及计数。例如对整数 $s\ge1$，取 $n=12s+1$，可得到 $s+1$ 棵树，每棵顶点数介于 $2n-5$ 与 $4n-7$ 之间。详见[小例、两路径族和嵌套族](../examples/tree-extension.zh.md)。

## 适用范围

这否定的是“固定位置的诱导森林总能通过补点变成单树”这一直接归约。允许移动、缩放、改变边模型或分别处理分量的其他归约，需要另外分析。

这个静态构造不是超三次方匹配复杂度的反例。一般森林的候选列表算法仍满足[三次方上界](cubic-bound.zh.md)。本项结果的状态是“仓库已给出反例族及任意参数下的证明”；有限实例验证是辅助证据，不作外部同行评审声明。

## 复核与引用

在仓库根目录使用 Python 3.10 或更高版本运行：

```text
python topics/simulation/grid-forest-matching/research/verify_tree_extension.py
```

[验证脚本](../verify_tree_extension.py)从坐标重新生成全部四邻接边，检查分量大小、森林性质、禁止格及分隔半径。任意参数下的不可扩充性由文字证明保证，不依赖有限枚举。

证明版本：2026-10-12 发布的[提交 640ae4a](https://github.com/OccamGC/MyAlgorithmProblems/commit/640ae4ac52a1ce5a3082022162611839f97591fe)。引用条目 `OccamGC2026GridForestTreeExtension` 及固定版本链接见[引用说明](../../../../../CITATION.md)；机器可读的假设与结论见[结论索引](../../../../../research-index.json)。