基于Cayley圖的互連網絡的研究.pdf

1、眾所周知，凱萊圖在計算機局域網及大規(guī)模并行處理系統(tǒng)的設計與分析中起著重要的作用。超立方體網絡，雙環(huán)網絡，星圖等都是凱萊圖。全文共分為五章，圍繞凱萊網絡中以下兩部分的重要課題進行討論：1．雙環(huán)網絡的尋徑策略與最優(yōu)設計；2．交錯群網絡與洗牌交換置換網絡的路由算法。下面是本文的一些主要結果： 1．本文給出了一個方法用于構造k-緊優(yōu)無限族(k≥1)，并用此方法構造出了4族3-緊優(yōu)無限族，3族新的4-緊優(yōu)無限族，3族5-緊優(yōu)無限族及2族6

2、-緊優(yōu)無限族。另外利用計算機搜索還找到了27族新的0-緊優(yōu)無限族，26族新的1-緊優(yōu)無限族，8族新的2-緊優(yōu)無限族，2族3-緊優(yōu)無限族。 2．本文給出了一個方法用于構造奇異1-緊優(yōu)無限族。用此方法構造出3族奇異1-緊優(yōu)無限族及1族奇異2-緊優(yōu)無限族。 3．利用預先計算出來的L-形瓦的四個參數(shù)及同余方程s_1x+s_2y≡1(modn)的一個解，我們給出了有向雙環(huán)網絡G(n；s_1，s_2)的時間復雜性為常數(shù)的最優(yōu)路由算法