仅对角邻接的网格森林：奇偶拆分与三次方界¶

同时保留正交和对角边的模型另见八邻接拓展，其证明使用方向词推广。

日期：2026-10-12。本文给出仅允许四个对角方向时的完整归约证明。这是已有四邻接结果的推论：两种奇偶类各自同构于四邻接整数网格，答案与候选检查次数可逐项对应，无需重新建立收费证明。

检索词：对角邻接、对角网格森林、奇偶拆分、坐标变换、平移匹配、三次方上界；diagonal-only grid forest, parity decomposition, lattice isomorphism, translation matching。

1. 模型与结论¶

棋盘为 \(\{0,\ldots,n-1\}^2\)，道路点集为 \(F\)，道路数为 \(N=|F|\)，实际移动数为 \(m\)。邻接和移动都只允许

\[ D=\{(1,1),(1,-1),(-1,1),(-1,-1)\}. \]

道路之间保留全部这种边，并要求诱导图是森林。对角边不受两侧正交格是否为道路影响；两条边在格子内部几何相交不产生额外顶点。这里没有上下左右的边，也没有额外的“禁止穿角”规则。

起点必须完整执行移动前缀，失败后永久失效；候选列表只在首次出现相对位移时筛选。记这些筛选中逐候选检查的总次数为 \(W\)，不计初始读取道路。则

\[ \boxed{W\le(5n-3)N},\qquad \boxed{T=O(n^2+m+nN)\subseteq O(n^3+m)}. \]

空间为 \(O(n^2)\)；短移动序列还满足 \(T=O(n^2+m+N\min(m,n))\)。在 \(m\ge n-1\) 时，该候选列表算法的最坏时间为 \(\Theta(n^3+m)\)。这不是所有可能算法的三次方下界。

补点扩充成单树时，跨奇偶类已有不可连通障碍；即使所有原点属于同一奇偶类，四邻接模型中的不可扩充反例族仍然保留。

2. 两种颜色各自变回四邻接¶

每次对角移动使坐标和改变零或正负二，因此保持 \(x+y\pmod 2\)。令

\[ F_p=\{(x,y)\in F:x+y\equiv p\pmod 2\},\qquad p\in\{0,1\}. \]

两类之间没有边。对固定奇偶类定义

\[ \Phi_p(x,y)=(u,v)=\left(\frac{x+y-p}{2},\frac{x-y-p}{2}\right), \qquad \Phi_p^{-1}(u,v)=(u+v+p,u-v). \]

这是整个该奇偶类与整数格点之间的双射。四种边和移动恰好变为：

原移动	变换后移动
\((1,1)\)	\((1,0)\)
\((1,-1)\)	\((0,1)\)
\((-1,1)\)	\((0,-1)\)
\((-1,-1)\)	\((-1,0)\)

逆变换也把每条四邻接边变成对角边，因此不会漏边或增加额外边。诱导图、连通分量、环与森林性质全部保留。

例如下面五个道路点全属于偶数类。右图把变换后的第二坐标整体加一；字母保持对应，点号表示未选中的位置。

A . B        . A .
. C .   ->   B C D
D . E        . E .

左边中心与四角相连，右边中心与上下左右相连：它们是同一棵五点树的两种坐标表示。

变换后的棋盘不必是实心矩形，但每个坐标方向所占的整数范围都至多有 \(n\) 个值：原来的和 \(x+y\) 与差 \(x-y\) 各落在长度 \(2(n-1)\) 的区间内；固定奇偶后间隔为二，除以二后的跨度至多为 \(n-1\)。整体平移并在空缺处填障碍，就得到一个边长至多为 \(n\) 的原四邻接实例。空奇偶类直接忽略。

3. 为什么答案和检查次数也完全对应¶

设原查询的某个相对位移为 \(q=(a,b)\)。由对角移动产生的位移满足 \(a+b\equiv0\pmod2\)。定义

\[ L(q)=\left(\frac{a+b}{2},\frac{a-b}{2}\right). \]

对任意奇偶类中的起点 \(s\in F_p\)，都有

\[ \Phi_p(s+q)=\Phi_p(s)+L(q). \]

所以每个移动前缀在原道路上合法，当且仅当变换后的前缀在相应道路像上合法；离开棋盘或遇到障碍都对应非道路。两个子问题使用同一条变换后的移动序列。

线性映射 \(L\) 是单射，故“相对位移是否首次出现”也保持。把每次筛选前的候选按奇偶类分开，便得到两个子实例的候选列表；永久失效、重复位移、全部候选清空后的处理均对应。记第 \(t\) 步后的答案为 \(A_t\)，则

\[ A_t=A_{t,0}+A_{t,1},\qquad W=W_0+W_1,\qquad N=N_0+N_1. \]

对两个边长至多为原棋盘边长的森林应用已有定理，得到

\[ W\le(5n-3)N_0+(5n-3)N_1=(5n-3)N. \]

这是按道路数相加，并未多付一倍总道路预算。直接在原坐标维护候选也成立，实际程序不必创建两个新棋盘。初始扫描棋盘、读取并输出所有移动分别花平方和线性时间；结合每步至多检查全部道路的平凡界，就得到第 1 节的时间、空间及短序列结论。空道路或零次移动时检查次数均为零。

4. 三次方下界的迁移¶

反向考虑一个 \(k\times k\) 的四邻接实例，定义

\[ \Psi(u,v)=(u+v,\ u-v+k-1). \]

所有像点都位于 \(\{0,\ldots,2k-2\}^2\)，并属于同一个奇偶类。这个全局仿射映射把四邻接诱导图精确变为对角诱导图；单位移动也变为一次对角移动，答案和检查次数保持。

取偶数行全部铺满道路、其余行为空的四邻接实例，并连续向右移动 \(k-1\) 次。道路是互不相邻的水平路径，有

\[ N=\left\lceil\frac{k}{2}\right\rceil k,\qquad W=\left\lceil\frac{k}{2}\right\rceil \sum_{j=1}^{k-1}(k-j+1) =\left\lceil\frac{k}{2}\right\rceil\frac{(k-1)(k+2)}2 =\Theta(k^3). \]

映射后方向为 \((1,-1)\)，棋盘边长为 \(2k-1\)，故费用仍为边长的三次方。对任意充分大的目标边长，取 \(k=\lfloor(n+1)/2\rfloor\) 并用障碍补齐棋盘。已有 \(k-1\le n-1\) 次移动产生三次方费用；其后沿已走过的边来回补足任意更长移动序列。每步输出仍需常数时间，因此

\[ m\ge n-1\quad\Longrightarrow\quad T_{\mathrm{worst}}=\Theta(n^3+m). \]

5. 森林补点成树：简单障碍与原反例族¶

若原森林同时包含两个奇偶类的点，则无论添加多少格点、扩大多少空间，都无法连通。例如 \((0,0)\) 与 \((0,1)\) 两个孤立点就已构成反例。路径中的每一步都保持奇偶性，补点无法改变这一事实。

若所有原点属于同一奇偶类，任何包含它们的单棵对角树也只能属于这一类。由于第 2 节的双射定义在整个无限格点集上，任意对角诱导树扩充都将逆映射为一个四邻接诱导树扩充。因此，原四邻接模型中的不可扩充森林经第 4 节映射后仍然不可扩充，允许任意扩大棋盘也无济于事。

这同时迁移了两条大路径的障碍，以及线性数量、每棵线性大小、任取两棵都无法扩充成树的嵌套族。映射保留顶点数与分量，只将棋盘边长改变常数倍，所以两个线性量级均保持。这里仍要求固定原顶点位置并保留所有诱导边；未改动原反例的适用边界。

6. 复核范围、依赖与限制¶

一般结论由上述同构及已有四邻接证明推出。它不适用于“保留上下左右并加入对角线”的八邻接模型，也不直接涵盖依赖侧面障碍的禁止穿角规则。原题的题面、输入方向编码和标准程序保持四邻接定义；本文是独立拓展研究。

从仓库根目录运行 Python 3.10 或更高版本，只需标准库：

python topics/simulation/grid-forest-matching/research/verify_diagonal_only.py --output tmp/grid-forest-matching/diagonal-only-results.json

验证脚本与发布的结果报告记录：

边长一至十二的两个奇偶类，共 24 个棋盘类别：检查双射、诱导邻接与坐标范围。
边长一至三的全部 530 个道路点集：检查拆分前后的森林判定一致；其中 498 个是对角诱导森林。
对这 498 个森林枚举全部 256 条长度为四的移动序列，共 127,488 个组合：逐步核对答案、检查次数和上界，并以不跳过重复位移的直接模拟独立核对答案。这也覆盖这些序列的全部较短前缀。
迁移四个条带下界实例：目标棋盘边长分别为 7、15、31、63，检查次数分别为 18、140、1,080、8,432。

这些有限检查不穷举任意棋盘或任意长移动序列，也不重新验证原三次方收费证明。引用键为 OccamGC2026DiagonalGridForest，见引用说明。状态是“仓库提供文字证明”，不表示外部同行评审或形式化证明系统验证。