隨機流網絡的d—下界點

潘程

【摘要】 本文主要對隨機流網絡的d-下界點進行了研究。首先，根據隨機流網絡的最大流，對容量向量進行了分類，并討論了不同類之間的關系，給出了d-下界點與d-上界點的另一種定義方式。其次，改進了容量向量中尋找極小元（極大元）的算法，也是求d-下（上）界點的方法。

【關鍵詞】 隨機流網絡 最小路 d-下界點

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

一、隨機流網絡的容量向量

1.1 容量向量的比較

定義1[3] 設容量向量X=（x1，…，xn）與Y=（y1，…，yn），如果滿足xi≤yi，i=1…n，那么稱X與Y可比較，即X≤Y（或X≥Y）；否則，稱X與Y不可比較。設X≤Y，若至少存在一個元件ai的當前容量x1Y）?；谏鲜鲫P系，所有的容量向量可以構成一個偏序集。對于所有的容量向量構成集合的任意子集，根據偏序關系，必然存在最大（或最小）的不可比元，在這里本文叫做極大元（或極小元）。

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

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

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

1.2 容量向量的分類

在網絡的容量向量X=（x1，…，xn）與最大流量d之間可以建立一個映射。如果這個映射記為f，那么X對應唯一一個非負整數d，把這個對應記作f（X）=d，稱f（X）為最大流量函數。定義2設g（X）是定義在容量向量上的實函數，如果X≥Y，就有g（X）≥g（Y），稱g（X）是關于容量向量的增函數。

顯然，最大流量函數f（X）是一個整值增函數。

令Ωd={X|f（X）=d}，對于所有容量向量構成的集合Ω，把f（X）相等作為等價關系。集合Ω可以分成若干個等價類，即。顯然，Ωd中的容量向量都是等價的。

1.3 不同類的容量向量之間關系

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

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

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

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

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

定理2說明相鄰等價類Ωd與Ωd+1中容量向量的關系。

二、 隨機流網絡的d-下界點

定義3 集合Ωd={X|f（X）=d}的極大元稱為d-上界點；集合Ωd={X|f（X）=d}的極小元稱為d-下界點。

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

2.1 d-下界點的計算

文獻[1]與文獻[2]分別給出了d-下界點與d-上界點的必要條件，據此可求得d-下界點與d-上界點。設F=（f1，f2，…，fk）為最小路MPj =1，2，…，k的流向量，Cj為網絡最小割集。

定理 3.1[1] 如果X為隨機流網絡的d-下界點，那么存在一個流量為d的可行流向量F=（f1，f2，…，fk），滿足（3.1）式：

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

定理 3.2[1] Amin是隨機流網絡的d-下界點集。

上面兩個定理說明利用網絡的最小路可求得d-下界點，文獻[2]利用最小割可求得d-上界點，這里不再贅述。事實上，也可以通過最小路（最小割）求出d-上界點（d-下界點），不過過程比較繁瑣。

2.2 d-下界點與其它容量向量的關系

設容量向量X=（x1，…，xn）∈Ωd，在X下，把一個元件ai由當前容量xi變成xi+1其他不變，即網絡的容量向量變為X'=（x1，…，xi+1，…，xn）。如果X仍然屬于Ωd，就稱X（或元件ai的容量）是可擴充的；否則稱X（或元件ai的容量）不能擴充。

定理4 設X為d-下界點，如果容量向量Y∈Ωd且Y>X，那么網絡所有的最小路MPj，至少存在一個元件ai∈MPj的容量不能擴充。

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

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

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

三、展望

本文主要對d-下界點進行了討論，對d-上界點的討論也是很有意義的。在限制條件下的計算網絡可靠性也是很重要的。因此對隨機流網絡的限制條件下的d-下界點進行討論勢在必行，這樣才能從根本上探究隨機流網絡可靠度的計算問題。

參 考 文 獻

[1]孫艷蕊，張祥德. 利用極小割計算隨機流網絡可靠度的一種算法[J]，系統工程學報，2010，25（2），284-288.