高 煒

(云南師范大學(xué) 信息學(xué)院， 云南 昆明 650500)

在計(jì)算機(jī)傳輸網(wǎng)絡(luò)中， 由于受單個(gè)通道容量的限制而無(wú)法傳輸大數(shù)據(jù)包. 因此， 一般需要將數(shù)據(jù)進(jìn)行切割， 分成若干個(gè)小塊再由各個(gè)通道分別傳輸， 最后在目的地節(jié)點(diǎn)進(jìn)行數(shù)據(jù)的重新組裝. 然而， 在理論上對(duì)網(wǎng)絡(luò)數(shù)據(jù)傳輸問(wèn)題進(jìn)行數(shù)學(xué)建模， 用頂點(diǎn)代表節(jié)點(diǎn)， 用邊代表兩個(gè)節(jié)點(diǎn)之間有直接的數(shù)據(jù)傳輸通道相連. 由此， 整個(gè)傳輸網(wǎng)絡(luò)用一個(gè)圖來(lái)表示， 而數(shù)據(jù)傳輸問(wèn)題則等價(jià)為圖上的分?jǐn)?shù)流問(wèn)題. 于是就可用分?jǐn)?shù)因子的存在性來(lái)間接刻畫網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)目尚行? 有關(guān)這方面的研究成果可參閱文獻(xiàn)[1—4].

而由于本文只考慮有限無(wú)環(huán)無(wú)重邊的無(wú)向圖， 也就是說(shuō)，假設(shè)兩節(jié)點(diǎn)之間數(shù)據(jù)傳輸是雙向的. 設(shè)G=(V(G)，E(G))是一個(gè)圖， 其中V(G)和E(G)分別為頂點(diǎn)集和邊集. 對(duì)任意頂點(diǎn)子集S， 設(shè)G[S]是S的導(dǎo)出子圖，dS(x)和NS(x)分別表示頂點(diǎn)x在G[S]中的度和鄰域集. 設(shè)δ(G)=min{d(x)：x∈V(G)}為圖G的最小圖. 對(duì)于G的不相交子集S，T， 設(shè)eG(S，T)為一端在S， 而另一端在T的邊的數(shù)量. 設(shè)H為邊集合，eH(S，T)表示一端在S， 另一端在T， 且屬于集合H的邊的數(shù)量. 并設(shè)n=|V(G)|表示圖的階.

特別地， 在上述定義中取m=1， 則分?jǐn)?shù)(k，m)-消去圖、 分?jǐn)?shù)(k，m)-覆蓋圖和分?jǐn)?shù)(k，m)-一致圖分別為分?jǐn)?shù)k-消去圖、 分?jǐn)?shù)k-覆蓋圖和分?jǐn)?shù)k-一致圖.

而聯(lián)結(jié)數(shù)是圖網(wǎng)絡(luò)的重要指標(biāo)， 用于衡量網(wǎng)絡(luò)的穩(wěn)定性和易受攻擊程度.

本文的主要目的是研究聯(lián)結(jié)數(shù)和分?jǐn)?shù)k-因子存在性的聯(lián)系， 我們將分別給出分?jǐn)?shù)(k，m)-覆蓋圖的聯(lián)結(jié)數(shù)條件， 進(jìn)而得到分?jǐn)?shù)(k，m)-一致圖的條件.

1 主要結(jié)果

本文的主要結(jié)論陳述如下.

定理1和定理2的證明主要通過(guò)以下引理的證明來(lái)完成.

而引理1和引理2的證明需要如下已知結(jié)果的支持.

引理3設(shè)k≥1，m≥0為兩個(gè)整數(shù). 設(shè)G是一個(gè)圖. 則G是分?jǐn)?shù)(k，m)-覆蓋圖當(dāng)且僅當(dāng)對(duì)任意含有m條邊的子圖H和任意S?V(G)有

(1)

其中T={x：x∈V(G)-S，dG-S(x)≤k-1}.

2 定理1和定理2的證明

其中T={x：x∈V(G)-S，dG-S(x)≤k-1}. 顯然有T≠φ.

設(shè)dmin=min{dG-S(x)：x∈T}， 則有dmin≤k-1. 利用引理4和引理5， 并且重復(fù)文獻(xiàn)[5]中對(duì)分?jǐn)?shù)(k，m)-消去圖的證明過(guò)程， 便可得到引理1和引理2. 同時(shí)， 利用文獻(xiàn)[5]中給出的一些反例， 也可以說(shuō)明引理1和引理2中對(duì)分?jǐn)?shù)(k，m)-覆蓋圖的聯(lián)結(jié)數(shù)條件是緊的.

最后， 把引理1和引理2與文獻(xiàn)[5]中的關(guān)于分?jǐn)?shù)(k，m)-消去圖的兩個(gè)結(jié)論(該文中的定理5和定理6)相結(jié)合， 即可得到定理1和定理2. 同時(shí)， 文獻(xiàn)[5]的一些反例同樣可以說(shuō)明定理1和定理2中對(duì)分?jǐn)?shù)(k，m)-一致圖的聯(lián)結(jié)數(shù)條件也是緊的.

3 討論

本文研究發(fā)現(xiàn)， 文獻(xiàn)[5]中關(guān)于分?jǐn)?shù)消去圖的證明過(guò)程， 可以完全用于引理1和引理2中關(guān)于分?jǐn)?shù)(k，m)-覆蓋圖的聯(lián)結(jié)數(shù)條件的證明. 這讓我們自然發(fā)出一個(gè)疑問(wèn)：是否所有關(guān)于分?jǐn)?shù)(k，m)-消去圖的結(jié)果都可以套用到分?jǐn)?shù)(k，m)-覆蓋圖， 進(jìn)而得到分?jǐn)?shù)(k，m)-一致圖的結(jié)論？這個(gè)問(wèn)題的答案是否定的.

要解答這個(gè)問(wèn)題， 我們需要從分?jǐn)?shù)(k，m)-消去圖和分?jǐn)?shù)(k，m)-覆蓋圖的充要條件入手. 設(shè)k≥1，m≥0為兩個(gè)整數(shù). 設(shè)G是一個(gè)圖. 則G是分?jǐn)?shù)(k，m)-消去圖當(dāng)且僅當(dāng)對(duì)任意含有m條邊的子圖H和任意S?V(G)有：

(2)

其中T={x：x∈V(G)-S，dG-S(x)-dH(x)+eH(x，S)≤k}(可以直接驗(yàn)證這里的集合T可以修改為T={x：x∈V(G)-S，dG-S(x)-dH(x)+eH(x，S)≤k-1}). 然而， 在處理大部分分?jǐn)?shù)(k，m)-消去圖相關(guān)問(wèn)題時(shí)， 我們傾向于使用另外一種形式的充分必要條件：G是分?jǐn)?shù)(k，m)-消去圖當(dāng)且僅當(dāng)對(duì)任意含有m條邊的子圖H和任意不交子集S，T?V(G)有：

也就是說(shuō)， 任意S和T={x：x∈V(G)-S，dG-S(x)≤k}， 與任意不相交的S，T?V(G)是等價(jià)的. 顯然， 若對(duì)任意不相交的S，T?V(G)， (2)式成立， 則對(duì)于任意S和T={x：x∈V(G)-S，dG-S(x)≤k}， 不等式(2)也能成立.

反之， 假設(shè)對(duì)于任意S和T={x：x∈V(G)-S，dG-S(x)≤k}， (2)式成立. 那么對(duì)于任意的不相交子集S，T?V(G)， 把T分成兩個(gè)部分：

T1={x∈V(G)-S|dG-S(x)-dH(x)+eH(x，S)≤k}；

T2={x∈V(G)-S|dG-S(x)-dH(x)+eH(x，S)>k}.

對(duì)于第1部分T1， 根據(jù)假設(shè)條件可得：

(3)

對(duì)于第2部分T2， 由它的定義得：

(4)

于是， 立刻可以用(3)式和(4)式， 驗(yàn)證(3)式+(4)式=(2)式， 由此可知關(guān)于分?jǐn)?shù)(k，m)-消去圖， 可以驗(yàn)證不同的充要條件之間的等價(jià)性.

T1={x∈V(G)-S|dG-S(x)≤k-1}；

T2={x∈V(G)-S|dG-S(x)≥k}.

對(duì)于第1部分T1， 根據(jù)假設(shè)條件可得：

(5)

對(duì)于第2部分T2， 由它的定義得：

(6)

通過(guò)(5)式+(6)式和(1)式對(duì)比， 發(fā)現(xiàn)缺少eH(S，T2)項(xiàng). 由此可知， 關(guān)于分?jǐn)?shù)(k，m)-覆蓋圖的充要條件中的任意S和T={x：x∈V(G)-S，dG-S(x)≤k-1}不能改為任意的不相交子集S，T?V(G).

事實(shí)上， 大部分關(guān)于覆蓋圖的情況需要重新考慮， 并不能把消去圖的證明過(guò)程照搬. 本文的結(jié)論只是湊巧， 原來(lái)的證明過(guò)程可以直接拿來(lái)用. 由于定理1和定理2的結(jié)論只對(duì)小m才能滿足， 即被條件k+1≥2m或k+2≥2m所限制， 因此， 給出如下的開問(wèn)題作為本文的結(jié)束.

開問(wèn)題對(duì)于一般的m， 需要什么樣的聯(lián)結(jié)數(shù)條件才能保證G是分?jǐn)?shù)(k，m)-覆蓋圖和分?jǐn)?shù)(k，m)-一致圖？