$N*N$表格图的最小支配集规模是多少？

嘿，咱们先把定义掰扯清楚：题目里的“单元格相邻”应该是指共享一条边的上下左右四个方向（对角线不算直接相邻），这是表格里相邻的常规理解哈。如果是包含对角线的8邻域，结论会不一样，我先按4邻域来解答～

这个问题的答案得按N的大小分情况说，先给直观的小N结果，再讲一般规律：

小N值的具体结果 #

先列几个小N的情况，方便你快速理解：

• N=1：只有1个单元格，最小支配集就是它自己，大小为 1。
• N=2：2×2网格有4个单元格，单个单元格只能覆盖自己和两个相邻的单元格，对角线的那个点既不在集合里，也不与它直接相邻，所以必须选至少2个单元格（比如两个对角的单元格）才能覆盖所有点，大小为 2。
• N=3：最小支配集大小是 3，比如选(1,1)、(2,3)、(3,2)这三个点，就能覆盖所有9个单元格；试一下就知道，2个点根本覆盖不完——每个点最多覆盖5个点，两个点最多覆盖10个，但网格里的角落点和中心点的覆盖范围有重叠，总会有漏网的。
• N=4：最小支配集大小是 4，比如选(1,2)、(2,4)、(3,1)、(4,3)，就能覆盖所有16个单元格。

更大N的规律 #

对于更大的N，最小支配集的大小可以参考OEIS序列A001835（专门记录4连通n×n网格的最小支配集大小），它的规律没法用一个简单的闭合公式概括，但我们可以用交错块选择的方法构造出最小的支配集：

1. 把网格分成2×2的小方块，每个完整的2×2块选两个对角的单元格，这样能刚好覆盖整个块的4个单元格；
2. 如果N是奇数，剩下的一行和一列也用类似的交错选择策略，保证每个未被覆盖的单元格都能和选中的单元格直接相邻。

为什么这是最小的？ #

每个选中的单元格最多覆盖自己和4个相邻的单元格（共5个），但边界的单元格覆盖范围更少，所以最小支配集的大小至少是 $\lceil \frac{N^2}{5} \rceil$，但实际的最小大小比这个下界更紧——比如N=3时，$\lceil 9/5 \rceil=2$，但实际需要3个点，因为角落的点没法被单个中心点覆盖（对角线不算相邻）。

如果题目里的“相邻”是指包含对角线的8邻域，结论就简单多了：

• 当N为偶数时，最小支配集大小为 $\boldsymbol{\frac{N^2}{4}}$：把网格分成2×2的块，每个块选一个单元格，这个单元格通过8邻域能覆盖整个块的4个单元格；
• 当N为奇数时，最小支配集大小为 $\boldsymbol{\lceil \frac{N^2}{9} \rceil}$：比如N=3时，选中心1个点就能覆盖所有9个单元格；N=5时，选5个点（比如(1,1),(1,5),(3,3),(5,1),(5,5)）就能覆盖所有25个单元格。

内容的提问来源于stack exchange，提问作者user3866081