一個圖上的漢彌爾頓路徑(迴路)，是一個簡單的路徑(迴路)，該路徑會訪問圖形的每個頂點剛好一次，漢彌爾頓圖(迴路)問題是要確定圖形是否含有漢彌爾頓圖(迴路)。如果含有漢彌爾頓迴路的話，則圖形稱作漢彌爾頓，如果在任何兩個不同頂點間有漢彌爾頓迴路，就被稱作漢彌爾頓連接。我們先介紹超級網格圖，當中包括了網格圖及三角形網格圖，以作為它們的子圖。網格圖及三角形網格圖的漢彌爾頓路徑(迴路)問題已知是NP完全。最近。我們亦已經證明了它們也是超級網格圖的NP完全。超級網格圖上的這些問題，可以應用於電腦縫紉機上的縫合痕跡。近期，我們也發現除兩個微不足道的禁止條件外，矩形超級網格圖是漢彌爾頓連接。在本文中，我們將會研究一些形狀超級網格圖的漢彌爾頓度及漢彌爾頓連接，當中包括了三角形，平行四邊形及梯形。我們也會證明這些形狀超級網格圖，除了一些微不足道的禁止條件外，它們總是包含了漢彌爾頓迴路，並且是漢彌爾頓連接。

A Hamiltonian path (cycle) of a graph is a simple path (cycle) in which each vertex of the graph is visited exactly once. The Hamiltonian path (cycle) problem is to determine whether a graph contains a Hamiltonian path (cycle). A graph is called Hamiltonian if it contains a Hamiltonian cycle, and it is said to be Hamiltonian connected if there exists a Hamiltonian path between any two distinct vertices. Supergrid graphs were first introduced by us and include grid graphs and triangular grid graphs as their subgraphs. These problems on supergrid graphs can be applied to compute the stitching traces of computerized sewing machines. In the past, we have proved the Hamiltonian path (cycle) problem on supergrid graphs to be NP-complete. Recently, we showed that rectangular supergrid graphs are Hamiltonian connected except one trivial forbidden condition. In this paper, we will verify the Hamiltonicity and Hamiltonian connectivity of some shaped supergrid graphs, including triangular, parallelogram, and trapezoid. The results can be used to solve the Hamiltonian problems on some special classes of supergrid graphs in the future.

目錄
摘要 I
Abstract II
目錄 III
圖目錄 VI
研究動機與目的 VII
第一章緒論 1
第二章材料與方法 4
A. 符號 4
定義 (Definition) 1： 6
定義2 9
定義3 10
定義4 11
定義5 12
B. 背景結果 12
引理 (Lemma) 1 12
引理2 14
命題 (Proposition) 3 14
命題4 14
命題5 15
第三章三角形和平行四邊形超級網格圖的漢彌爾頓度和漢彌爾頓連接 16
A.三角形超級網格圖的漢彌爾頓度和漢彌爾頓連接 16
引理6 16
引理7 18
引理8 19
B.平行四邊形超級網格圖的漢彌爾頓和漢彌爾頓連通性 23
引理9 23
引理10 27
引理11 28
引理12 28
引論13 34
定理14 37
C. 梯形超級網格圖的漢彌爾頓度和漢彌爾頓連接 37
引論15 38
引理17 41
引論18 45
定理19 47
第四章結語級備註 48
參考文獻 49

 

[1] M.A.H. Akhand, Shahina Akter, M.A. Rashid, and S.B. Yaakob, “Velocity tentative PSO: an optimal velocity implementation based particle swarm optimization to solve traveling salesman problem,” IAENG Intern. J. Comput. Sci., vol. 42, pp. 221–232, 2015.
[2] A.A. Bertossi and M.A. Bonuccelli, “Hamiltonian circuits in interval graph generalizations,” Inform. Process. Lett., vol. 23, pp. 195–200, 1986.
[3] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan Press, London, 1976.
[4] L. Chen, J. Meng, Y. Tian, and F. Liu, “Restricted connectivity of Cartesian product graphs,” IAENG Intern. J. Appl. Math., vol. 46, pp. 58–63, 2016.
[5] X. Chen, D. Xie, W. Xiong, and J. Meng, “Total restrained domination in trees,” Eng. Lett., vol. 24, pp. 69–74, 2016.
[6] G.H. Chen, J.S. Fu, and J.F. Fang, “Hypercomplete: a pancyclic recursive topology for large scale distributed multicomputer systems,” Networks, vol. 35, pp. 56–69, 2000.
[7] Y.C. Chen, C.H. Tsai, L.H. Hsu ,and J.J.M. Tan, “On some super fault-tolerant Hamiltonian graphs,” Appl. Math. Comput., vol. 148, pp. 729–741, 2004.
[8] P. Damaschke, “The Hamiltonian circuit problem for circle graphs is NP-complete,” Inform. Process. Lett., vol. 32, pp. 1–2, 1989.
[9] N. Funabiki, S. Sukaridhoto, M. Hata, S. Tomisato, T. Nakanishi, K. Watanabe, and S. Tajima, “A smart access-point selection Algorithm for scalable wireless mesh networks,” IAENG Intern. J. Comput. Sci., vol. 38, pp. 260–267, 2011.
[10] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979.
[11] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.
[12] V.S. Gordon, Y.L. Orlovich, and F. Werner, “Hamiltonin properties of triangular grid graphs,” Discrete Math., vol. 308, pp. 6166–6188, 2008.
[13] T. Helmy and Z. Rasheed, “Independent job scheduling by fuzzy Cmean clustering and an ant optimization algorithm in a computation grid,” IAENG Intern. J. Comput. Sci., vol. 37, pp. 136–145, 2010.
[14] R.W. Hung, “Constructing two edge-disjoint Hamiltonian cycles and two-equal path cover in augmented cubes,” IAENG Intern. J. Comput. Sci., vol. 39, pp. 42–49, 2012.
[15] R.W. Hung, C.C. Yao, and S.J. Chan, “The Hamiltonian properties of supergrid graphs,” Theoret. Comput. Sci., vol. 602, pp. 132–148, 2015.
[16] R.W. Hung, “The property of edge-disjoint Hamiltonian cycles in transposition networks and hypercube-like networks,” Discrete Appl. Math., vol. 181, pp. 109–122, 2015.
[17] R.W. Hung, “Hamiltonian cycles in linear-convex supergrid graphs,” Discrete Appl. Math., vol. 211, pp. 99–121, 2016.
[18] Ruo-Wei Hung, Chien-Hui Hou, Hao-Yu Chih, Xiaoguang Li, and Bing Sun, “The Hamiltonian connectivity of rectangular supergrid graphs,” Lecture Notes in Engineering and Computer Science: Proceedings of The International MultiConference of Engineers and Computer Scientists 2016, 16-18 March, 2016, Hong Kong, pp. 115–121.
[19] Ruo-Wei Hung, Jong-Shin Chen, Jun-Lin Li, and Chin-Han Lin, “The Hamiltonian connected property of some shaped supergrid graphs,” Lecture Notes in Engineering and Computer Science: Proceedings of The International MultiConference of Engineers and Computer Scientists 2017, 15-17 March, 2017, Hong Kong, pp. 63–68.
[20] C.H. Huang and J.F. Fang, “The pancyclicity and the Hamiltonianconnectivity of the generalized base-b hypercube,” Comput. Electr. Eng., vol. 34, pp. 263–269, 2008.
[21] W.T. Huang, M.Y. Lin, J.M. Tan, and L.H. Hsu, “Fault-tolerant ring embedding in faulty crossed cubes,” in Proceedings of World Multiconference on Systemics, Cybernetics, and Informatics (SCI’2000), 2000, pp. 97–102.
[22] W.T. Huang, J.J.M. Tan, C.N. Huang, and L.H. Hsu, “Fault-tolerant Hamiltonicity of twisted cubes,” J. Parallel Distrib. Comput., vol. 62, pp. 591–604, 2002.
[23] A. Itai, C.H. Papadimitriou, and J.L. Szwarcfiter, “Hamiltonian paths in grid graphs,” SIAM J. Comput., vol. 11, pp. 676–686, 1982.
[24] D.S. Johnson, “The NP-complete column: an ongoing guide,” J. Algorithms, vol. 6, pp. 434–451, 1985.
[25] M.S. Krishnamoorthy, “An NP-hard problem in bipartite graphs,” SIGACT News, vol. 7, p. 26, 1976.
[26] Y. Li, S. Peng, and W. Chu, “Hamiltonian connectedness of recursive dual-net,” in Proceedings of the 9th IEEE International Conference on Computer and Information Technology (CIT’09), vol. 1, 2009, pp. 203–208.
[27] J. Liu and X. Zhang, “Cube-connected complete graphs,” IAENG Intern. J. Appl. Math., vol. 443, pp. 134–136, 2014.
[28] M. Liu and H.M.Liu, “The edge-fault-tolerant Hamiltonian connectivity of enhanced hypercube,” in International Conference on Network Computing and Information Security (NCIS’2011), vol. 2, 2011, pp. 103–107.
[29] R.S. Lo and G.H. Chen, “Embedding Hamiltonian paths in faulty arrangement graphs with the backtracking method,” IEEE Trans. Parallel Distrib. Syst., vol. 12, pp. 209–222, 2001.
[30] L. Lun, X. Chi, and H. Xu, ”An algorithm for nodes-constrained shortest component path on software architecture,” Eng. Lett., vol. 25, pp. 52–60, 2017.
[31] Y. Mi, L. Zuo, and C. Shang, “On minimal energy of a class of bicyclic graphs with given cycles’ length and pendent vertices,” IAENG Intern. J. Appl. Math., vol. 47, pp. 97–105, 2017.
[32] G.K.D. Saharidis, G. Kolomvos, and G. Liberopoulos, “Modeling and aolution approach for the environmental traveling salesman problem,” Eng. Lett., vol. 22, pp. 70–74, 2014.
[33] L. Zuoy, S. He, and R. Wang, “The linear 4-arboricity of balanced complete bipartite graphs,” IAENG Intern. J. Appl. Math., vol. 45, pp. 23–30, 2015.
[34] L. Zuoy, B. Zhang, and S. Zhang, “The k-path vertex cover in product graphs of stars and complete graphs,” IAENG Intern. J. Appl. Math.,vol. 46, pp. 97–103, 2016.