亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        無向雙環(huán)網(wǎng)絡(luò)的強(qiáng)彩虹連通性

        2019-11-29 10:25:28陳寶興
        關(guān)鍵詞:上界雙環(huán)著色

        劉 杰,陳寶興

        (1.閩南師范大學(xué)計算機(jī)學(xué)院,福建 漳州 363000;2.三明醫(yī)學(xué)科技職業(yè)學(xué)院,福建 三明 365000;3.數(shù)據(jù)科學(xué)與智能應(yīng)用福建省高等學(xué)校重點實驗室,福建 漳州 363000)

        令G為一個非平凡的連通圖,連接圖G中的兩個頂點u和v的最短路徑的長度稱為u和v之間的距離,記為d(u,v).圖G中任意兩個頂點之間距離的最大值稱為圖G的直徑,記作D(G).在G上定義一個邊染色C:E(G)→{1,2,…,k},k∈N,其中相鄰的邊可能染同種顏色,如果一條路P上的邊分別染不同的顏色,則稱P是一條彩虹路.如果圖G任意兩個不同頂點之間都有一條彩虹路相連,則稱圖G是彩虹連通的.使得圖G彩虹連通所需要的最少顏色數(shù)稱為G的彩虹連通數(shù),記為rc(G).如果圖G的任意兩個不同頂點之間都有一條最短路徑是彩虹路,則稱圖G是強(qiáng)彩虹連通的.使得圖G強(qiáng)彩虹連通所需要的最少顏色數(shù)稱為G的強(qiáng)彩虹連通數(shù),記為src(G).

        圖的染色有廣泛的實際應(yīng)用,比如說學(xué)生選課系統(tǒng)、電路布局、排序問題、會議安排、電路安排、考試安排等,這些問題都與圖的染色理論密切相關(guān).雙環(huán)網(wǎng)絡(luò)是一種重要的計算機(jī)網(wǎng)絡(luò),它具有對稱性,且易于擴(kuò)展.與環(huán)狀網(wǎng)絡(luò)比較,它的直徑比較小,且有較好的容錯能力.雙環(huán)網(wǎng)絡(luò)在設(shè)計和構(gòu)建大中型網(wǎng)絡(luò)或者并行處理計算機(jī)系統(tǒng)中有著廣泛的應(yīng)用.雙環(huán)網(wǎng)絡(luò)的直徑估計與計算[1-5],構(gòu)造最優(yōu)雙環(huán)網(wǎng)絡(luò),以及雙環(huán)網(wǎng)絡(luò)的尋徑策略研究,曾經(jīng)受到不少學(xué)者的重視[6-10].在過去的幾年里,圖的彩虹連通著色[11-13]作為圖論中的一個新問題受到了廣泛的關(guān)注,它也被應(yīng)用到網(wǎng)絡(luò)信息安全與密碼學(xué)等領(lǐng)域.劉欣欣等[14]給出了有向雙環(huán)網(wǎng)絡(luò)彩虹連通的一個著色方案,從而得到了其彩虹連通數(shù)的一個上界.王燕等[15]研究了一類線性多邊形鏈的彩虹連通著色.本文中將對無向雙環(huán)網(wǎng)絡(luò)任意兩點之間的最短路徑進(jìn)行刻畫:證明任意兩點之間存在一條最短路徑W[+s1]+R[+s2],這里|W|

        1 定義及引理

        設(shè)1≤s1

        圖1 無向雙環(huán)網(wǎng)絡(luò)G(8;±1,±3)Fig.1 Undirected double loop network G(8; ±1, ±3)

        對于雙環(huán)網(wǎng)絡(luò)G(n;±s1,±s2),從點i到點(i+s1) (modn)的邊稱為[+s1]邊,點i到點(i-s1)(modn)的邊稱為[-s1]邊.點i到點(i+s2)(modn) 的邊稱為[+s2]邊,點i到點(i-s2)(modn) 的邊稱為[-s2]邊.若一條從點i到點j的路徑包含x1條[+s1]和x2條[-s1]邊,y1條[+s2]邊和y2條[-s2]邊,則有j≡(i+x1s1-x2s1+y1s2-y2s2)(modn),且等式成立與路徑中邊的順序無關(guān),將此路徑記為:x1[+s1]+x2[-s1]+y1[+s2]+y2[-s2].

        設(shè)i、j是G(n;±s1,±s2)中的兩個節(jié)點,x1[+s1]+x2[-s1]+y1[+s2]+y2[-s2]是一條從i到j(luò)的最短路徑,則x1與x2至少有一個為0,y1與y2至少一個為0.從i到j(luò)的最短路徑使用的邊僅含[+s1]與[+s2]或僅含[-s1]與[+s2],或僅含[+s1]與[-s2]或僅含[-s1]與[-s2].從i到j(luò)的最短路徑可記為:x[+s1]+y[+s2],這里x、y∈Z.

        Chen等[4]給出了由G(n;±s1,±s2)所確定的同余方程最小非負(fù)解和最小交叉解的定義,并給出了G(n;±s1,±s2)的直徑公式.

        定義1[4]稱格點(a1,a2)為同余式

        xs1+ys2≡0(modn)

        (1)

        的一個非負(fù)解,如果a1s1+a2s2≡0(modn),a1,a2∈Z+,并且(a1,a2)≠(0,0).

        稱(u,v)為同余式(1)的最小非負(fù)解,若它滿足以下條件:

        (i) (u,v)為同余式(1)的非負(fù)解.

        (ii) 同余式(1)的任意非負(fù)解(a1,a2),都有u+v≤a1+a2.

        (iii) 如果存在同余式(1)的非負(fù)解(a1,a2)≠(u,v)并且a1+a2=u+v,則有u>a1.

        定義2[4]稱格點(-a1,a2)為同余式(1)的交叉解,如果-a1s1+a2s2≡0(modn),a1、a2∈Z+,(-a1,a2)≠(0,0),并且(-a1,a2)、(0,0)、(u,v)三點不在同一直線上,其中(u,v)為同余式(1)的最小非負(fù)解.

        稱(-a,b)為同余式(1)的最小交叉解,若它滿足以下條件:

        (i) (-a,b)為同余式(1)的交叉解.

        (ii) 同余式(1)的任意交叉解(-a1,a2),都有a+b≤a1+a2.

        (iii) 如果同余式(1)存在交叉解(-a1,a2)≠(-a,b)并且a+b=a1+a2,則有b>a2.

        引理1[4]設(shè)(u,v)、(-a,b)分別是同余式(1)的最小非負(fù)解和最小交叉解.如果u≥v,則有a≤u、a≤b、v

        特別地,容易證明:如果u=v,則有a

        引理2[4]設(shè)(u,v),(-a,b)分別是同余式(1)的最小非負(fù)解和最小交叉解.如果uu,a>b,b

        引理3當(dāng)u=v時,對于0≤k≤n-1,G(n;±s1,±s2)中存在一條從0到k的最短路徑W[+s1]+R[+s2],滿足|W|

        證明對于0≤k≤n-1,若W[+s1]+R[+s2]是一條從0到k的最短路徑,則必有|R|

        用反證法,若|R|≥b,不妨設(shè)R≥b(R≤-b類似可證).由引理1可知,當(dāng)u=v時,有a

        若|W|≥u,不妨設(shè)W≥u(W≤-u類似可證).設(shè)W=iu+j,這里i、j∈Z,且0≤j≤u-1.注意到(W-iu)[+s1]+(R-iu)[+s2]也是一條從0到k的路徑,且|W-iu|+|R-iu|=W-iu+|R-iu|≤W-iu+|R|+iu=W+|R|.因此(W-iu)[+s1]+(R-iu)[+s2]也是一條從0到k的最短路徑且|W-iu|

        引理4當(dāng)u>v時,對于0≤k≤n-1,G(n;±s1,±s2)中存在一條從0到k的最短路徑W[+s1]+R[+s2],滿足|W|

        證明對于0≤k≤n-1,若W[+s1]+R[+s2]是一條從0到k的最短路徑,則必有|W|

        用反證法,若|W|≥u,不妨設(shè)W≥u(W≤-u類似可證).注意到(W-u)[+s1]+(R-v)[+s2]也是一條從0到k的路徑,且|W-u|+|R-v|=W-u+|R-v|≤W-u+|R|+v<|W|+|R|,這與W[+s1]+R[+s2]是一條從0到k的最短路徑矛盾.

        若|R|≥b,不妨設(shè)R≥b(R≤-b類似可證).設(shè)R=ib+j,這里i、j∈Z,且0≤j≤b-1.注意到(W+ia)[+s1]+(R-ib)[+s2]也是一條從0到k的路徑,且|W+ia|+|R-ib|=|W+ia|+R-ib≤|W|+ia+R-ib≤|W|+|R|,因此(W+ia)[+s1]+(R-ib)[+s2]也是一條從0到k的最短路徑且|W+ia|

        引理5當(dāng)u

        證明對于0≤k≤n-1,若W[+s1]+R[+s2]是一條從0到k的最短路徑,則必有|W|

        用反證法,若|W|≥a,不妨設(shè)W≥a(W≤-a類似可證).注意到(W-a)[+s1]+(R+b)[+s2]也是一條從0到k的路徑,且|W-a|+|R+b|=W-a+|R+b|≤W-a+|R|+b<|W|+|R|,這與W[+s1]+R[+s2]是一條從0到k的最短路徑矛盾.

        類似可證|R|

        令t1=max{u,a},t2=max{v,b},從引理3~5,可得引理6.

        引理6對于0≤k≤n-1,在G(n;±s1,±s2)中存在一條從0到k的最短路徑W[+s1]+R[+s2]滿足|W|

        無向環(huán)狀網(wǎng)絡(luò)G(n; ±s)是如下定義的無向圖(V(G),E(G)):節(jié)點集V(G)={0,1,2,…,n-1},邊集E(G)={i→i-s(modn),i→i+s(modn)|i=0,1,2,…,n-1}.注意到G(n;±s)是連通的當(dāng)且僅當(dāng)gcd(n,s)=1.當(dāng)gcd(n,s)=d>1時,無向環(huán)狀網(wǎng)絡(luò)是不連通的.此網(wǎng)絡(luò)有d個連通分量,節(jié)點0,1,2,…,n-1分別屬于這d個連通分量.

        引理8的證明與文獻(xiàn)[14]的引理1類似,這里略去.

        例1對于無向環(huán)狀網(wǎng)絡(luò)G(33;±12),取t=5,則用6種顏色對G(33;±12)邊著色,就可使得G(33;±12)中任一條長度不超過5的路徑均是一條彩虹路.

        2 主要結(jié)果

        下面將給出無向雙環(huán)網(wǎng)絡(luò)強(qiáng)彩虹連通的一個著色方案,并給出了該網(wǎng)絡(luò)強(qiáng)彩虹連通數(shù)的一個上界.

        圖2 環(huán)狀網(wǎng)絡(luò)G(33;±12)的彩虹著色方案Fig.2 The rainbow coloring scheme of loop network G(33;±12)

        證明注意到無向雙環(huán)網(wǎng)絡(luò)的邊有兩種類型:一種是[+s1]邊或[-s1]邊,即G(n; ±s1)中的邊,另一種是[+s2]邊或[-s2]邊,即G(n;±s2)中的邊.

        這樣便完成了無向雙環(huán)網(wǎng)絡(luò)G(n; ±s1,±s2)中所有邊的著色.

        據(jù)引理6,對于0≤k≤n-1,在G(n;±s1,±s2)中存在一條從0到k的最短路徑W[+s1]+R[+s2]滿足|W|

        在G(n;±s1)中有一條長為|W|的彩虹路:當(dāng)W>0時,0→s1→2s1→…→Ws1.當(dāng)W<0時,0→-s1→ -2s1→…→Ws1.

        在G(n;±s2)中有一條長為|R|的彩虹路:當(dāng)R>0時,Ws1→Ws1+s2→Ws1+2s2→…→Ws1+Rs2.當(dāng)R<0時,Ws1→Ws1-s2→Ws1-2s2→…→Ws1+Rs2.

        因在兩個網(wǎng)狀網(wǎng)絡(luò)G(n;±s1)與G(n;±s2)中的著色不同,故可得到一條從0到k,長度為|W|+|R|的最短彩虹路.證畢.

        證明僅就u≥v的情形給出證明,u

        當(dāng)u≥v,r3=r4且(u+a)(v+b)≡1(mod 2)時,可推出a=v.由引理1,可知a≤u.因此r3=(u+b)/2.據(jù)引理7,可得D(G)=r3-1=(u+b)/2-1.由定理1,可知src(G)≤2(t1+t2)-6=2(u+b)-6=4[(u+b)/2-1]-2=4D(G)-2.證畢.

        例2求無向雙環(huán)網(wǎng)絡(luò)G(2t2+2t+1;±1,±(2t+1))(這里t是正整數(shù),t>1)的強(qiáng)彩虹連通數(shù)的上界、直徑.

        (ii) 計算G(2t2+2t+1;±1,±(2t+1))的直徑.

        注意到src(G)≥D(G),我們得到的G(2t2+2t+1;±1,±(2t+1))的強(qiáng)彩虹連通數(shù)上界2t+2與該網(wǎng)絡(luò)直徑t較為接近.

        3 結(jié) 論

        圖的彩虹著色問題是一個多項式復(fù)雜程度的非確定性(NP)問題.其困難在于使用最小顏色數(shù)k,并要求G的任意兩點間均有一條彩虹路.直至目前,未見有文獻(xiàn)給出無向雙環(huán)網(wǎng)絡(luò)的彩虹著色方案.本文中通過對無向雙環(huán)網(wǎng)絡(luò)任意兩點之間的最短路徑進(jìn)行刻畫,進(jìn)而給出了該網(wǎng)絡(luò)強(qiáng)彩虹連通的一個著色方案,最后得到了該網(wǎng)絡(luò)強(qiáng)彩虹連通數(shù)的一個上界,這上界主要由G(n;±s1,±s2)所對應(yīng)的同余方程的最小非負(fù)解和最小交叉解中的4個參數(shù)表示.下一步的任務(wù)是找出更好的著色方案,使得所用的顏色數(shù)更少.

        猜你喜歡
        上界雙環(huán)著色
        蔬菜著色不良 這樣預(yù)防最好
        蘋果膨大著色期 管理細(xì)致別大意
        一個三角形角平分線不等式的上界估計
        10位畫家為美術(shù)片著色
        電影(2018年10期)2018-10-26 01:55:48
        一道經(jīng)典不等式的再加強(qiáng)
        “單環(huán)學(xué)習(xí)”與“雙環(huán)學(xué)習(xí)”
        電流雙環(huán)控制的LCL單相并網(wǎng)逆變器逆變研究
        聚丙烯成核劑雙環(huán)[2.2.1]-庚烷-2,3-二羧酸鈉的合成
        Nekrasov矩陣‖A-1‖∞的上界估計
        雙環(huán)法結(jié)合雙“V”形乳腺切除法在乳房肥大整形術(shù)中的應(yīng)用
        亚洲av中文无码字幕色本草| 亚洲中文字幕无线乱码va| 蜜桃成人精品一区二区三区| 欲女在线一区二区三区| 久久国产精品99精品国产| 97色伦图片97综合影院久久| 久久国产精品男人的天堂av| 婚外情长久的相处之道| 中文字幕日韩精品一区二区三区| 69精品丰满人妻无码视频a片| 中文字幕一区韩国三级| 日本高级黄色一区二区三区| 国产欧美一区二区三区在线看| 中字幕久久久人妻熟女| 国产精品国产三级国产三不| 人妖国产视频一区二区| 色哟哟精品视频在线观看| 精品无码久久久久久久动漫| 天堂女人av一区二区| 亚洲av综合av一区| 成l人在线观看线路1| 揄拍成人国产精品视频| 丰满人妻一区二区三区精品高清| 国产亚洲成人av一区| 明星性猛交ⅹxxx乱大交| 亚洲精品美女自拍偷拍| 日韩一二三四区在线观看| 免费a级毛片无码a∨中文字幕下载| 窝窝影院午夜看片| 久久视频在线视频精品| 亚洲一区二区在线观看免费视频| 亚洲中文字幕国产综合| 亚洲黄色尤物视频| 国产一区二区白浆在线观看| 亚洲av无码乱码在线观看富二代| 免费无码av片在线观看| 国内自拍第一区二区三区| 人妻少妇被猛烈进入中文字幕 | 日韩精品中文字幕一区二区| 亚洲va中文字幕无码毛片| 亚洲AV永久青草无码性色av|