潘程

【摘要】 本文主要對(duì)隨機(jī)流網(wǎng)絡(luò)的d-下界點(diǎn)進(jìn)行了研究。首先，根據(jù)隨機(jī)流網(wǎng)絡(luò)的最大流，對(duì)容量向量進(jìn)行了分類(lèi)，并討論了不同類(lèi)之間的關(guān)系，給出了d-下界點(diǎn)與d-上界點(diǎn)的另一種定義方式。其次，改進(jìn)了容量向量中尋找極小元（極大元）的算法，也是求d-下（上）界點(diǎn)的方法。

【關(guān)鍵詞】 隨機(jī)流網(wǎng)絡(luò) 最小路 d-下界點(diǎn)

隨機(jī)流網(wǎng)絡(luò)可靠度定義為終點(diǎn)獲得的流量不小于需求流量d+1的概率。很多文獻(xiàn)提出了現(xiàn)實(shí)生活中許多系統(tǒng)（如計(jì)算機(jī)系統(tǒng)、通訊系統(tǒng)、物流系統(tǒng)等）的性能指標(biāo)，并給出了一個(gè)較好的計(jì)算系統(tǒng)或者網(wǎng)絡(luò)模型的可靠度算法。然而，可靠度主要是通過(guò)求d-下界點(diǎn)或d-上界點(diǎn)進(jìn)行計(jì)算的，所以對(duì)d-下界點(diǎn)的討論是非常重要的。1、模型假設(shè)。在討論隨機(jī)流網(wǎng)絡(luò)的容量向量之前，對(duì)問(wèn)題做以下假設(shè)：（1）隨機(jī)流網(wǎng)絡(luò)的每一個(gè)邊可以取不同的容量，但每一個(gè)結(jié)點(diǎn)的容量沒(méi)有限制。（2）不同邊容量的取值是相互獨(dú)立的。（3）隨機(jī)流網(wǎng)絡(luò)的流在傳輸?shù)臅r(shí)候滿足流守恒。（4）元件aj的最大容量mi與當(dāng)前容量xi取值整數(shù)，且滿足1≤xi≤mi。2、符號(hào)說(shuō)明。G（V，E）， 表示頂點(diǎn)集為V ，弧集為E的圖所表示的網(wǎng)絡(luò)；M=（m1，…，mk） ，最大容量向量或系統(tǒng)狀態(tài)，即mi為元件aj的最大（承受）容量；X=（x1，…，xn）當(dāng)前容量向量或系統(tǒng)狀態(tài)，即xi為元件aj的當(dāng)前（承受）容量；MPj，隨機(jī)流網(wǎng)絡(luò)的第j條最小路；fj ， fj為網(wǎng)絡(luò)最大流量在MPj 上分配的流量；F=（f1，…， fK） ，分配在所有最小路上的流量fj構(gòu)成的向量；d，需要傳輸?shù)臄?shù)據(jù)量。

一、隨機(jī)流網(wǎng)絡(luò)的容量向量

1.1 容量向量的比較

定義1[3] 設(shè)容量向量X=（x1，…，xn）與Y=（y1，…，yn），如果滿足xi≤yi，i=1…n，那么稱(chēng)X與Y可比較，即X≤Y（或X≥Y）；否則，稱(chēng)X與Y不可比較。設(shè)X≤Y，若至少存在一個(gè)元件ai的當(dāng)前容量x1Y）。基于上述關(guān)系，所有的容量向量可以構(gòu)成一個(gè)偏序集。對(duì)于所有的容量向量構(gòu)成集合的任意子集，根據(jù)偏序關(guān)系，必然存在最大（或最?。┑牟豢杀仍?，在這里本文叫做極大元（或極小元）。

定理1 設(shè)容量向量構(gòu)成的集合Ω，Y為Ω中任意的非極小元，必然存在X∈Ω滿足Y>X。這個(gè)結(jié)論很顯然。對(duì)于非極大元具有類(lèi)似的性質(zhì)。由定理1可知，偏序集Ω中的所有元素可以分解成若干個(gè)子鏈。對(duì)于非極小元Y所在的子鏈，必然存在極小元X并且Y≥X。最后，通過(guò)X與所有子鏈的極小元比較得出Ω中的極小元X≥X。根據(jù)Y不是極小元，所以Y>X。推論1 如果Y為Ω中的非極小元，那么存在集合Ω中的極小元X滿足Y>X。設(shè)s個(gè)容量向量X1，…，Xs 放在容器Ω中，容器Θ最后用于存放d-下界點(diǎn)，X與Y表示容量向量。下面給出尋找極小元的算法1：

步驟0 在容器Ω中，取一個(gè)容量向量X移到容器Θ。步驟1 判斷Ω中是否還有容量向量：若有，轉(zhuǎn)到步驟2；反之，轉(zhuǎn)到步驟3。步驟2取Ω中一個(gè)的容量向量（設(shè)Y）與Θ中所有容量向量比較，并判斷：步驟2.1若Y與Θ中所有不可比較，把Y移到Θ中；否則，Y與Θ中某個(gè)容量向量（設(shè)X）可以比較，轉(zhuǎn)到步驟2.2。步驟2.2若Y

算法 1得到的容器Θ中所有容量向量就是所有極小元。如果把步驟2做一下改變，那么也可以得到所有極大元。

1.2 容量向量的分類(lèi)

在網(wǎng)絡(luò)的容量向量X=（x1，…，xn）與最大流量d之間可以建立一個(gè)映射。如果這個(gè)映射記為f，那么X對(duì)應(yīng)唯一一個(gè)非負(fù)整數(shù)d，把這個(gè)對(duì)應(yīng)記作f（X）=d，稱(chēng)f（X）為最大流量函數(shù)。定義2設(shè)g（X）是定義在容量向量上的實(shí)函數(shù)，如果X≥Y，就有g(shù)（X）≥g（Y），稱(chēng)g（X）是關(guān)于容量向量的增函數(shù)。

顯然，最大流量函數(shù)f（X）是一個(gè)整值增函數(shù)。

令Ωd={X|f（X）=d}，對(duì)于所有容量向量構(gòu)成的集合Ω，把f（X）相等作為等價(jià)關(guān)系。集合Ω可以分成若干個(gè)等價(jià)類(lèi)，即。顯然，Ωd中的容量向量都是等價(jià)的。

1.3 不同類(lèi)的容量向量之間關(guān)系

定理2 設(shè)容量向量集合Ωd與Ωd+1，d為非負(fù)整數(shù)，有以下結(jié)論：（1）設(shè)X為Ωd+1中的極小元，那么必然存在Y∈Ωd滿足X>Y；（2）設(shè)X為Ωd中的極大元，若Ωd+1非空，則必然存在Y∈Ωd+1滿足X

證明：（1）設(shè)X=（x1，x2，…，xn），根據(jù)最大流最小割定理，對(duì)于網(wǎng)絡(luò)的一個(gè)最小割集Cmin，那么最大流量。存在網(wǎng)絡(luò)的元件ak∈Cmin且Xk>0。令Y=（x1，…，xk-1，…，xn），因此在容量向量Y下，最大流量為

從而，Y∈Ωd。顯然，X>Y。

（2）X=（x1，x2，…，xn）是集合Ωd中的極大元，即在X下，網(wǎng)絡(luò)最大流量是d，那么存在最小割集C的元件容量之和等于d，并且不屬于最小割集C的元件的容量都為最大容量；否則與X為Ωd中的極大元矛盾。Ωd+1非空，所以X不是網(wǎng)絡(luò)的最大容量向量。在割集C中，至少存在一個(gè)元件ak的容量xk不是最大容量，取Y=（x1，…，xk+1，…，xn），網(wǎng)絡(luò)的最大流量為

從而，Y∈Ωd+1。顯然，X>Y。證畢。

定理2說(shuō)明相鄰等價(jià)類(lèi)Ωd與Ωd+1中容量向量的關(guān)系。

二、 隨機(jī)流網(wǎng)絡(luò)的d-下界點(diǎn)

定義3 集合Ωd={X|f（X）=d}的極大元稱(chēng)為d-上界點(diǎn)；集合Ωd={X|f（X）=d}的極小元稱(chēng)為d-下界點(diǎn)。

上述定義與文獻(xiàn)[1-2]中是等價(jià)的，d-上界點(diǎn)（d-下界點(diǎn)）就是Ωd={X|f（X）=d}的極大（極小元）。

2.1 d-下界點(diǎn)的計(jì)算

文獻(xiàn)[1]與文獻(xiàn)[2]分別給出了d-下界點(diǎn)與d-上界點(diǎn)的必要條件，據(jù)此可求得d-下界點(diǎn)與d-上界點(diǎn)。設(shè)F=（f1，f2，…，fk）為最小路MPj =1，2，…，k的流向量，Cj為網(wǎng)絡(luò)最小割集。

定理 3.1[1] 如果X為隨機(jī)流網(wǎng)絡(luò)的d-下界點(diǎn)，那么存在一個(gè)流量為d的可行流向量F=（f1，f2，…，fk），滿足（3.1）式：

令A(yù)={XF|F為可行流}，Amin={x|x為A的極小元}。

定理 3.2[1] Amin是隨機(jī)流網(wǎng)絡(luò)的d-下界點(diǎn)集。

上面兩個(gè)定理說(shuō)明利用網(wǎng)絡(luò)的最小路可求得d-下界點(diǎn)，文獻(xiàn)[2]利用最小割可求得d-上界點(diǎn)，這里不再贅述。事實(shí)上，也可以通過(guò)最小路（最小割）求出d-上界點(diǎn)（d-下界點(diǎn)），不過(guò)過(guò)程比較繁瑣。

2.2 d-下界點(diǎn)與其它容量向量的關(guān)系

設(shè)容量向量X=（x1，…，xn）∈Ωd，在X下，把一個(gè)元件ai由當(dāng)前容量xi變成xi+1其他不變，即網(wǎng)絡(luò)的容量向量變?yōu)閄'=（x1，…，xi+1，…，xn）。如果X仍然屬于Ωd，就稱(chēng)X（或元件ai的容量）是可擴(kuò)充的；否則稱(chēng)X（或元件ai的容量）不能擴(kuò)充。

定理4 設(shè)X為d-下界點(diǎn)，如果容量向量Y∈Ωd且Y>X，那么網(wǎng)絡(luò)所有的最小路MPj，至少存在一個(gè)元件ai∈MPj的容量不能擴(kuò)充。

證明：（反證法）假設(shè)存在一個(gè)最小路MPj，MPj中所有元件ai的容量由xi可以擴(kuò)充成yi，并且xi

令Y'（x1+1，…，xs+1，…，xn），有Y'≤Y。在Y下，可以分配的流向量為F=（f1，f2，…，fj-1，fj+1，fj+1，…，fk），那么隨機(jī)流網(wǎng)絡(luò)的最大流為（3.3）

由于Y'≤Y，所以Y的最大流大于等于d+1。這與容量向量Y∈Ωd矛盾。因此，命題成立。證畢。通過(guò)定理4可以看出，對(duì)于Ωd中的容量向量可以由d-下界點(diǎn)，根據(jù)定理4的必要條件進(jìn)行擴(kuò)充得到，并且隨機(jī)流網(wǎng)絡(luò)的最大流保持不變。由定理2可知，如果X=（x1，x2，…，xn）為（d+1）-下界點(diǎn)（d≥0），那么存在Ωd中的容量向量Y，有X>Y。根據(jù)推論1，對(duì)于Ωd中的容量向量Y，必然存在于Ωd中的極小元z滿足Y≥z。因此，有以下結(jié)論：推論2 如果X為（d+1）-下界點(diǎn)（d≥0），那么存在d-下界點(diǎn)z，有X>z。因此，對(duì)于Ωd+1中的容量向量，必然大于等于Ωd中的容量向量。同理，d-上界點(diǎn)也有類(lèi)似的關(guān)系，這里不再贅述。

三、展望

本文主要對(duì)d-下界點(diǎn)進(jìn)行了討論，對(duì)d-上界點(diǎn)的討論也是很有意義的。在限制條件下的計(jì)算網(wǎng)絡(luò)可靠性也是很重要的。因此對(duì)隨機(jī)流網(wǎng)絡(luò)的限制條件下的d-下界點(diǎn)進(jìn)行討論勢(shì)在必行，這樣才能從根本上探究隨機(jī)流網(wǎng)絡(luò)可靠度的計(jì)算問(wèn)題。

參 考 文 獻(xiàn)

[1]孫艷蕊，張祥德. 利用極小割計(jì)算隨機(jī)流網(wǎng)絡(luò)可靠度的一種算法[J]，系統(tǒng)工程學(xué)報(bào)，2010，25（2），284-288.