王志穎，魏二玲

(中國人民大學(xué) 數(shù)學(xué)學(xué)院, 北京 100872)

0 引 言

信息社會(huì)離不開計(jì)算機(jī)互聯(lián)網(wǎng)絡(luò). 隨著互聯(lián)網(wǎng)使用規(guī)模的不斷擴(kuò)大, 處理器之間的連線故障更加頻繁.為此, 網(wǎng)絡(luò)需要具備一定的容錯(cuò)性.網(wǎng)絡(luò)的容錯(cuò)性是指在故障發(fā)生時(shí), 網(wǎng)絡(luò)是否能繼續(xù)保持良好的性能.反映到理論上, 就是要對(duì)互聯(lián)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的研究.多處理器系統(tǒng)可以用一個(gè)圖網(wǎng)絡(luò)來表示.多處理器即圖中的節(jié)點(diǎn), 兩個(gè)多處理器之間若有線相連, 即在兩點(diǎn)之間連邊.多處理器故障即網(wǎng)絡(luò)的頂點(diǎn)故障, 連線故障即邊故障.完全獨(dú)立支撐樹被廣泛應(yīng)用于互聯(lián)網(wǎng)的容錯(cuò)通信問題之中.當(dāng)計(jì)算機(jī)沿著這k個(gè)完全獨(dú)立支撐樹發(fā)送消息時(shí), 即使k-1個(gè)支撐樹路徑發(fā)生故障, 最后一個(gè)支撐樹路徑仍然能保證通信過程正常進(jìn)行，所以對(duì)完全獨(dú)立支撐樹的研究是非常有意義的.

完全獨(dú)立支撐樹的研究是源于Hasunuma[1]的早期工作，作者給出了完全獨(dú)立支撐樹的刻畫并證明了k連通線圖的基礎(chǔ)圖存在k個(gè)完全獨(dú)立支撐樹.Araki[2]、Hong和Liu[3]以及林政寬等人[4]關(guān)注圖的最小度條件，給出了存在完全獨(dú)立支撐樹的新的充分條件.Hong[5]證明了最小度δ≥k、頂點(diǎn)數(shù)n≥2k的連通圖G的k次方圖Gk存在k個(gè)完全獨(dú)立支撐樹.Qin等[6]給出了一類復(fù)合圖存在k個(gè)完全獨(dú)立支撐樹的充分條件.判斷圖是否存在完全獨(dú)立支撐樹，除了從最小度數(shù)條件出發(fā), 還可以從圖的連通度出發(fā).Hasunuma[1]進(jìn)一步研究了完全獨(dú)立支撐樹與連通度之間的關(guān)系,猜想任意2k連通的圖都有k個(gè)完全獨(dú)立支撐樹.Péterfalvi[7]和Pai等人[8]證明了這個(gè)猜想是不正確的，并且Péterfalvi[7]給出了反例，表示對(duì)任一個(gè)k(k≥2)，存在k連通的圖，但圖中找不到兩個(gè)完全獨(dú)立支撐樹.說明連通度不是保證存在完全獨(dú)立支撐樹的條件.更多關(guān)于完全獨(dú)立支撐樹的研究可參見文獻(xiàn)[9]和[10]等.

雖然Hasunuma的猜想存在反例，但是仍有大量的2k連通的圖有k個(gè)完全獨(dú)立支撐樹，尤其對(duì)一些具有高度對(duì)稱性的網(wǎng)絡(luò).文獻(xiàn)[11]證明了對(duì)任一個(gè)環(huán)面網(wǎng)絡(luò)來說，都存在兩個(gè)完全獨(dú)立支撐樹.很多大型并行計(jì)算機(jī)中大量采用環(huán)面平行互聯(lián)網(wǎng)絡(luò).本文討論的一類克萊因瓶網(wǎng)絡(luò)是環(huán)面網(wǎng)絡(luò)的一種變形.它是一個(gè)具有mn個(gè)頂點(diǎn),2mn條邊的圖.我們知道一個(gè)mn個(gè)頂點(diǎn)的樹含有mn-1條邊, 由邊的關(guān)系我們知道這類網(wǎng)絡(luò)的完全獨(dú)立支撐樹至多有兩個(gè). 在接下來的討論中, 我們將集中討論這類網(wǎng)絡(luò)是否存在兩個(gè)完全獨(dú)立支撐樹.

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

首先我們給出本文討論的克萊因瓶網(wǎng)絡(luò)K(m,n)=(V,E)的定義, 其中m和n是大于等于3的整數(shù)，其頂點(diǎn)集為V={(i,j)|0≤i≤m-1,0≤j≤n-1},((i,j),(s,t))∈E當(dāng)且僅當(dāng)滿足以下三種情況之一：

①i=s,j≡t±1(modn)；

②j=t,i?{0,m-1}或s?{0,m-1},i≡s±1(modm)；

③i,s∈{0,m-1},i≠s,j+t=n-1.

圖1給出了K(m,n)的圖示.為了使圖清晰起見，本文對(duì)部分邊使用半邊表示法，即一條邊分解為兩個(gè)半邊.例如：圖1中頂點(diǎn)(0,0)和(m-1,n-1)關(guān)聯(lián)的兩個(gè)半邊合起來即為邊((0,0),(m-1,n-1)).在之后所示的圖中，我們都采用了這種表示法，不再贅述.

圖1 克萊因瓶網(wǎng)絡(luò)K(m,n)Fig.1 Klein bottle network K(m,n)

文獻(xiàn)[11]中將并行計(jì)算中用到的一類網(wǎng)絡(luò)稱為環(huán)面網(wǎng)絡(luò)，并討論了環(huán)面網(wǎng)絡(luò)的完全獨(dú)立支撐樹圖.本文討論了與文獻(xiàn)[11]中網(wǎng)絡(luò)類似、但對(duì)稱性稍弱、可以嵌入在克萊因瓶上的網(wǎng)絡(luò), 并定義其為克萊因瓶網(wǎng)絡(luò).圖2給出了以K(3×4)在克萊因瓶上的嵌入.

圖2 K(3,4)在克萊因瓶上的嵌入Fig.2 Embedding of K(3,4) on the Klein bottle

接下來介紹第二個(gè)重要的定義：完全獨(dú)立支撐樹(CIST). 設(shè)G是一個(gè)簡(jiǎn)單無向圖,P1和P2是圖G中頂點(diǎn)x到頂點(diǎn)y的兩條路, 如果P1和P2除了頂點(diǎn)x和頂點(diǎn)y以外沒有相同的頂點(diǎn)和邊, 那么稱P1和P2是內(nèi)部不相交的.設(shè)T1,T2，…，Tk是圖G的一組生成樹，對(duì)圖G中的任意兩個(gè)頂點(diǎn)r和v, 如果T1,T2，…，Tk中頂點(diǎn)r到頂點(diǎn)v的路兩兩內(nèi)部不相交, 那么稱T1,T2，…，Tk是圖G的一組完全獨(dú)立支撐樹.

①圖G的任意導(dǎo)出子圖G[Vi]是連通的；

②二分圖B(Vi，Vj)的每一個(gè)連通分支H滿足|E(H)|≥|V(H)|,i=1,2,3，…，k且i≠j.

定理1.1[1]連通圖G有k個(gè)完全獨(dú)立支撐樹，當(dāng)且僅當(dāng)G的頂點(diǎn)集V(G)存在CIST劃分(V1,V2,…，Vk).

定理1.2[1]設(shè)T1,T2，…，Tk是圖G的一組生成樹，T1,T2，…，Tk是一組完全獨(dú)立支撐樹當(dāng)且僅當(dāng)T1,T2，…，Tk是邊不相交的, 并且圖G中任意頂點(diǎn)v僅在最多一個(gè)生成樹Ti中滿足dTi(v)>1.

2 克萊因瓶網(wǎng)絡(luò)的完全獨(dú)立支撐樹

定理：K(m×n)有兩個(gè)完全獨(dú)立支撐樹，這里m≥3,n≥3.

證明：我們將用紅、藍(lán)兩種顏色對(duì)邊進(jìn)行染色, 之后將點(diǎn)按照其關(guān)聯(lián)的多數(shù)邊的顏色染色.我們將證明所有紅(藍(lán))邊導(dǎo)出K(m×n)一棵支撐樹，并且這兩棵支撐樹是完全獨(dú)立的，從而該定理得證.下面按照參數(shù)的奇偶性，將K(m×n)分為三類，然后依次進(jìn)行證明.

(1)K(2k×n),k≥2,n≥3的染色規(guī)則：

1)給下列集合中的邊染為紅色：

2)給下列集合中的邊染為藍(lán)色：

3)不染色的邊有兩條：

((0,0)，(2k-1,n-1))以及((0,n-1),(2k-1,0)).

圖3給出了按照上述方法所得的染色.

圖3 K(2k×n),k≥2,n≥3的一組完全獨(dú)立支撐樹Fig.3 Two CISTs of K(2k×n),k≥2,n≥3

(2)K((2k+1)×2t)的染色規(guī)則,這里k≥1,t≥2.

1)K((2k+1)×4),k≥1的染色規(guī)則：

a)染紅色的邊：

b)染藍(lán)色的邊：

c)不染色的邊：

((0,0),(2k,3))以及((0,1),(2k,2)).

圖4給出了按照上述方法所得的染色.

圖4 K((2k+1)×4),k≥1的一組完全獨(dú)立支撐樹Fig.4 Two CISTs of K((2k+1)×4),k≥1

2)K((2k+1)×(4t+2))的染色規(guī)則, 這里k≥1,t≥1.

a)下列集合中的邊染為紅色：

b)下列集合中的邊染為藍(lán)色：

c)不染色的邊有兩條, 分別為((0,0),(2k,4t+1))以及((0,2t),(2k,2t+1)).

按照該染色方法我們得到圖5.

3)K((2k+1)×4t)的染色規(guī)則,k≥1,t≥2.

a)下列集合中的邊染為紅色：

b)下列集合中的邊染為藍(lán)色：

c)不染色的邊有兩條, 分別為：((0,0),(2k,4t-1))和((0,2t),(2k,2t-1)).

實(shí)際上，K((2k+1)×4t)的染色方案可從圖5所示的K((2k+1)×(4t+2))染色方案得到：圖5所示的j列，其中j=2t-2,2t-1,…,2t+3,被圖6所示的4列取代.后面的列按照順序重新標(biāo)號(hào)即可.

圖5 K((2k+1)×(4t+2)),k≥1的一組完全獨(dú)立支撐樹Fig.5 Two CISTs of K((2k+1)×(4t+2)),k≥1,t≥1

圖6 替換結(jié)構(gòu)Fig.6 Replacement structure

(3)K((2k+1)×(2t+1))的染色規(guī)則,這里k≥1,t≥1.

1)K((2k+1)×3),k≥1的染色規(guī)則:

a)下列集合中的邊染為紅色：

∪j=0.2((0,j),(1,j))

b)下列集合中的邊染為藍(lán)色：

((0,0),(2k,2))

c)不染色的邊有兩條, 分別為((0,0),(0,2)) 和((1,1),(1,2)) .

圖7給出了按照該染色方法所得圖例.

圖7 K((2k+1)×3),k≥1的一組完全獨(dú)立支撐樹Fig.7 Two CISTs of K((2k+1)×3),k≥1

2)K((2k+1)×(2t+1)) ,k≥1,t≥2,的染色規(guī)則：

a)下列集合中的邊染為紅色：

b)下列集合中的邊染為藍(lán)色：

c)不染色的邊有兩條, 分別為((1,0),(1,2t)) 和((2k,0),(2k,2t)) .

圖8給出了這種情形下的染色方案.

圖8 K(2k+1)×(2t+1),k≥1,t≥2的一組完全獨(dú)立支撐樹Fig.8 Two CISTs of K(2k+1)×(2t+1),k≥1,t≥2

可以驗(yàn)證, 紅(藍(lán))色邊各導(dǎo)出K(m,n)的一棵生成樹, 在每組染色過程中不被染色的邊有兩條.因?yàn)镵(m,n)有2mn條邊, 兩棵支撐樹占用了2mn-2條邊, 所以還剩兩條邊不在兩個(gè)完全獨(dú)立支撐樹中.下面我們證明不同顏色的邊及所有點(diǎn)構(gòu)成的兩顆樹是圖的一組完全獨(dú)立支撐樹.

可以看出我們沒有對(duì)邊進(jìn)行重復(fù)染色, 所以兩個(gè)完全獨(dú)立支撐樹中沒有重復(fù)的邊.從圖中可以看出，藍(lán)色頂點(diǎn)在紅色邊導(dǎo)出的樹中為葉子節(jié)點(diǎn), 在藍(lán)色邊導(dǎo)出中為中間節(jié)點(diǎn)；紅色頂點(diǎn)在藍(lán)色邊導(dǎo)出中為葉子節(jié)點(diǎn)，在紅色邊導(dǎo)出中為中間節(jié)點(diǎn)，即同一頂點(diǎn)只在藍(lán)邊圖或紅邊圖中的一個(gè)圖度數(shù)大于1, 根據(jù)定理1.2，我們可以判斷這兩個(gè)支撐樹是K(m,n)的一組完全獨(dú)立支撐樹.故定理得證.

3 結(jié) 論

顯然K(m,n)的連通度與其參數(shù)有關(guān)，但是基于完全獨(dú)立支撐樹的角度, 可以確定它均存在兩個(gè)完全獨(dú)立支撐樹，且最多只存在兩個(gè).通過對(duì)m和n的奇偶性進(jìn)行分類，可以分為四大類，即奇×奇、奇×偶、偶×奇、偶×偶.實(shí)際操作中, 我們把偶×奇、偶×偶?xì)w為一類，找到了K(2k×n),k≥2,n≥3的一組完全獨(dú)立支撐樹.之后把奇×偶的情形又分為兩個(gè)子類, 找到了K((2k+1)×(4t+2))和K((2k+1)×4t)，k≥1,t≥1的一組完全獨(dú)立支撐樹.最后找到了K((2k+1)×(2t+1)),k≥1,t≥1的一組完全獨(dú)立支撐樹.至此, 我們找到了K(m,n)一組完全獨(dú)立支撐樹.