林上為，原牡丹，李春芳

(山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山西 太原 030006)

多處理機(jī)系統(tǒng)互連網(wǎng)絡(luò)的數(shù)學(xué)模型是圖.Kautz圖[1]作為Kautz網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)在1969年被提出.由于具有在某種意義下使得連通度達(dá)到最大(可靠性到達(dá)最高)、直徑達(dá)到最小(傳輸延遲達(dá)到最小)的優(yōu)點(diǎn)， Kautz圖成為大型多處理機(jī)系統(tǒng)重要的候選互連網(wǎng)絡(luò)，得到廣泛的關(guān)注[2-4].

邊連通度是度量網(wǎng)絡(luò)可靠性的一個(gè)重要參數(shù).為了更加精確地度量，在1988年，Esfahanian和 Hakimi[5]提出了無向圖的限制邊連通度的概念.關(guān)于無向圖的限制邊連通度已經(jīng)有很多結(jié)果，詳見綜述文章[6].作為限制邊連通度在有向圖中的4個(gè)推廣，強(qiáng)限制弧連通度、限制弧連通度、圈分離弧連通度和條件弧連通度分別被Xu等[7]、Volkmann[8]、Zhang等[9]和周等[10]提出.與無向圖的限制邊連通度相比，對有向圖的限制弧連通度的研究剛剛起步[7-12].

無向Kautz圖的限制邊連通度已經(jīng)被完全確定[13-16].有向Kautz圖的限制弧連通度也得到了一些研究.2004年，范等[17]確定了有向Kautz圖的強(qiáng)限制弧連通度.2017年，周等[10]確定了有向Kautz圖的條件弧連通度.文中將完全確定有向Kautz圖的限制弧連通度和圈分離弧連通度，并且確定了對應(yīng)的最小限制弧割的結(jié)構(gòu)特征.

1 準(zhǔn)備工作

對于本文沒有定義的符號和術(shù)語，請參見文[18].先介紹有向Kautz圖的定義.

圖1 有向Kautz圖K(2,2)和K(2,3)圖

下面介紹有向Kautz圖K(d,n)的一個(gè)有用的性質(zhì).稱有向Kautz圖K(d,n)的一個(gè)頂點(diǎn)x=x1x2…xn是交錯(cuò)點(diǎn)，如果存在2個(gè)不同的數(shù)a,b∈{0,1,…d}，使得x1=x3…=a≠b=x2=x4=….稱2個(gè)交錯(cuò)頂點(diǎn)x=x1x2…xn和y=y1y2…yn是對稱的，如果x1=y2且x2=y1.將長度為2的圈稱為2-圈.

命題1[16]xyx是K(d,n)中的一個(gè)2-圈當(dāng)且僅當(dāng)x,y是一對對稱交錯(cuò)點(diǎn).

無向Kautz圖UK(d,n)是有向Kautz圖K(d,n)的基礎(chǔ)無向圖，即通過刪去K(d,n)的所有的弧的方向以及只保留2-圈中的一條邊得到的無向圖.圖2給出了無向Kautz圖UK(2,2)和UK(2,3).

圖2 無向圖UK(2,2)和UK(2,3)圖

一個(gè)圖稱為是平凡的，若它只有一個(gè)頂點(diǎn)，否則稱它為非平凡的.

定義1[5]設(shè)G是一個(gè)連通無向圖.稱G的一個(gè)邊子集S是G的一個(gè)限制邊割，若G-S不連通，且G-S的每個(gè)連通分支都是非平凡的.若G中存在一個(gè)限制邊割，則稱G是限制邊連通的.限制邊連通圖G的限制邊連通度定義為它的一個(gè)最小限制邊割所包含的邊數(shù)，記為λ′(G).

對于無向圖G的非空頂點(diǎn)子集對X,Y，記X與Y之間的邊的集合為[X,Y].由文[19]中引理1.1的證明可得下面的定理.

定理1[19]設(shè)G是一個(gè)限制邊連通的無向圖，如果存在V(G)的一個(gè)子集X,使得G的2個(gè)導(dǎo)出子圖G[X]和G[Y]都包含一個(gè)非平凡的連通子圖，其中Y=V(G)-X，那么[X,Y]包含G的一個(gè)限制邊割，從而|[X,Y]|≥λ′(G).

定義2[13]稱一個(gè)連通無向圖G是超級限制邊連通的，如果G的任意一個(gè)最小限制邊割S都是某條邊的相鄰邊集，即G-S只有2個(gè)連通分支，且其中的一個(gè)連通分支只有一條邊.

定理2[13]當(dāng)d=2和n≥3時(shí)，無向Kautz圖UK(d,n)的限制邊連通度為λ′(UK(d,n))=4d-4=4，且UK(d,n)是超級限制邊連通的.

定理3[14]當(dāng)d≥3和n≥2時(shí)，無向Kautz圖UK(d,n)的限制邊連通度為λ′(UK(d,n))=4d-4，且UK(d,n)是超級限制邊連通的.

定理4[15]當(dāng)d≥3和n=1時(shí)，無向Kautz圖UK(d,n)的限制邊連通度為λ′(UK(d,n))=2d-2，且UK(d,n)是超級限制邊連通的.

有向圖D稱為是強(qiáng)連通的，若對D中的任意2個(gè)頂點(diǎn)u和v，都存在從u到v和從v到u的有向路.有向圖D的極大強(qiáng)連通子圖稱為D的強(qiáng)連通分支.若D中有t個(gè)強(qiáng)連通分支，則可將這t個(gè)強(qiáng)連通分支排序?yàn)镈1,D2,…,Dt，使得當(dāng)j>i時(shí)，沒有從Dj到Di的弧，這樣的D1,D2,…,Dt叫作D的一個(gè)強(qiáng)連通分支無圈序[18].

設(shè)D是一個(gè)有向圖.稱D的一個(gè)弧子集S是D的一個(gè)弧割，若D-S不強(qiáng)連通.有向圖D的弧連通度定義為它的一個(gè)最小弧割所包含的弧數(shù)，記為λ(D).

定理5[20]當(dāng)d≥1和n≥2時(shí)，有向Kautz圖K(d,n)的弧連通度λ(K(d,n))=d.

設(shè)D是一個(gè)強(qiáng)連通有向圖.下面給出D的4種限制弧連通度的定義.

定義3[7]稱D中的一個(gè)弧割S是D的一個(gè)強(qiáng)限制弧割，若D-S的每個(gè)強(qiáng)連通分支都是非平凡的.若D中存在一個(gè)強(qiáng)限制弧割，則稱D是λ2-連通的.λ2-連通有向圖D的強(qiáng)限制弧連通度定義為D的一個(gè)最小強(qiáng)限制弧割所含的弧數(shù)，記作λ2(D).

定義4[8]稱D中的一個(gè)弧割S是D的一個(gè)限制弧割，若D-S有一個(gè)非平凡強(qiáng)連通分支D′，使得D-V(D′)包含一條弧.若D中存在一個(gè)限制弧割，則稱D是λ′-連通的.λ′-連通有向圖D的限制弧連通度定義為D的一個(gè)最小限制弧割所含的弧數(shù)，記作λ′(D).

定義5[9]稱D中的一個(gè)弧割S是D的一個(gè)圈分離弧割，若D-S有至少2個(gè)非平凡強(qiáng)連通分支.若D中存在一個(gè)圈分離弧割，則稱D是λc-連通的.λc-連通有向圖D的圈弧連通度定義為D的一個(gè)最小圈分離弧割所含的弧數(shù)，記作λc(D).

定義6[10]稱D中的一個(gè)弧割S是D的一個(gè)條件弧割，若D-S的最小度δ(D-S)≥1，即D的每個(gè)頂點(diǎn)在D-S中都有至少一個(gè)出鄰點(diǎn)和入鄰點(diǎn).若D中存在一個(gè)條件弧割，則稱D是λ(1)-連通的.λ(1)-連通有向圖D的條件弧連通度定義為D的一個(gè)最小條件弧割所含的弧數(shù)，記作λ(1)(D).

文獻(xiàn)[10]說明以上定義的4種弧連通度都是無向圖的限制邊連通度在有向圖的推廣，并且研究了它們之間的關(guān)系.

定理6[10]若D是一個(gè)λ2-連通有向圖，則有λ2(D)≥λ(1)(D)≥λc(D)≥λ′(D).

文[10]也給出例子說明了在同一個(gè)有向圖上，這4種弧連通度的取值可能不同，這就說明了這4個(gè)弧連通度確實(shí)是不同的圖參數(shù).對有向Kautz圖有下列結(jié)論.

定理7[17]對d≥2,n≥1且(d,n)≠(2,1)，有向Kautz圖K(d,n)是λ2-連通的，且K(d,n)的強(qiáng)限制弧連通度λ2(K(d,n))=2d-2.

定理8[10]對d≥2,n≥1且(d,n)≠(2,1)，有向Kautz圖K(d,n)是λ(1)-連通的，且K(d,n)的條件弧連通度λ(1)(K(d,n))=2d-2.

在有向圖D中，記?+(X)={(x,y)∈A(D):x∈X,y?X}，?-(X)={(x,y)∈A(D):x?X,y∈X}.若X是單點(diǎn)集合X={x}，也將?+(X)簡寫為?+(x)，將?-(X)簡寫為?-(x).

定理9[21]若D是一個(gè)d-正則的有向圖，則對D的任意非空頂點(diǎn)子集X?V(D)，有|?+(X)|=|?-(X)|.

定義7[22]一個(gè)λ′-連通的有向圖D是超級限制弧連通的，若對D的每一個(gè)最小限制弧割S,都存在一條弧(x,y)∈A(D),使得S∈Ωxy={?+({x,y}),?-({x,y}),?-(x)∪?+(y),?+(x)∪?-(y)}.

定理10[22]設(shè)D是一個(gè)λ′-連通有向圖，S是D的一個(gè)最小限制弧割.如果D不是超級限制弧連通的，那么存在一個(gè)頂點(diǎn)子集X?V(D)，使得S=?+(X)，且誘導(dǎo)子圖D[X]和D[V(D)-X]都包含一條弧.

2 主要結(jié)果

顯然，對任意的n≥1，K(1,n)是2階完全有向圖，K(2,1)是3階完全有向圖，都不是λ′-連通的，下面考慮剩余的情形.

定理11若d≥2和n≥1是滿足(d,n)≠(2,1)的2個(gè)整數(shù)，則有向Kautz圖K(d,n)的限制弧連通度λ′(K(d,n))=2d-2，且K(d,n)中的任意一個(gè)最小限制弧割S必是某個(gè)2-圈的出弧集或入弧集，即存在K(d,n)中的一對對稱交錯(cuò)點(diǎn)x和y，使得S=?+({x,y})或S=?-({x,y}).

證明根據(jù)定理6和定理7，當(dāng)d≥2和n≥1且滿足(d,n)≠(2,1)時(shí)，有2d-2=λ2(K(d,n))≥λ(1)(K(d,n))≥λc(K(d,n))≥λ′(K(d,n))，可得

λ′(K(d,n))≤2d-2.

(1)

設(shè)S是K(d,n)的一個(gè)最小限制弧割，則有|S|=λ′(K(d,n))≤2d-2.分別考慮以下情形，完成證明.

情形1(d,n)=(2,2).

結(jié)合(1)式、定理5以及定義4，2=2d-2≥λ′(K(2,2))≥λ(K(2,2))=2.故|S|=λ′(K(2,2)=2d-2=2.

設(shè)D1,D2,…,Dt是K(2,2)-S的一個(gè)強(qiáng)連通分支無圈序.顯然有t≥2.

假設(shè)|V(Dt)|=1，則不失一般性可設(shè)V(Dt)={01}.由強(qiáng)連通分支無圈序的定義，可知{(01,12),(01,10)}=?+(V(Dt))?S.又因?yàn)閨S|=2，所以S={(01,12),(01,10)}.由圖1容易看出K(2,2)-S只包含2個(gè)強(qiáng)連通分支D1和D2，其中V(D2)={01}，D1=K(2,2)-V(D2).因此D1是K(2,2)-S唯一的非平凡強(qiáng)連通分支，但K(2,2)-V(D1)不含弧，與S是限制弧割矛盾.因此，|V(Dt)|≥2.同理可得|V(D1)|≥2.

假設(shè)|V(Dt)|≥3且|V(D1)|≥3.由于K(2,2)只有6個(gè)頂點(diǎn)，故t=2且|V(D1)|=|V(D2)|=3.從圖1容易看出，K(2,2)中3階強(qiáng)連通子圖只有K(2,2)[{01,12,20}]和K(2,2)[{10,21,02}].不失一般性可設(shè)Dt=K(2,2)[{01,12,20}].由強(qiáng)連通分支無圈序的定義，?+(V(Dt))?S，故|S|≥|?+(V(Dt))|=3，與|S|=2矛盾.因此，|V(Dt)|=2或|V(D1)|=2.

若|V(Dt)|=2，則Dt是一個(gè)2-圈，由2=|?+(V(Dt))|≤|S|=2，可得?+(V(Dt))=S；同理，若|V(D1)|=2，此時(shí)D1是一個(gè)2-圈且?-(V(D1))=S.綜上，當(dāng)(d,n)=(2,2)時(shí)，K(2,2)中的任意一個(gè)最小限制弧割S是某個(gè)2-圈的出弧集或入弧集.

情形2d≥2和n≥1且(d,n)≠(2,2).

情形2.1不存在一條弧(x,y)∈A(K(d,n))，使得S∈Ωxy，其中Ωxy的定義參見定義7.

由定義7，K(d,n)不是超級限制弧連通的.根據(jù)定理10，存在一個(gè)頂點(diǎn)子集X?V(K(d,n))，使得S=?+(X),且誘導(dǎo)子圖K(d,n)[X]和K(d,n)[Y]都至少包含一條弧，其中Y=V(K(d,n))-X.記K(d,n)中X與Y之間的2-圈數(shù)為c，即c=|{xyx:x∈X,y∈Y,(x,y),(y,x)∈A(K(d,n))}|.

由于K(d,n)是d-正則的，根據(jù)定理9，|?+(X)|=|?-(X)|.在無向圖UK(d,n)中，記X與Y之間的邊的集合為[X,Y]，那么有

|[X,Y]|=|?+(X)|+|?-(X)|-c=2|?+(X)|-c=2|S|-c.

(2)

因?yàn)镵(d,n)的誘導(dǎo)子圖K(d,n)[X]和K(d,n)[Y]都至少包含一條弧，所以無向圖UK(d,n)的誘導(dǎo)子圖UK(d,n)[X]和UK(d,n)[Y]都至少包含一條邊.根據(jù)定理1， [X,Y]包含UK(d,n)的一個(gè)限制邊割，從而

|[X,Y]|≥λ′(UK(d,n)).

(3)

當(dāng)n=1且d≥3時(shí)，K(d,n)是d+1階完全有向圖，對任意的2個(gè)頂點(diǎn)x,y，都有xyx是一個(gè)2-圈，因此有c=|S|.再結(jié)合(1)式、(2)式、(3)式和定理4，可得2d-2≥|S|=2|S|-c=|[X,Y]|≥λ′(UK(d,n))=2d-2，即|S|=|[X,Y]|=λ′(UK(d,n))=2d-2.

當(dāng)d≥2和n≥2且(d,n)≠(2,2)時(shí)，結(jié)合(1)式、(2)式、(3)式、定理2和定理3可知 4d-4≥2|S|≥2|S|-c=|[X,Y]|≥λ′(UK(d,n))=4d-4，從而有|[X,Y]|=λ′(UK(d,n))和|S|=2d-2.

綜上，當(dāng)d≥2和n≥1且(d,n)≠(2,2)時(shí)都有λ′(K(d,n))=|S|=2d-2且|[X,Y]|=λ′(UK(d,n))，又因?yàn)閇X,Y]包含UK(d,n)的一個(gè)限制邊割，所以[X,Y]就是UK(d,n)的一個(gè)最小限制邊割.由定理2、定理3和定理4，UK(d,n)是超級限制邊連通的，由定義2可知或者UK(d,n)[X]是一條邊或者UK(d,n)[Y]是一條邊.若UK(d,n)[X]是一條邊，則可設(shè)X={x,y}且(x,y)是K(d,n)的一條弧.此時(shí)S=?+(X)=?+({x,y})∈Ωxy，矛盾.同理，若UK(d,n)[Y]是一條邊，則可設(shè)Y={x,y}且(x,y)是K(d,n)的一條弧.此時(shí)S=?-(Y)=?-({x,y})∈Ωxy,矛盾.

情形2.2存在一條弧(x,y)∈A(K(d,n))，使得S∈Ωxy.

由定義，Ωxy={?+({x,y}),?-({x,y}),?-(x)∪?+(y),?+(x)∪?-(y)}.若(y,x)?A(K(d,n)),則|?+({x,y})|=d+(x)+d+(y)-1=2d-1，|?-({x,y})|=d-(x)+d-(y)-1=2d-1，|?-(x)∪?+(y)|=d+(y)+d-(x)=2d，|?+(x)∪?-(y)|=d+(x)+d-(y)-1=2d-1，因此|S|≥min{d+(x)+d+(y)-1,d-(x)+d-(y)-1,d+(y)+d-(x),d+(x)+d-(y)-1}=2d-1，與(1)式矛盾.因此可得(y,x)∈A(K(d,n)).此時(shí)xyx是一個(gè)2-圈.當(dāng)S=?-(x)∪?+(y)時(shí)，|S|=|?-(x)∪?+(y)|=d+(y)+d-(x)-1=2d-1，與(1)式矛盾；當(dāng)S=?+(x)∪?-(y)時(shí)，|S|=|?+(x)∪?-(y)|=d+(x)+d-(y)-1=2d-1，與(1)式矛盾，故只有S=?+({x,y})或S=?-({x,y}).如果S=?+({x,y})，那么S是2-圈xyx的出弧集且|S|=|?+({x,y})|=d+(x)+d+(y)-2=2d-2；如果S=?-({x,y})，那么S是2-圈xyx的入弧集且|S|=|?-({x,y})|=d-(x)+d-(y)-2=2d-2.定理得證.

由定理11和定義7可得下面的推論1.

推論1若d≥2和n≥1是滿足(d,n)≠(2,1)的2個(gè)整數(shù)，則有向Kautz圖K(d,n)是超級限制弧連通的.

推論2若d≥2和n≥1是滿足(d,n)≠(2,1)的2個(gè)整數(shù)，則對有向Kautz圖K(d,n)有λ2(K(d,n))=λ(1)(K(d,n))=λc(K(d,n))=λ′(K(d,n))=2d-2，且每個(gè)最小強(qiáng)限制弧割、最小條件弧割、最小圈分離弧割和最小限制弧割都是某個(gè)2-圈的出弧集或入弧集.

證明根據(jù)定理6、定理7和定理11，容易得到 2d-2=λ2(K(d,n))≥λ(1)(K(d,n))≥λc(K(d,n))≥λ′(K(d,n))=2d-2，故有λ2(K(d,n))=λ(1)(K(d,n))=λc(K(d,n))=λ′(K(d,n))=2d-2.設(shè)S是K(d,n)的一個(gè)最小強(qiáng)限制弧割或最小條件弧割或最小圈分離弧割或最小限制弧割，則|S|=2d-2.由定義3、定義4、定義5和定義6，S也是K(d,n)的一個(gè)限制弧割，由定理11，λ′(K(d,n))=2d-2，故S也是K(d,n)的一個(gè)最小限制弧割，故S必是某個(gè)2-圈的出弧集或入弧集.