臺灣博碩士論文加值系統

一般化費氏立方體 ( GFCs ) 是最近才被提出的一種互連布局的集合,它
所涵括的範圍從規則圖形如多立方體到半規則圖形, 如二階費氏立方體
。 現並已被指出, 當 0 .ltoreq. n < k 時 n + k 維的 k 階 GFC 相
當於 n 維的多立方體; 而當 n .gtoreq. k 時, 則是其子圖形。如此,
在所有 n .gtoreq. k 的情形下, 從 n 維的多立方體中移去一些特定的
節點可以得到一個 n + k 維的 k 階 GFC 。 在沒有錯誤點的情況在這是
一個非常簡單的問題, 但是當有錯誤點存在時則變得非常複雜。首先, 在
這篇論文中, 我們要考慮以下這個問題: 如何在一個最大的 ( 就節點數
而言 ) 的一般化中費氏立方體, 這同時也可視為一個在多立方體中的容
錯嵌入問題。然後, 我們將說明如何將一個 GFC 直接地嵌入一個錯誤的
多立方體中, 並且證明若沒有超過三個錯誤節點出現, 當 n = 4 或 n
.gtoreq. 6, 在最差的情況下 , 可以將一個 n + [ n / 2 ] 維的 [ n
/ 2 ] 階 GFC 直接嵌入一個 n 維的多立方體。

The generalized Fibonacci cubes ( abbreviated to GFCs ) were
recently proposed as a class of interconnection topologies,
which cover a spectrum ranging from regular graphs such as
the hypercube to semi-regular graphs such as the second
order Fibonacci cube. It has been shown that the kth order
GFC of dimension n + k is equivalent to an n cube for 0
.ltoreq. n < k; and it is a proper subgraph of an n-cube for n.
gtoreq. k. Thus, a kth order GFC of dimension n + k can be
obtained from the n-cube for all n.gtoreq. k by removing
certain nodes from an n-cube. This problem is very simple
when no faulty node exists in an n-cube; but it becomes very
complex if some faulty nodes appear in an n-cube. In this
paper, first, we concern the following open problem: How to
identify a maximal ( in terms of the number of nodes )
generalized Fibonacci cube from a faulty hypercube which can
also be considered as a Fault-tolerant embedding in
hypercubes. Then, we shall show how to directly embed a GFC
into a faulty hypercube and prove that if no more than three
faulty nodes, then an [ n / 2 ]th order GFC of dimension n + [
n / 2 ] can be directly embedded into an n-cube in the
worst case, for n = 4 or n.gtoreq. 6.