1、引言
設N和h是正整數,其中N ≥5,2≤h ≤N-1。N個節點的雙環網絡G\\(N;1,h\\)是如下定義的有向圖:其節點集為ZN={0,1,…,N -1},邊集為E={i→i+1\\(mod N\\),i→i+h\\(mod N\\)|i∈ZN}。雙環網絡由于其點對稱性、連通性、易擴展性且具有一定的容錯能力,已廣泛地應用于局域網和計算機分布式系統的設計中。最優雙環網絡設計、雙環網絡的尋徑策略研究及其網絡的直徑估計及計算一直是受到關注的研究課題。
信息路由是通信網絡的基本功能。若每個信息總是沿著從信源到信宿的最短路經傳送,則稱為最優信息路由。對于雙環網絡G\\(N;1,h\\),文獻[6]給出了2≤h≤ 槡N +1時任意兩點間最短路徑的一個非常簡便的算法。文獻[4]提出了“非正常節點”概念,提出的尋徑策略是預先存儲0~h所有“非正常節點”編號及節點0到這些節點的最短路徑,以便提高尋徑效率。文獻[5]也對0~h的“非正常節點”進行了研究,并給出了在滿足某些條件的情況下,G\\(N;1,h\\)在區間 \\(0,h\\)內不存在“非平常節點”,并給出了類似于文獻[4]的尋徑策略。
本文對在什么情況下,G\\(N;1,h\\)在區間 \\(0,h\\)內不存在“非平常節點”,什么情況下存在“非平常節點”進行了研究。給出了雙環網絡G\\(N;1,h\\)在區間 \\(0,h\\)內不存在“非平常節點”的充分必要條件,并得到了它的兩個應用:\\(1\\)給出一類有向雙環網絡的單播路由算法,這個算法是簡單且最優的;\\(2\\)給出了這類有向雙環網絡的直徑公式。另外,指出了文獻[5]中兩個推論的紕漏。
2、定義及引理
網絡中兩個節點i與j間的距離d\\(i,j\\)定義為從i到j的最短路徑的長度。網絡的直徑指的是網絡中所有點對之間距離的最大者。用D\\(N;1,h\\)表示雙環網絡G\\(N;1,h\\)的直徑。因為雙環網絡是點對稱性的,所以D\\(N;1,h\\)= max{d\\(i,j\\)|0≤i,j 給定G\\(N;1,h\\),從點i到i+1的邊稱為[+1]邊,從點i到i+h的邊稱為[+h]邊?？紤]一條從i到j的路徑,它包含[+1]邊、[+h]邊的個數分別為x、y\\(x、y均為非負整數\\),則有j≡\\(i+x+yh\\)\\(mod N\\),等式成立與邊出現的順序無關,我們可把此路徑記為x[+1]+y[+h]。 下面的三個定義來自文獻。 定義1若存在整數x,使得x[+1]是0到v\\(0 考慮0到v\\(0 定義3稱以下節點為節點0所對應的“非平常節點”:0到它們的[+h]邊優先最短路徑正好就是它們的單一[+h]邊最短路徑。比如,雙環網絡G\\(26;1,11\\)中節點0所對應的“非平常節點”為:7,11,18,22。在區間\\(0,11\\)內節點0所對應的“非平常節點”為7。0到7的最短路徑是3[+11],路徑長度為3。 下面將給出關于節點0所對應的“非平常節點”的若干性質。為了方便起見,把G\\(N;1,h\\)中在區間 \\(0,h\\)內節點0所對應的“非平常節點”簡稱為在區間 \\(0,h\\)內的“非平常節點”。比如,網絡G\\(26;1,11\\)中,在區間\\(0,11\\)內的“非平常節點”為7。 以下總設N、p、h為正整數,且N ≥5,p≥1,h≥2,q為非負整數,0≤q≤h-1。 引理1給定雙環網絡G\\(N;1,h\\),其中N =ph+q,0≤q≤h-1,則G\\(N;1,h\\)在區間 \\(0,h\\)內至少存在一個“非平常節點”的充分必要條件是存在兩個正整數x、xh,使得x ≤xh 另一方面,若存在兩個正整數x、xh使得式\\(1\\)成立:x≤xh \\(1\\)當i=0時,則有jh≡xh\\(mod N\\)且j \\(2\\)當i>0時,則有xh≡i+jh\\(mod N\\),即jh ≡xh-i\\(mod N\\)且j 從上可知,0[+1]+x[+h]是0到xh的一條最短路徑,它也是單一[+h]邊最短路徑,即xh是G\\(N;1,h\\)在區間 \\(0,h\\)內的一個“非平常節點”。 3、主要定理 這一節將對在什么情況下,G\\(N;1,h\\)在區間\\(0,h\\)內不存在“非平常節點”,什么情況下存在“非平常節點”進行研究。定理1給定雙環網絡G\\(N;1,h\\),設N =ph+q,1≤q≤h-1,若p+q≥h,則G\\(N;1,h\\)在區間 \\(0,h\\)內不存在“非平常節點”。證明令t=p+q-h≥0,則有N +p-t=\\(p+1\\)h。用反證法,若在區間 \\(0,h\\)內有一個“非平常節點”,則存在兩個正整數x、xh,使得x≤xh \\(1\\)當r=0,由式\\(3\\)可得xh=l\\(p-t\\),因此x=l\\(p+1\\)+r>xh,這與x≤xh的假設矛盾! \\(2\\)當1≤r \\(3\\)當r=p,由式\\(3\\)可得l\\(p-t\\)+ph+q≡xh+q\\(mod N\\),即l\\(p-t\\)≡xh+q\\(mod N\\)。 因此l\\(p-t\\)=xh+q,從而xh 定理2給定雙環網絡G\\(N;1,h\\),若N =ph,則G\\(N;1,h\\)在區間 \\(0,h\\)內不存在“非平常節點”。證明用反證法,若在區間 \\(0,h\\)內有一個“非平常節點”,則存在兩個正整數x、xh,使得x≤xh 推論1給定雙環網絡G\\(N;1,h\\),設N =ph+q,0≤q≤h-1,當h≤ 槡N時,G\\(N;1,h\\)在區間 \\(0,h\\)內不存在“非平常節點”。證明當q=0時,由定理2可知,G\\(N;1,h\\)在區間 \\(0,h\\)內不存在“非平常節點”。當q>0時,因為p=\\(N-q\\)/h>\\(N-h\\)/h=N/h-1≥h-1,所以有1≤q≤h-1且p+q≥h。由定理1可知,G\\(N;1,h\\)在區間 \\(0,h\\)內不存在“非平常節點”。 推論2對于給定的正整數N ≥5,令s=槡N,h=s+1。若N ≠s2,則G\\(N;1,h\\)在區間 \\(0,h\\)內不存在“非平常節點”。證明設N =ph+q,0≤q≤h-1。因為N ≠s2,所以可把N分為下列四種情形進行討論: \\(1\\)當N =s2+r,1≤r \\(2\\)當N =s2+s時,可得N =s\\(s+1\\),即p=s,q=0。 \\(3\\)當N =s2+s+r,1≤r \\(4\\)當N =s2+2s時,可得N =s\\(s+1\\)+s,即p=s,q=s。此時p+q=2s=h+s-1≥h。 對于上面的第\\(1\\)、\\(3\\)、\\(4\\)三種情形,均有p+q≥h,由定理1可知在這三種情形下,G\\(N;1,h\\)在區間 \\(0,h\\)內不存在“非平常節點”。對于上面的第\\(2\\)種情形,因為q=0,由定理2可知在這種情形下,G\\(N;1,h\\)在區間 \\(0,h\\)內也不存在“非平常節點”。 引理2給定雙環網絡G\\(N;1,h\\),設N =ph+q,1≤q≤h-1,若p+q≤h-1,則G\\(N;1,h\\)在區間 \\(0,h\\)內至少存在一個 “非平常節點”。證明因為p+q≤h-1且1≤q≤h-1,所以有p+1≤h-q 由定理1、定理2及引理2,可得如下的定理3。 定理3給定雙環網絡G\\(N;1,h\\),設N =ph+q,0≤q≤h-1,則G\\(N;1,h\\)在區間 \\(0,h\\)內不存在“非平常節點”的充分必要條件是q=0或1≤q≤h-1且p+q≥h。4兩個應用這一節將利用上一節得到的結論,給出它們的兩個應用:\\(1\\)當G\\(N;1,h\\)在區間 \\(0,h\\)內不存在“非平常節點”時,其直徑公式特別簡單。\\(2\\)當G\\(N;1,h\\)在區間 \\(0,h\\)內不存在“非平常節點”時,我們將給出一個簡單且最優的單播路由算法,此算法適用的范圍大于文獻[6]給出的范圍\\(僅有一種情況除外\\)。引理3給定雙環網絡G\\(N;1,h\\),設N =ph+q,0 ≤q ≤h-1,則G\\(N;1,h\\)的直徑D\\(N;1,h\\)≤p+h-2。 證明當0≤j≤\\(p-1\\)h+h-1時,設j=xh+y,其中0≤y≤h-1,則有x≤p-1,y≤h-1。注意到y[+1]+x[+h]是0到j的一條路徑,因此有d\\(0,j\\)≤x+y≤p+h-2。當ph ≤j≤ N-1=ph+q-1時,設j=ph+y,其中0≤y≤q-1,注意到y[+1]+p[+h]是0到j的一條路徑,因此有d\\(0,j\\)≤p+y≤p+q-1≤p+h-2。 由上可知,D\\(N;1,h\\)= max{d\\(0,j\\)|0≤j< N}≤p+h-2?！醵ɡ?給定雙環網絡G\\(N;1,h\\),設N =ph+q,0≤q≤ h-1,若G\\(N;1,h\\)在區間 \\(0,h\\)內不存在“非平常節點”\\(即q=0或1≤q≤h-1且p +q ≥ h\\),則G\\(N;1,h\\)的 直 徑 為D\\(N;1,h\\)=p+h-2。 證明先證 \\(h-1\\)[+1]+\\(p-1\\)[+h]是0到 \\(p-1\\)h+h-1=ph-1的一條最短路徑。用反證法,若它不是最短路徑,假設x[+1]+y[+h]\\(其中0≤x 從上可知,\\(h-1\\)[+1]+\\(p-1\\)[+h]是0到ph-1的一條最短路徑,從而有d\\(0,ph-1\\)=p+h-2。這樣可得,D\\(N;1,h\\)= max{d\\(0,j\\)|0≤j< N}≥d\\(0,ph-1\\)=p+h-2。 由引理3,D\\(N;1,h\\)≤p+h-2,即可得D\\(N;1,h\\)=p+h-2?！鯊耐普?和推論2可知,此定理拓廣了文獻[6]中定理5的范圍\\(僅有一種情況G\\(s2;1,s+1\\)除外\\)。比如,雙環網絡G\\(42;1,9\\)的步長9大于槡42 +1=7,它不在文獻[6]中定理5所確定的范圍。然而,因為42=4×9+6,4+6>9,據定理4可知,雙環網絡G\\(42;1,9\\)的直徑等于4+9-2=11。 文獻中的兩個推論有誤,現舉例說明之。文獻中的推論2有誤。取h =100,p =100,q=99,N =10099。所給的雙環網絡符合推論2的 條 件,按 照 推 論2的 公 式,雙 環 網 絡G\\(10099;1,100\\)的直徑為max{p-1+h-1,p+q}= max{198,199}=199。 然而根據定理4,雙環網絡G\\(10099;1,100\\)的直徑應為p+h-2=100+100-2=198。文獻[5]中的推論3有誤。為了討論方便起見,現把其摘錄如下:“推論3在G\\(N;1,h\\)中,當d >p+h-2時,則在0→h內至少存在一個‘非平常節點’\\(其中d指的是網絡G\\(N;1,h\\)的直徑\\)?！睆囊?可知,不管在什么情況下,雙環網絡G\\(N;1,h\\)的直徑是小于或等于p+h-2,不可能出現G\\(N;1,h\\)直徑大于p+h-2的情況,因此推論3所給的條件是沒有意義的。 定理5給定雙環網絡G\\(N;1,h\\),設N =ph+q,0≤q≤h-1,當G\\(N;1,h\\)在區間 \\(0,h\\)內不存在“非平常節點”時\\(即q=0或1≤q≤h-1且p+q≥h\\),G\\(N;1,h\\)存在簡單且最優的單播路由算法:從0到v\\(其中1≤v≤ N -1,v=mh+n,0≤m≤p,0≤n 證明用反證法,若n[+1]+m[+h]不是最短路徑,假設x[+1]+y[+h]\\(其中0≤x 情形1 y>m。由mh+n≡yh+x\\(mod N\\)及x+y 情形2 y=m。由mh+n≡yh+x\\(mod N\\)及x+y 情形3 y < m。若x ≤n,則由mh+n ≡yh+x\\(mod N\\),可得 \\(m-y\\)h+n-x≡0\\(modN\\)。即0<\\(m-y\\)h+n-x=kN,k≥1,這與0<\\(m-y\\)h+n-x≤mh+n=v □從第2節的推論1和推論2可以看出,定理5給出的單播路由算法適用的范圍大于文獻[6]給出的范圍\\(僅有一種情況G\\(s2;1,s+1\\)除外\\),也就是說,文獻算法適用的范圍比定理5的范圍更狹隘一些。比如,雙環網絡G\\(42;1,9\\)的步長9大于槡42 +1=7,它不在文獻[6]中所確定的步長范圍內。然而,因為42=4×9+6,4+6>9,據定理1可知,G\\(42;1,9\\)在區間\\(0,9\\)內不存在“非平常節點”。從定理5可知其存在簡單且最優的單播路由算法。 求雙環網絡G\\(42;1,9\\)中從節點21到節點3的最短路徑。因為3-21≡24\\(mod 42\\),24=2×9+6,所以從節點21到節點3的最短路徑是6[+1]+2[+9],即21→30→39→40→41→0→1→2→3。 5、結束語 本文給出了有向雙環網絡G\\(N;1,h\\)在區間\\(0,h\\)內不存在“非平常節點”的一個充分必要條件,并得到了它的兩個應用:\\(1\\)給出一類有向雙環網絡的單播路由算法,這個算法是簡單且最優的,此單播路由算法適用的范圍大于文獻[6]給出的范圍\\(僅有一種情況G\\(s2;1,s+1\\)除外\\);\\(2\\)給出了這類有向雙環網絡的直徑公式。對存在“非平常節點”的情形,下一步的工作將確定有向雙環網絡G\\(N;1,h\\)在區間 \\(0,h\\)內的“非平常節點”。
