朱 琦

吉林工商學(xué)院信息工程學(xué)院，吉林長春 136200

無向雙環(huán)網(wǎng)絡(luò)的節(jié)點故障出現(xiàn)在保證網(wǎng)絡(luò)節(jié)點間的路由是一個非常重要的問題。如果按照最短的路徑訪問方式而映射到直角坐標系會形成最優(yōu)的路由構(gòu)圖CG(N; ±r，±s)，針對故障節(jié)點的封閉區(qū)和逃選區(qū)，仍然可以進行最優(yōu)路由。

1 無向雙環(huán)網(wǎng)絡(luò)設(shè)計定理

我們來舉個例子，如果a=84,若b=89,u=102；v=68 的話，x=0;y 是基數(shù)并且滿足定理的條件，這時，x=0,y=3，b-a=5 ≠y,b-a=5 ≠y-2,所以，這樣的形式是不可成立的。

1）雙環(huán)網(wǎng)絡(luò)G（N；r，s）有N個結(jié)點0，1，2，…，N－1，而且是從每個結(jié)點i發(fā)出兩條有向邊i→i＋r（m odN）和i→i＋s（modN其中1≤r≠s〈N。有一個這樣的問題：對于給定的N，如何選取r和s使得G（N；r，s）有最小的直徑呢，我們就根據(jù)r＝1的特殊情形想到一個方法，并且構(gòu)造出最小直徑是不會在r＝1的情況下達到的雙環(huán)網(wǎng)絡(luò)無限族，同時指出了錯誤；

2）早在1987 年就有人證明一般的雙環(huán)網(wǎng)絡(luò)G（N;r,s）是成立的，而此時，大家通過網(wǎng)絡(luò)搜索發(fā)現(xiàn)到，N 是存在的，最小值竟然是450，事實上d1(450)=36，而且G（450；1,59）是優(yōu)的。有很多方法都可以構(gòu)造出含有奇異無線子族的緊優(yōu)雙環(huán)的網(wǎng)絡(luò)無線族是優(yōu)2 種情形發(fā)生的，第一種情況就是已經(jīng)知道某個奇異緊優(yōu)的雙環(huán)網(wǎng)絡(luò)G(No;ro,so)為了起始的元素緊優(yōu)的雙環(huán)網(wǎng)絡(luò)無線族，使之其中的一個奇異無限子族在起始元素未知的情況下構(gòu)造出一個含有奇異無限子族的緊優(yōu)雙環(huán)網(wǎng)絡(luò)無限族；

3）無向雙環(huán)網(wǎng)絡(luò)的構(gòu)造簡單而且具有規(guī)則性、對稱性和可擴性，所以在計算機互聯(lián)網(wǎng)可以得到廣泛的應(yīng)用，是非常重要的，它可以用直徑去度量，目前已經(jīng)找到了大量的含有緊優(yōu)的雙環(huán)網(wǎng)絡(luò)無限族，早在1993 年的時候，人們就提出關(guān)于給定的K ＞1 并且找出了無向緊優(yōu)雙環(huán)網(wǎng)絡(luò)的無限族，對給定的正整數(shù)n,給出了一個全新的算法用來無向雙環(huán)網(wǎng)絡(luò)的最優(yōu)步長s,使之無向雙環(huán)網(wǎng)絡(luò)G(n；±1,±s)的直徑最短，無向雙環(huán)網(wǎng)絡(luò)G(2t2－B；±1,±s)及無向雙環(huán)網(wǎng)絡(luò)G(2t2－2；±1,±s)緊優(yōu)的充分必要條件；

4）有一種仿真算法：（1 小邊；s 為大邊；N 為節(jié)點數(shù))但是不足的是利用數(shù)據(jù)庫去采取中間的結(jié)果，N 很大的時候計算時間就會長，不利于N 值緊優(yōu)雙環(huán)網(wǎng)絡(luò)的分析。針對這個問題，應(yīng)該提出一個非常有效的仿真法，根據(jù)存取的結(jié)果，再加上這樣的算法很快會研究到G(N；±1,±s)緊優(yōu)分布的特性計算出了4 ≤N ≤1 000 當中的任意節(jié)點數(shù)N 的緊優(yōu)無向雙環(huán)網(wǎng)絡(luò)個數(shù)n；仿真此時的n-N 緊優(yōu)分布率和n/(N-3)-N 緊優(yōu)分布率；計算4 ≤N ≤1 000 中不存在緊優(yōu)無向雙環(huán)網(wǎng)絡(luò)的N 值；

5）雙環(huán)網(wǎng)的尋徑是當前關(guān)注較多的課題。主要是關(guān)于同一個雙環(huán)網(wǎng)在兩個不同節(jié)點間的運算情況,其算法則需要完成的時間為O(△),其中△是該網(wǎng)絡(luò)的直徑。雙環(huán)網(wǎng)絡(luò)已經(jīng)是一個很重要的互聯(lián)網(wǎng)絡(luò)結(jié)構(gòu)了，最傳統(tǒng)的優(yōu)尋徑方法并沒有利用網(wǎng)絡(luò)中同一節(jié)點和不同節(jié)點的最短路徑之間的關(guān)系，所以給的算法不是最優(yōu)的，定義了雙環(huán)網(wǎng)絡(luò)的一種最短路徑—— [+ 1]邊優(yōu)先最短路徑，在這樣的形式下，最短的路徑形式已成為唯一，況且同一個源節(jié)點和不同目的節(jié)點的最短的路徑存在著遞推的聯(lián)系，并且給出了相應(yīng)的遞推公式。運用這個公式，平均不到兩次的加法運算和一次比較就能找到源節(jié)點至所有其它節(jié)點的最短路徑。再利用所得的結(jié)果，源節(jié)點只用儲很少的信息就能經(jīng)過簡單的計算求得到其它節(jié)點的最短路徑。和傳統(tǒng)的方法比較起來，這種算法已經(jīng)提高了系統(tǒng)的尋徑效率設(shè)n=qh+r,這里1 ≤r ≤h-1,w=「(h-1)/(q+r)；

6）2hn.（雙環(huán)網(wǎng)絡(luò)),(hnD 是如下定義的有向圖：其結(jié)點集是}1,1,0{-=nZnL, 邊集是}10：)(mod),(mod1{-++=ninhiiniiE.設(shè)rhrqhwhrrqhn/)其中，源結(jié)點至目的結(jié)點最短路徑的算法，這樣的算法最多只要2 次的算術(shù)運算和一次比較，各結(jié)點沒有必要先存儲網(wǎng)絡(luò)中其他信息，而是可以提出新的緊優(yōu)雙環(huán)網(wǎng)絡(luò)無限族的構(gòu)造方法，這種構(gòu)造不含k(0 ≤k ≤m)緊優(yōu)雙環(huán)網(wǎng)絡(luò)的無限族。從一個可以表現(xiàn)具體的實現(xiàn)L 形瓦出發(fā)，利用h 和y 互素條件，構(gòu)造就能實現(xiàn)L 形瓦的無限族，給出的7 緊優(yōu)、8 緊優(yōu)雙環(huán)網(wǎng)絡(luò)的無限族，并且解決好幾個關(guān)于緊優(yōu)雙環(huán)網(wǎng)絡(luò)無限族的公開問題，雙環(huán)網(wǎng)絡(luò)G(N ;r,s)有N 個結(jié)點 0,1,2，… ,N - 1,并從從每個結(jié)點i 發(fā)出兩條有向邊i →i +r(modN)和i →i+s(modN) ,其中 1 ≤r ≠s N。有一個問題是對于給定的N，如何選取r 和s 使得G(N ;r,s)有最小直徑，這就可以在特殊計算環(huán)境下使用數(shù)值定義的方法。可以對最小直徑超出r=1 的的相關(guān)雙環(huán)網(wǎng)絡(luò)無限族進行擴大和利用；

7）先利用之前計算出來的L-形瓦的四個參數(shù)及同余方程s_1x+s_2y ≡1(mod n)的一個解，并且給出有向雙環(huán)網(wǎng)絡(luò)G(n；s_1，s_2)的時間復(fù)雜性作為常數(shù)的最優(yōu)路由算法。也就是說，經(jīng)過常數(shù)時間的計算就可以得到任意兩點間的一條最短的路徑。如果n 是一個定值整數(shù)，使用數(shù)據(jù)算法對k-緊優(yōu)的雙環(huán)網(wǎng)絡(luò)G(n；1，s)進行運算，該種算法公式具有一定的時間復(fù)雜性O(shè)(k～(2.5)n～(0.25)log n)。利用已知變量L-形瓦的相關(guān)參數(shù)原理和同余方程s_1x+s_2y ≡1(mod n)得出一個最優(yōu)解，從而可以得知雙環(huán)網(wǎng)絡(luò)G(n；±s_1，±s_2)的時間復(fù)雜性計算的最優(yōu)時間計算方法。也可以通過基本常數(shù)運算對兩個所求點的最短距離進行精確化運算。

2 結(jié)論

相信很多的企業(yè)在網(wǎng)絡(luò)方面還不是非常完善，目前，計算機雙環(huán)網(wǎng)絡(luò)已經(jīng)占據(jù)了不可替代的地位，而且聰明的人們還給出了交錯群網(wǎng)絡(luò)AN_n 的一個最優(yōu)路由算法和洗牌交換置換網(wǎng)絡(luò)SEP_n 的全新路由運算方法，并給出了SEP_n 直徑下的一個人新型發(fā)展途徑。

[1]李靜，王子瀟.最優(yōu)的雙環(huán)網(wǎng)絡(luò)無限族[J].中國科學(xué)，2010(4).

[2]沈康.關(guān)于雙環(huán)網(wǎng)絡(luò)的定理[J].中國科學(xué)技術(shù)學(xué)報，2012(8).

[3]徐嬌，汪斌，張國棟.仿真法[M].中國科學(xué)技術(shù)大學(xué)出版社，2011(7).