平均漢米爾頓迴圈問題

The Balanced Hamiltonian Cycle Problem

王侯仁(Hou-Ren Wang)

指導教授 ： 阮夙姿

國立暨南國際大學/科技學院/資訊工程學系/碩士(2011年)

https://doi.org/10.6837/NCNU.2011.00310

摘要

三維掃描為目前許多產業重要的一環，如製造業、娛樂業，甚至醫學應用數位化。應用格雷碼來設計三維掃描是可有效降低資源與增加精確的方法之一。但格雷碼在位元轉換時常發生變換頻率集中在同一部份之問題，高頻率下容易會對影像的強度產生干擾；也容易發生編碼解碼時量化錯誤等問題，若能將位元變換頻率平均分散，則可以有效的提升編碼效能。針對降低位元變換時所產生的問題，我們可對映至圖形理論中的超立方體圖的平均漢米爾頓迴圈問題，並嘗試找出其規律性，進而提升格雷碼在應用上的效率。我們將平均漢米爾頓迴圈定義得更加廣泛。對於任意邊集合可分維度的圖形G，定義G的平均漢米爾頓迴圈問題為，在圖G上找出任意兩個維度邊數差異小於等於1的漢米爾頓迴圈。本文首先對超立方體圖Qn進行研究。此圖可分為兩種情況；第一種是n = 2k (k為正整數)，此種情形的理想狀況是，可以使超立方體圖Qn的平均漢米爾頓迴圈每一維度邊數為2n / n = 22k / 2k = 22k－k ；第二種是n ≠ 2k，此種情形的理想狀況是，可以使超立方體圖Qn的平均漢米爾頓迴圈每一維度邊數差異小於等於1。本研究先從第二種情形著手，提出一個在n ≠ 2k情況下無法求得超立方體Qn的平均漢米爾頓迴圈的證明；對於第一種情形則提出超立方體圖Q2，Q4的平均漢米爾頓迴圈，接著再提出一個尋找超立方體圖Q8的平均漢米爾頓迴圈的演算法。接下來我們針對Cn × Cn、Cn × Kmn、Cn × Cmn、C3 × Km、C4 × Cm (m, n為大於3之正整數)，進行研究。首先提出在Cn × Cn上尋找平均漢米爾頓迴圈的演算法。接著再提出對於奇數n的Cn × Kmn；及對於偶數n的Cn × Cmn上尋找平均漢米爾頓迴圈的演算法。最後，提出在C3 × Km及C4 × Cm上尋找平均漢米爾頓迴圈的演算法。

關鍵字

漢米爾頓迴圈 ； 平均 ； 超立方體 ； 卡氏積 ； 環方格圖

並列摘要

The application of gray-code is one of the ways in decreasing resource consumption and increasing precision for 3D scanning. The bit conversion of gray-code usually concentrates on some parts. That will cause some problems, such as the interference strength of an image or the error of decoding. If we can average the bit conversion into all different bits, then there will be more efficient. The problem of finding an average bit conversion of gray-code is equivalent to the problem of finding a balanced Hamiltonian cycle in a hypercube. We define a balanced
Hamiltonian cycle in a graph G, whose edge set can be partitioned into n dimensions, by a Hamiltonian cycle C in G such that for the set of all i-dimensional edge Ei(C) in E(C), ||Ei(C)| － |Ej(C)|| = 1, for i ≠ j. In this thesis, we prove that there is no balanced Hamiltonian cycle in hypercube Qn when n ≠ 2k for any positive integer k, and there is a balanced Hamiltonian cycle in hypercube Qn for n = 2k, when k = 1,2 and 3. Furthermore, for any positive integer m, n ≥ 3 we propose a method to find a balanced Hamiltonian cycle on Cn × Cn (also called torus graphs T(n, n)). Next we find a balanced Hamiltonian cycle on Cn × Kn when n is odd. When n is even we can get better result that to find a balanced Hamiltonian cycle on Cn × Cmn. Finally, we propose two algorithms to find a balanced Hamiltonian cycle on C3 × Km and C4 × Cm.

並列關鍵字

Hamiltonian cycle ； balanced ； hypercube ； Cartesian product ； torus ； toroidal mesh

參考文獻

[1] A. E. Brouwer, I. J. Dejter, and C. Thomassen, "Highly symmetric subgraphs of hypercubes," Journal of Algebraic Combinatorics, Vol. 2, No. 1, pp. 25－29,1993.

[2] M. Buratti, "Edge-colourings characterizing a class of cayley graphs and a new characterization of hypercubes," Discrete Mathematics, Vol. 161, pp. 291－295, 1996.

[3] C. H. Chang, C. K. Lin, H. M. Huang, and L. H. Hsu, "The super laceability of the hypercubes," Information Processing Letters, Vol. 92, No. 1, pp. 15－21, 2004.

[4] Y. C. Chen, The Enhanced Pyramid Network: An Attractive Alternative to the Pyramid Network. Master Thesis of Department of Computer Science and Information Engineering, National Chi Nan University, 2004.

[5] Y. Y. Chin, Binary and M-ary Structured Light Patterns with Gray Coding Rule in Active Non-contact 3D Surface Scanning. Master Thesis of Department of Computer Science and Information Engineering, National Chi Nan University, 2009.