主題
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)。

另請參閱

環圖, 多米諾圖, 超立方體, 梯形圖, 晶格圖, 路徑圖, 車圖, 正方形網格, 環面網格圖

透過 探索

參考文獻

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. “網格圖。” 來自 Web 資源。 https://mathworld.tw/GridGraph.html

主題分類