當k為偶數時，在k位元n維立方體上的互相獨立之漢米爾頓迴圈

Mutually Independent Hamiltonian Cycles in k-ary n-cubes when k is even

潘佳伶(Jing-Ling Pan)

指導教授 ： 高欣欣

中原大學/理學院/應用數學研究所/碩士(2011年)

https://doi.org/10.6840/CYCU.2011.00193

摘要

k位元n維立方體已被使用於多數實際的平行電腦連線架構，並且在過去已被廣泛地研究。本篇論文中，我們將證明：當n為大於等於2的整數且k為大於等於4的偶數時，任一k位元n維立方體(Q(k,n))包含有2n條互相獨立之漢米爾頓迴圈。更具體地說，令N表示Q(k,n)的頂點總數，v(i)表示每個頂點，其中1≤ i ≤ N，且以〈v(1),v(2),…,v(N),v(1)〉表示一條漢米爾頓迴圈。我們證明出Q(k,n)有2n條漢米爾頓迴圈，記為Cl=〈v(1),vl(2),…,vl(N),v(1)〉，其中0≤ l ≤ 2n-1，且當l≠l' 時，對所有2≤ i ≤N， vl(i)≠vl'(i)。因為此處的Q(k,n)每個頂點恰好有2n個鄰點，這已為最佳的結果。

關鍵字

二部的 ； 超立方體 ； 漢米爾頓的

並列摘要

The k-ary n-cube has been used as the underlying topology for many practical multicomputers, and has been extensively studied in the past. In this thesis, we will prove that any k-ary n-cube Q(k,n), where n ≥ 2 is an integer and k ≥ 4 is an even integer, contains 2n mutually independent Hamiltonian cycles. More specifically, let N =∣V(Q(k,n))|, v(i)∈V(Q(k,n)) for 1 ≤ i ≤ N, and ⟨v(1), v(2),…, v(N), v(1)⟩ be a Hamiltonian cycle of Q(k,n). We prove that Q(k,n) contains 2n Hamiltonian cycles, denoted by Cl = ⟨v(1); vl(2),…, vl(N), v(1)⟩ for all 0 ≤ l ≤ 2n−1, such that vl(i)≠ vl′(i) for all 2 ≤ i ≤ N whenever l≠l′. The result is optimal since each vertex of Q(k,n) has exactly 2n neighbors.

並列關鍵字

Hamiltonian ； bipartite ； hypercubes

參考文獻

[1] B. Bose, B. Broeg, Y. Kwon and Y. Ashir, Lee distance and topological properties of k-ary n-cubes, IEEE Trans. on Comput. 44(1995), no. 8, 1021-1030.

[2] S. Bettayeb, On the k-ary hypercube, Theor. Comput. Sci. 140(1995), 333-339.

[3] C.H. Tsai, Linear array and ring embeddings in conditional faulty hypercubes, Theor. Comput. Sci. 314(2004), 31-43.

[4] J. Fink, Perfect matchings extend to Hamilton cycles in hypercubes, J. of Comb. Theory, Series B 97(2007), 1074-1076.

[5] F. Harary, J.P. Hayes and H.J. Wu, A survey of the theory of the hypercube graphs, Comput. Math. with Appl. 15(1988), 277-289.