Cayley圖在比較模型下的可診斷性

周 俊

(西安電子科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，陜西西安 710071)

隨著現(xiàn)代科學(xué)技術(shù)的發(fā)展，一個(gè)多處理器系統(tǒng)可由成千上萬(wàn)個(gè)處理器組成，系統(tǒng)在使用過程中會(huì)出現(xiàn)故障的處理器，將其找出是本文所要做的工作。所謂系統(tǒng)診斷就是找出一個(gè)處理器中故障點(diǎn)的過程，定義一個(gè)正整數(shù)t，只要一個(gè)系統(tǒng)的故障點(diǎn)不超過t，那么這個(gè)系統(tǒng)就是可診斷的。

目前，為診斷多處理器系統(tǒng)中的故障點(diǎn)，已有人提出了兩種診斷模型:PMC模型和比較模型。本文將主要采用比較模型解決系統(tǒng)的診斷，所謂比較模型就是從系統(tǒng)中的一個(gè)點(diǎn)w去測(cè)試和w相鄰的不同的兩個(gè)點(diǎn)u，v，再比較兩個(gè)測(cè)試結(jié)果是否一致。文中分別用(u，v)w和r((u，v)w)表示一個(gè)測(cè)試點(diǎn)和一個(gè)測(cè)試結(jié)果，若 r((u，v)w)=0，則表示測(cè)試一致;若 r((u，v)w)=1，則表示測(cè)試結(jié)果不同。在比較模型下，如果r((u，v)w)=0且w不是故障點(diǎn)，則u，v都是無(wú)故障點(diǎn);如果r((u，v)w)=1，則 u，v，w 至少有一個(gè)點(diǎn)是故障點(diǎn);如果w是故障點(diǎn)，則測(cè)試結(jié)果是不可靠的。

1 預(yù)備知識(shí)

設(shè)Γ是一個(gè)固定的群，S是Γ的一個(gè)子集且不含有 Γ 中的相同的元素，Cayley［1］圖 Cay(Γ，S)是一個(gè)無(wú)向圖，其中Γ是點(diǎn)集;集合{(g，gs )∈Γ，s∈S}是弧集。Sym(n)用一個(gè)置換{1，…，n}，ij位置置換表示為(p1…pi…pj…pn)(ij)=(p1…pj…pi…pn)。設(shè) X 為一個(gè)置換集，則G(X)是一個(gè)置換樹生成圖［2］，其中點(diǎn)集為{1，2，…，n}邊集 E=(ij)∈X}。

一個(gè)多處理器系統(tǒng)可以表示成一個(gè)無(wú)向圖G=(V，E)，其中V和E分別是圖G的點(diǎn)集和邊集。如果兩個(gè)點(diǎn)u，v是相鄰的則uv是G中的一條邊。一條路徑可表示為 P［v0，vk］=〈v0，v1，…，vk〉，其中若 vi和vi+1在G中相鄰，且P中的內(nèi)部點(diǎn)互不相同。當(dāng)v0=vk時(shí)，則P［v0，vk］為一個(gè)圈。設(shè) u是圖 G中的一個(gè)點(diǎn)，則uNG(u)表示u的鄰點(diǎn)，設(shè)X為圖G中的一個(gè)點(diǎn)集［3］，則 NG(X)={v∈V(G)－X∈X 且(u，v)∈E(G)}。用Gn表示n維置換樹生成的 Cayley圖［4－6］。

定義1 若一個(gè)有n個(gè)點(diǎn)的系統(tǒng)所有故障點(diǎn)不超過t，其所有的故障點(diǎn)可以被診斷出，該系統(tǒng)是t－可診斷的［7］。

定義2 假設(shè)一個(gè)圖G=(V，E)，若G中的每一條邊E至少有一個(gè)端點(diǎn)在H中，則H是G的一個(gè)點(diǎn)覆蓋。假設(shè)u∈V，則點(diǎn)u關(guān)于圖G的最小點(diǎn)覆蓋數(shù)稱為u的次序。

根據(jù)以上的定義可以得到以下結(jié)論:

引理1［8］Gn中任何點(diǎn)的次序都為 n－1。

引理2［8］Gn中任何兩個(gè)點(diǎn)最多有兩個(gè)相同的鄰點(diǎn)。

引理3［9］Gn中沒有奇圈。

引理4［9］設(shè)Gn是置換樹生成的Caley圖且Gn不是星圖，則當(dāng)n≥3時(shí)有:(1)Gn中最小圈是4。(2)Gn中沒有K2，3作為子圖，如圖1所示。

圖 1 K2，3

2 主要結(jié)果

引理5 設(shè)u，v是 Gn中兩個(gè)點(diǎn)，則 NG(u，v)≥2n－4。

證明 Gn是(n－1)正則圖，則。考慮兩種情況:(1)u，v是Gn中相鄰的兩個(gè)點(diǎn)，則2n－4。(2)u，v不是 Gn中相鄰的兩個(gè)點(diǎn)，則

綜上所述，Gn中任意兩點(diǎn)中至少有2n－4個(gè)鄰點(diǎn)。

引理 6 設(shè) u，v，x，y是 Gn中 4 個(gè)點(diǎn)，則

證明 考慮到4個(gè)點(diǎn)中相鄰點(diǎn)的數(shù)目，可以有以下幾種情況:

(1)當(dāng)4個(gè)點(diǎn)都相鄰，則會(huì)有圖2所示的3種情形。

圖2 4個(gè)點(diǎn)相鄰

1)4個(gè)點(diǎn)組成一個(gè)圈，則

2)4個(gè)點(diǎn)中最多有1個(gè)相同鄰點(diǎn)，則

3)4個(gè)點(diǎn)中最多有兩個(gè)相同鄰點(diǎn)，則

(2)4個(gè)點(diǎn)中有3個(gè)點(diǎn)相鄰，而另一個(gè)點(diǎn)與這3個(gè)點(diǎn)都不相鄰。則會(huì)有如圖3所示的兩種情況。

圖3 3個(gè)點(diǎn)相鄰

1)這種情況下，4個(gè)點(diǎn)最多有4個(gè)相同鄰點(diǎn)，則

2)這種情況下，4個(gè)點(diǎn)最多有3個(gè)相同的鄰點(diǎn)，則

(3)4個(gè)點(diǎn)中兩個(gè)點(diǎn)相鄰與兩個(gè)點(diǎn)相鄰，如圖4所示。則

圖4 4個(gè)點(diǎn)兩兩相鄰

(4)4個(gè)點(diǎn)中兩個(gè)點(diǎn)相鄰，另兩個(gè)點(diǎn)不相鄰，如圖5所示。則

圖5 4個(gè)點(diǎn)中兩個(gè)點(diǎn)相鄰另兩個(gè)不相鄰

(5)4個(gè)點(diǎn)都不相鄰，如圖6所示。則有

綜上所述:Gn中任何4個(gè)點(diǎn)至少有4n－12個(gè)鄰點(diǎn)。

定理1［8］一個(gè)有N個(gè)點(diǎn)的系統(tǒng)是t－可診斷的，

則滿足3個(gè)條件:(1)N≥2t+1。(2)任意一個(gè)點(diǎn)的次序至少為t。(3)任何一個(gè)集合X?V，則有2t+p且

定理2［8］當(dāng)n≥4時(shí)，n維星圖在比較模型下是(n－1)可診斷的。

定理3 當(dāng)n≥5時(shí)，n維置換樹生成的 Cayley圖在比較模型下是(n－1)可診斷的。

證明 由定理2可知，當(dāng)n≥4時(shí)，n維星圖在比較模型下是(n－1)可診斷的［5－6］。接下來(lái)，證明 Gn是(n－1)可診斷的。

已知Gn有n!個(gè)點(diǎn)且Gn中每個(gè)點(diǎn)的次序都是(n－1)。顯然當(dāng)n≥3時(shí)，n!≥2(n－1)+1。根據(jù)定理1，只要證明條件(3)。即滿足是正確的。分兩步證明，首先，證明當(dāng)p=n－2時(shí)結(jié)論是正確的，再證明當(dāng)0≤p≤n－3時(shí)結(jié)論正確。

圖6 兩個(gè)點(diǎn)不在T(X)中

1)NG(u)∩X=?。2)若果存在u'∈NG(u)∩X，則NG(u')∩X=?，如果兩個(gè)點(diǎn)。

u，v?T(X)則滿足圖7中3種情況的一種。

圖7 兩個(gè)點(diǎn)不在T(X)中的3種情形

情形1 不在T(X)中的兩個(gè)點(diǎn)都是圖6中情形a的點(diǎn)，由于則有

情形2 一個(gè)點(diǎn)是情形a中的點(diǎn)，另一個(gè)點(diǎn)是情形b中的點(diǎn)。假設(shè)u是情形b中的點(diǎn)，v是情形a中的點(diǎn)。由于v和X中任何點(diǎn)都不連通，所以u(píng)和v不相鄰。故 有且

情形3 兩個(gè)點(diǎn)都屬于情形b中的點(diǎn)，由T(X)的定義可知，u'和v'是不相鄰的，則且

圖8 4個(gè)點(diǎn)不在T(X)中的5種情形

情形1 4 個(gè)點(diǎn)都屬于情形 a，則 NG({u，v，x，y}) 以及 u，v，x，y 都不在 X 中且有 NG({u，v，x，y})≥4n －12，故有

情形2 4個(gè)點(diǎn)中有3個(gè)點(diǎn)屬于情形a一個(gè)點(diǎn)屬于情形b。假設(shè)u和u'是相連通的且u'∈X，則u'和v，x，y不相鄰，則有以下3種情形:

情形2.1 v，x 和 y 相鄰，則 NG({u'，v，x，y})以及v，x，y 都不在 X 中且有 NG({u'，v，x，y})≥4n － 12，故有

情形2.2 3個(gè)點(diǎn)中有兩個(gè)點(diǎn)相鄰一個(gè)點(diǎn)不相鄰，則 NG({u'，v，x，y})以及 v，x，y 都不在 X 中且有NG({u'，v，x，y})≥4n －10，故有

情形 2.3 3 個(gè)點(diǎn)相互相鄰，則 NG({u'，v，x，y})以及 v，x，y 都不在 X 中且有 NG({u'，v，x，y})≥4n －12，故有

情形3 4個(gè)點(diǎn)中有兩個(gè)點(diǎn)屬于情形a另外兩個(gè)點(diǎn)屬于情形b，假設(shè)u，v屬于情形b x，y屬于情形a，則u'和v'互不相鄰，同時(shí)和x，y也不相鄰。則有以下兩種情形:

情形 3.1 x，y 是相鄰的兩個(gè)點(diǎn)，則 NG({u'，v'，x，y})以及 x，y 都不在 X 中且有 NG({u'，v，x，y})≥4n －10，故有

情形3.2 x，y是互不相鄰的兩個(gè)點(diǎn)，則NG({u'，v'，x，y})以及 x，y 都不在 X 中且有 NG({u'，v，x，y})≥4n－12，故有

情形4 4個(gè)點(diǎn)中有3個(gè)點(diǎn)屬于情形b有一個(gè)點(diǎn)屬于情形a，假設(shè)屬于情形b且y屬于情形a。則u'，v'，x'互不相鄰且不和 y 相鄰，則 NG({u'，v'，x'，y})以及 y都不在 X 中且有 NG({u'，v'，x'，y})≥4n －12，故有

情形 5 4 個(gè)點(diǎn)都屬于情形 b，則 u'，v'，x'，y'互不相鄰，則 NG({u'，v'，x'，y'})都不在 X 中且有 NG({u'，v'，x'，y'})≥4n －12，故有

3 結(jié)束語(yǔ)

證明了當(dāng)n≥5時(shí)，置換樹生成的Cayley圖在比較模型下是n－1可診斷的。同時(shí)Gn的最小邊界也已研究，這樣就可以繼續(xù)研究Gn的額外連通度。在此結(jié)果的基礎(chǔ)上，當(dāng)一個(gè)系統(tǒng)的故障處理器不超過n－1時(shí)，就可對(duì)該系統(tǒng)進(jìn)行診斷。而該診斷只涉及一個(gè)測(cè)試階段，以確定有故障的處理器和一個(gè)更換階段。因此，使用與環(huán)境的組件是可靠的，并具有周期性和快速性，且經(jīng)濟(jì)實(shí)惠。

［1］Cheng E，Lipták L.Diagnosability of Cayley graphs generated by transposition trees with missing edges［J］.Information Sciences，2013，23(8):250 －252.

［2］Hsu G H，Chiang C F，Shih L M，et al.Conditional diagnosability of hypercubes under the comparison diagnosis model［J］.Journal of Systems Architecture，2009，55(2):140 －146.

［3］Zheng J，Latifi S，Regentova E，et al.Diagnosability of star graphs under the comparison diagnosis model［J］.Information Processing Letters，2005，93(1):29 －36.

［4］Bondy J A，Murty U S R.Graph theory with applications［M］.London:Macmillan，1976.

［5］Tanaka Y，Kikuchi Y，Araki T，et al.Bipancyclic properties of Cayley graphs generated by transpositions［J］.Discrete Mathematics，2010，310(4):748 －754.

［6］Caruso A，Chessa S，Maestrini P，et al.Diagnosability of regular systems ［J］.Journal of Algorithms，2002，45(2):126－143.

［7］Tanaka Y，Kikuchi Y，Araki T，et al.Bipancyclic properties of Cayley graphs generated by transpositions［J］.Discrete Mathematics，2010，310(4):748 －754.

［8］Yang W，Li H，Meng J.Conditional connectivity of Cayley graphs generated by transposition trees［J］.Information Processing Letters，2010，110(23):1027 －1030.

［9］Cheng E，Lipták L，Shawash N.Orienting Cayley graphs generated by transposition trees［J］.Computers and Mathematics with Applications，2008，55(11):2662 －2672.