随机流网络的d—下界点
2014-04-29潘程
潘程
【摘要】 本文主要对随机流网络的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的当前容量x1
定理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.
