排列圖上的獨立漢米爾頓迴圈

Mutually Independent Hamiltonian Cycles on Arrangement Graphs

林政達(Cheng-Da Lin)

指導教授 ： 高欣欣

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

https://doi.org/10.6840/cycu201100748

摘要

排列圖An;k過去曾被使用於平行網路上面的拓樸性質,並且有非常廣泛的研究。
在本篇文章中，我們將證明n ¡ k ¸ 3, k ¸ 2，An;k會包含k(n ¡ k)條相互獨立的漢米爾頓迴圈。　特別地來說，我們假設N =j V (An;k) j, v(i) 2 V (An;k)當1 · i · N而且hv(1); v(2); ¢ ¢ ¢ ; v(N); v(1)i是一條在An;k中的漢米爾頓迴圈，我們將證明An;k包含了k(n ¡ k)條相互獨立的漢米爾頓迴圈，並且表示成Cl = hv(1); vl(2); ¢ ¢ ¢ ; vl(N); v(1)i對所有的1 · l · k(n ¡ k)，使得vl(i) 6= vl0 (i)對於所有2 · i · N的當l 6= l0。因為每個An;k在的點都有個鄰點，所以這是最佳的結果。

關鍵字

相互獨立 ； 漢米爾頓迴圈 ； 排列圖

並列摘要

The arrangement graph An;k, has been used as the underlying topology for many practi-
cal multicomputers, and has been extensively studied in the past. In this thesis, we will
prove that any An;k where n ¡ k ¸ 3, k ¸ 2, contains k(n ¡ k) mutually independent
hamiltonian cycles. More speci¯cally, let N =j V (An;k) j, v(i) 2 V (An;k) for 1 · i · N
and hv(1); v(2); ¢ ¢ ¢ ; v(N); v(1)i be a hamiltonian cycle of An;k. We prove that An;k con-
tains k(n ¡ k) hamiltonian cycles, denoted by Cl = hv(1); vl(2); ¢ ¢ ¢ ; vl(N); v(1)i for all
1 · l · k(n ¡ k), such that vl(i) 6= vl0 (i) for all 2 · i · N whenever l 6= l0 . The result is
optimal since each vertex of An;k has exactly k(n ¡ k) neighbors.

並列關鍵字

mutually independent ； hamiltonain cycle ； arrangement graphs

參考文獻

[1] K. Day, and A. Tripathi (1992), Arrangemnet graphs: A class of generalized star

graphs, Inform. Processing Lett., No. 42:235{241.

[2] K. Day, and A. Tripathi (1993), Embedding of cycles in arrangement graphs, IEEE

Transactions on Computers, Vol. 42, No. 8:235{241.

[3] K. Day, and A. Tripathi (1993), Embedding grids, hypercubes, and trees in arrange-