基于Cayley圖的互連網(wǎng)絡(luò)的研究.pdf

1、眾所周知，凱萊圖在計算機局域網(wǎng)及大規(guī)模并行處理系統(tǒng)的設(shè)計與分析中起著重要的作用。超立方體網(wǎng)絡(luò)，雙環(huán)網(wǎng)絡(luò)，星圖等都是凱萊圖。全文共分為五章，圍繞凱萊網(wǎng)絡(luò)中以下兩部分的重要課題進行討論：1．雙環(huán)網(wǎng)絡(luò)的尋徑策略與最優(yōu)設(shè)計；2．交錯群網(wǎng)絡(luò)與洗牌交換置換網(wǎng)絡(luò)的路由算法。下面是本文的一些主要結(jié)果： 1．本文給出了一個方法用于構(gòu)造k-緊優(yōu)無限族(k≥1)，并用此方法構(gòu)造出了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．本文給出了一個方法用于構(gòu)造奇異1-緊優(yōu)無限族。用此方法構(gòu)造出3族奇異1-緊優(yōu)無限族及1族奇異2-緊優(yōu)無限族。 3．利用預(yù)先計算出來的L-形瓦的四個參數(shù)及同余方程s_1x+s_2y≡1(modn)的一個解，我們給出了有向雙環(huán)網(wǎng)絡(luò)G(n；s_1，s_2)的時間復(fù)雜性為常數(shù)的最優(yōu)路由算法