容錯標誌環嵌入雙迴路網路

Abstract

一個雙迴路網路G(n;s1,s2)是一個由n個點{0,1,...,n-1}和2n個i->i+s1 (mod n)和i->i+s2 (mod n)邊所組成的有向圖。假如在雙迴路網路中任意 去掉一個邊還存在一個hamiltonian cycle,我們稱此雙迴路網路G(n;s1, s2)為LFT。相同地, 假如在雙迴路網路中任意去掉一個點還存在一個 hamiltonian cycle,我們稱此雙迴路網路 G(n;s1,s2)為NFT。在本篇論文 中,我們對於LFT和NFT的雙迴路網路提出充分必要的條件。 A double loop network G(n;s1,s2) is a digraph with n nodes{0, 1,..., n-1} and 2n links of the form i->i+s1 (mod n)andi ->i+s2 (mod n). A double loop network G(n;s1,s2) is LFTif there is a hamiltonian cycle in every G(n;s1,s2) - e wheree is any link in the network. Similarly, a double loop network G(n;s1,s2) is NFT if there is a hamiltonian cycle in everyG(n;s1,s2) - v where v is a node in the network. In this paper,we present necessary and sufficient conditions for LFT and NFTdouble loop networks, respectively.