主题
Search

网格图

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本

二维网格图，也称为矩形网格图或二维晶格图（例如，Acharya 和 Gill 1981），是一个 m×n 晶格图，它是 图的笛卡尔积 P_m square P_n，其中 路径图 在 m 和 n 个顶点上。 m×n 网格图有时表示为 L(m,n)（例如，Acharya 和 Gill 1981）。 n×n 矩形网格图的特殊情况有时称为正方形网格图。

GridGraph

不幸的是，关于哪个索引对应宽度，哪个索引对应高度的约定仍然模糊不清。一些作者（例如，Acharya 和 Gill 1981）使用应用于 矩阵 尺寸标注的相同高度乘以宽度的约定（这也对应于画布上绘画的尺寸表达顺序）。Wolfram 语言 实现GridGraph[{m, n, ...}] 也采用了这种排序，返回的嵌入中 m 对应于高度，n 对应于宽度。其他来源采用用于测量纸张、房间尺寸和窗户的“宽度乘以高度”约定（例如，8 1/2 英寸 x 11 英寸的纸张是 8 1/2 英寸宽，11 英寸高）。因此，根据约定，上面图示的图可以被称为 7×4 网格图或 4×7 网格图。

Harary（1994，第 194 页）使用的另一种约定是，他没有明确说明哪个索引对应哪个维度，而是在定义 2-晶格时使用 0 偏移编号，作为其点是有序整数对 (i,j)，其中 i=0, 1, ..., m 和 j=0, 1, ..., n。如果将 Harary 的有序对解释为笛卡尔坐标，则参数为 m 和 n 的网格图由 m+1 个顶点沿 x-轴和 n+1 个顶点沿 y-轴组成。这与 图的笛卡尔积 中 P_m square P_n 的解释一致，即路径具有 m 和 n 条边（因此分别为 m+1 和 n+1 个顶点）。

请注意，Brouwer等人（1989，第 440 页）使用术语“m×n 网格”来指 线图 L(K_(m,n))，它是 完全二部图 K_(m,n) 的线图，在本工作中称为 车图 K_m square K_n。

可以使用以下命令获取许多网格图的预计算属性GraphData[{"Grid", {m, ..., r, ...}}].

网格图 P_m square P_n 有 mn 个顶点和 (m-1)n+(n-1)m=2mn-m-n 条边。

如果行数或列数是偶数，则网格图 P_m square P_n 是 哈密顿图 (Skiena 1990, p. 148)。网格图也是二分图 (Skiena 1990, p. 148)。m×n 和 n×n 网格图是 优美图 (Acharya 和 Gill 1981, Gallian 2018)。

d 维网格图的任意维度和形状似乎是 可追踪的，尽管关于这一断言的完整证明似乎并未出现在文献中（参见 Simmons 1978, Hedetniemi 等人 1980, Itai 等人 1982, Zamfirescu 和 Zamfirescu 1992）。

对于 n×n 网格图，当 n=1, 2, ... 时，有向 哈密顿路径 的数量由 1, 8, 40, 552, 8648, 458696, 27070560, ... 给出（OEIS A096969）。一般来说，对于固定的 m，m×n 网格图上的哈密顿路径的数量由线性递推关系给出。

对于 n×n 网格图，当 n=1, 2, ... 时，有向 哈密顿环 的数量为 0, 2, 0, 12, 0, 2144, 0, 9277152, ... （OEIS A143246）。一般来说，对于固定的 m，m×n 网格图上的哈密顿环的数量由线性递推关系给出。

对于 n×n 网格图，当 n=1, 2, ... 时，（无向）图环 的数量为 0, 1, 13, 213, 9349, 1222363, ... （OEIS A140517）。一般来说，n×n 网格图上 k-环的数量 c_k 由 c_k=0 给出，当 k 为奇数时，当 k 为偶数时，由关于 n 的二次多项式给出，前几个是

c_4=(n-1)^2
(1)
c_6=2(n-1)(n-2)
(2)
c_8={0 for n<3; 7(n-2)^2-2 otherwise
(3)
c_(10)={0 for n<4; 4[7(n-3)^2+7(n-3)-1] otherwise
(4)
c_(12)={0 for n<4; 76 for n=4; 2(62n^2-370n+523) otherwise
(5)
c_(14)={0 for n<4; 32 for n=4; 1100 for n=5; 12(49n^2-338n+556) otherwise
(6)
c_(14)={0 for n<4; 6 for n=4; 2102 for n=5; 11144 for n=6; 2(1469n^2-11452n+21395) otherwise
(7)

（E. Weisstein，2014 年 11 月 16 日）。

P_m square P_n 的 支配数 由下式给出

gamma(P_m square P_n)=|_((m+2)(n+2))/5_|-4
(8)

对于 16<=m<=n，正如 Chang (1992) 所推测的，Guichard (2004) 证实到加法常数，Gonçalves等人 (2011) 证明了这一点。Gonçalves等人 (2011) 给出了 m<16 的分段公式，但对于 n=16 给出的表达式并非在所有情况下都正确。Chang 和 Clark (1993) 的公式 (6) 中给出了归因于 Hare 的 n=16 的正确公式，但是随后给出了不正确的重新表述作为公式 (14)。

Mertens (2024) 计算了 n×n 网格图直到 n=22 的 支配多项式 和 支配集 的数量。

GridGraphsSpecial

广义网格图，也称为 n 维晶格图（例如，Acharya 和 Gill 1981），也可以定义为 P_m square P_n square P_r square ...（例如，Harary 1967，第 28 页；Acharya 和 Gill 1981）。这样的图有时表示为 G_(m,n,r,...) 或 L(m,n,r,...)（例如，Acharya 和 Gill 1981）。广义网格图的 色数 为 2，退化情况 单例图 除外，其 色数 为 1。特殊情况在上面说明并在下表中总结。

网格图特殊情况
P_1 square P_n路径图 P_n
P_2 square P_n梯形图 L_n
P_2 square P_2正方形图 C_4
P_2 square P_3多米诺图
P_2 square P_2 square P_2立方图 Q_3
P_2 square ... square P_2_()_(n)超立方体图 Q_n

P_m square P_n square P_2 是 优美图 (Liu 等人 2012, Gallian 2018)。

另请参阅

环图, 多米诺图, 超立方体, 梯形图, 晶格图, 路径图, 车图, 正方形网格, 环面网格图

通过 Wolfram|Alpha 探索

参考文献

Acharya, B. D. 和 Gill, M. K. "On the Index of Gracefulness of a Graph and the Gracefulness of Two-Dimensional Square Lattice Graphs." Indian J. Math. 23, 81-94. 1981.Brouwer, A. E.; Cohen, A. M.; 和 Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.Chang, T. Y. Domination Numbers of Grid Graphs. Ph.D. thesis. Tampa, FL: University of South Florida, 1992.Faase, F. "On the Number of Specific Spanning Subgraphs of the Graphs G square P_n." Ars Combin. 49, 129-154, 1998.Chang, T. Y. 和 Clark, W. E. "The Domination Numbers of the 5×n and 6×n Grid Graphs." J. Graph Th. 17, 81-107, 1993.Gallian, J. "Dynamic Survey of Graph Labeling." Elec. J. Combin. DS6. Dec. 21, 2018. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Gonçalves, D.; Pinlou, A.; Rao, M.; 和 Thomassé, S. "The Domination Number of Grids." SIAM J. Discrete Math. 25, 1443-1453, 2011.Guichard, D. R. "A Lower Bound for the Domination Number of Complete Grid Graphs." J. Combin. Math. Combin. Comput. 49, 215-220, 2004.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 194, 1994.Harary, F. "Graphical Enumeration Problems." In Graph Theory and Theoretical Physics (Ed. F. Harary). London: Academic Press, pp. 1-41, 1967.Hedetniemi, S. M.; Hedetniemi, S. T.; 和 Slater, P. S. "Which Grids Are Hamiltonian?" Congr. Numer. 29, 511-524, 1980.Itai, A.; Papadimitriou, C. H.; 和 Szwarcfiter, J. L. "Hamilton Paths in Grid Graphs." SIAM J. Comput. 11, 676-686, 1982.Iwashita, H.; Nakazawa, Y.; Kawahara, J.; Uno, T.; 和 Minato, S.-I. "Efficient Computation of the Number of Paths in a Grid Graph with Minimal Perfect Hash Functions." TCS Technical Report. No. TCS-TR-A-13-64. Hokkaido University Division of Computer Science. Apr. 26, 2013.Jacobsen, J. L. "Exact Enumeration of Hamiltonian Circuits, Walks and Chains in Two and Three Dimensions." J. Phys. A: Math. Theor. 40, 14667-14678, 2007.Karavaev, A. M. "FlowProblem: Hamiltonian Cycles." http://flowproblem.ru/paths/hamilton-cycles.Karavaev, A. M. "FlowProblem: Hamiltonian Paths." http://flowproblem.ru/paths/hamilton-paths.Liu, J. B.; Zou, T.; 和 Lu, Y. "Gracefulness of Cartesian Product Graphs." Pure Appl. Math. (Xi'an) 28, 329-332 and 362, 2012.Mertens, S. "Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph." 15 Aug 2024. https://arxiv.org/abs/2408.08053.Pönitz, A. "Computing Invariants in Graphs of Small Bandwidth." Math. in Computers and Sim. 49, 179-191, 1999.Reddy, V. 和 Skiena, S. "Frequencies of Large Distances in Integer Lattices." Technical Report, Department of Computer Science. Stony Brook, NY: State University of New York, Stony Brook, 1989.Schmalz, T. G.; Hite, G. E.; 和 Klein, D. J. "Compact Self-Avoiding Circuits on Two-Dimensional Lattices." J. Phys. A: Math. Gen. 17, 445-453, 1984.Simmons, G. J. "Almost All n-Dimensional Rectangular Lattices Are Hamilton-Laceable." In Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978) (Ed. F. Hoffman, D. McCarthy, R. C. Mullin, and R. G. Stanton). Winnipeg, Manitoba: Utilitas Mathematica Publishing, pp. 649-661, 1978.Skiena, S. "Grid Graphs." §4.2.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 147-148, 1990.Sloane, N. J. A. Sequences A096969, A140517, and A143246 in "The On-Line Encyclopedia of Integer Sequences."Umans, C. M. "An Algorithm for Finding Hamiltonian Cycles in Grid graphs without Holes." Undergraduate thesis.Umans, C. 和 Lenhart, W. "Hamiltonian Cycles in Solid Grid Graphs." In Proc. 38th Annual IEEE Sympos. Found. Comput. Sci. pp. 496-505, 1997.Zamfirescu, C. 和 Zamfirescu, T. "Hamiltonian Properties of Grid Graphs." SIAM J. Disc. Math. 5, 564-570, 1992.

请引用为

Weisstein, Eric W. “网格图。” 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/GridGraph.html

主题分类