有錯蝴蝶圖中環型圖之嵌入

Abstract

圍繞型蝴蝶圖 BFn 已定義在 Leighton 所寫的書中,其擁有許多很好的性質,包括正則性,對稱性,最大連通性,漢彌爾頓圖,漢彌爾頓圖分解及直徑為log(|BFn|)等等 ◦ 因為 BFn 每個點的自由度都固定為四,為了要建構漢彌爾頓環路,最多只能容忍有兩個錯誤 ◦ 在這篇論文中,當n是偶數且 BFn 最多發生兩個錯誤時,我們證明它包含一個長度為 N-2f 的環路, N 代表圖的所有點數, f 則是壞點的個數 ◦ 當n是奇數,我們證明 BFn 在擁有兩個錯誤的情況下還包含一個漢彌爾頓環路 ◦

The wrapped butterfly network BFn is defined in the book written by Leighton [1] which has a lot of good properties including regularity, symmetry, logarithmic diameter, maximal connectivity, hamiltonian, hamiltonian decomposable, etc. Since BFn is regular of degree four, it can tolerate at most two faults in the worst case in order to construct a hamiltonian cycle. In this paper, we prove that the graph BFn contains a cycle of length N-2f even if it has at most two faults where n is an even integer, f is the number of faulty nodes, and N is the cardinality of BFn. Additionally, we prove that BFn contains a hamiltonian cycle after removing at most two faults (even edges and/or nodes) if n is an odd integer.