|
依據Akers 及Krishnamurthy 所提出的群論模式, 我們以建造出許多有用的群圖綱路
。這類的架構具有對稱性, 而建出之綱路的擁擠度問題可以減低。各個處理機可以有
相同之繞徑策略, 易於設計演算法。在這算論文之中我們討論群圖綱路的容錯度。我
們將視綱路之容錯度為兩部分: 第一部分是移去最多之連線而綱路而連通; 第二部分
是移去最多之頂點而綱路仍連通。在我們所研究的群圖綱路SHCG(Strongly Hierarch
ical Cayley Craph)中, 我們將證明這類綱路具有最佳之容錯度, 也就是: 如果每個
頂點連接出d 條線的話, 則綱路的連線容錯度是d-1 , 而且頂點的容錯度也是d-1 。
此外, 我們也討論其他情況: 生成單元(generator) 可以是互為轉置(inverse) 或生
成單元可以重複。在第一種情況中, 我們證明: 綱路的連線容錯度是最佳的。而在第
二種情況中, 我們將證明: 如果生成單元的重複次數一樣多的話, 綱路的連線容錯度
也是最佳的。
|