在超級網格圖中的漢彌爾頓迴路問題

The Hamiltonian Cycle Problem in Supergrid Graphs

詹尚儒(Shang-Ju Chan)

指導教授 ： 洪若偉

朝陽科技大學/資訊學院/資訊工程系/碩士(2015年)

摘要

在本文中，我們首先提出了一種新的圖形，即超級網格(supergrid)。超級網格圖包括網格圖和三角網格圖作為自己的子圖。網格圖和三角網格圖的漢彌爾頓圖迴路與路徑問題，被稱為是NP完全問題。然而在超級網格圖中尚未提出。超級網格圖中漢彌爾頓圖迴路（路徑）的問題可以應用於電腦控制縫紉機的針跡描繪。在本文中，我們將證明，在超級網格圖形中哈密頓迴路問題是NP完全問題。這是很容易由漢彌爾頓迴路特性所得出的結果，在超級網格圖的漢彌爾頓路徑問題也是NP完全問題。然後，我們證明超級網格圖，包括矩形（並行）和字母的兩個子類，總是包含漢彌爾頓迴路。

關鍵字

漢彌爾頓特性 ； 超級網格圖

並列摘要

In this thesis, we first introduce a novel class of graphs, namely supergrid. Supergrid graphs include grid graphs and triangular grid graphs as their subgraphs. The Hamiltonian cycle and path problems for grid graphs and triangular grid graphs were known to be NP-complete. However, they are unknown for supergrid graphs. The Hamiltonian cycle (path) problem on supergrid graphs can be applied to control the stitching trace of computerized sewing machines. In this thesis, we will prove that the Hamiltonian cycle problem on supergrid graphs is NP-complete. It is easily derived from the Hamiltonian cycle result that the Hamiltonian path problem on supergrid graphs is also NP-complete. We then show that two subclasses of supergrid graphs, including rectangular (parallelism) and alphabet, always contain Hamiltonian cycles.

並列關鍵字

Hamiltonian properties ； supergrid graph

參考文獻

[3] A.A. Bertossi, and M.A. Bonuccelli, “Hamiltonian circuits in interval graph generalizations,” Inform. Process. Lett. vol. 23, pp. 195–200, 1986.

[4] J.A. Bondy and U.S.R. Murty, “Graph Theory”, 2nd Ed., Springer, New York, 2008.

[5] I. Bouchemakh and M. Zemir, “On the broadcast independence number of grid graph,” Graph. Combinator., vol. 30, pp. 83–100, 2014.

[6] S.D. Chen, H. Shen, and R. Topor, “An efficient algorithm for constructing Hamiltonian paths in meshes,” Parallel Comput., vol. 28, pp. 1293–1305, 2002.

[7] P. Damaschke, “The Hamiltonian circuit problem for circle graphs is NP-complete,” Inform. Process. Lett., vol. 32, pp. 1–2, 1989.