英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料
一种获取网络中最大多路由流的方法
Wataru Kishimoto *
Department of Information amp; Communication Engineering, Tamagawa University, Tamagawagakuen, Machida-shi, Tokyo 194, Japan n
摘要
在通信网络中，多路径信道比普通信道在链路或终端故障方面更可靠。一个m路径流对应于一组m路径通道，其中m是它们所经过的不相交路径的数量。Kishimoto和Takeuchi证明了它们的最大流量最小割定理。我们展示了如何获得两个顶点之间的最大m路径流量。首先，我们通过计算普通流量最大值的m倍来求两个顶点之间的m路径流量的最大值。然后，构造出具有最大值的m路网络流。该方法的正确性为Kishimoto和Takeuchi的最大流最小割定理提供了另一个证明。m个路由流的最大值对应于两个终端之间的m个路由信道的最大容量。copy; 1996 John Wiley amp; Sons, Inc
1.介绍
在本文中，我们将在以下情况下考虑网络中的流问题:我们必须分析通信网络，尤其需要在指定的一对终端s和t之间具有抗物理故障的健壮通道。我们可以采用多路通道，即将s和t之间的通信路径物理地分隔为一个信道，使该信道始终能经受个链路故障，我们称这样的一组通信路径为路由通道。
网络是一个加权图，其中一个称为边容量的正实数与其每条边相关联。我们可以把网络作为通信网络的抽象模型。然后，两个顶点之间的流对应于两个顶点对应的终端之间的一组通信路径。在网络中，Kishimoto和Takeuchi将顶点不相交版本的路径流和边不相交版本的路径流定义为通信网络中的一组路径通道[8]。此外，在定义了路由容量之后，对于一个切割，他们在两个版本中都展示了路径流的最大流最小切割定理[8]。
我们展示了如何获得两个顶点之间的最大路径流。首先，我们通过计算普通流的最大值来计算两个顶点之间的路径流的最大值。然后，构造出具有最大值的路径流。该方法的正确性为Kishimoto和Takeuchi的最大流量最小割定理提供了又一个证明。路径流的最大值对应两个终端之间路由通道的最大容量。
第二部分给出了本文的必要条件。第三节描述了如何在边不相交版本中获得最大路径流。第四节讨论了顶点不相交版本中的路径流。第5节描述无向网络中的路径流。
2. 初步结果
2.1 网络中的流量
本文中的符号和术语是基于[2]的。令是一个有顶点的图，顶点集设为，边集设为，则是一个网络，其中表示边容量。如果是中的一组边，展开得到，我们称为的容量。当是定向的。是有向的，当是无向的，是无向的。
定义2.1 令和是两个网络。如果是子图，且对于中的每个边有，我们将称为的子网络。
定义2.2 令，，hellip;, 是网络。然后表示的顶点集, 是的边集。网络,hellip;, 的总和定义为 网络，使得如果是的顶点集，是的边集
当时，
当时，令
定义2.3 令为网络，为子网络。如果是一个网络，使得和的和是。从中减去等于。
令为网络的顶点集的非空真子集，为的补集。如果是有方向的，那么的一个切割就是一组边的集合，且每条边都从中的一个顶点指向中的一个顶点。如果是无向的，的一个切割是一组边的集合，且每条边的其中一个顶点在中，另一个顶点在中。我们用表示的补集，其中是的子集。与顶点相关联的边集是的关联割，并写作。我们说的度数是中的边数。特别是在有向网络中，一组从中射出的边称为v的出射截割，一组指向的边称为v的内射截割。则表示的出射截割，表示的内射截割。我们将扩展为和的最小值，并将其定义有向网络中的一个顶点的容量，即：
如果是无向的，则定义。在本文中，我们将混合切割定义如下：
定义2.4[8] 在有向网络中，令和为的顶点集的两个非空真子集，使得。混合切割是一组由从中的顶点指向中的顶点的边，以及所有在中的顶点组成.对于此混合切割，我们使用符号表示。
如果是无向网络，则混合切割是一个包含边和顶点的集合，每个边的两个端点分别在和中，每个顶点都是在集合中。如果，则混合切割符合普通切割。如果，，且顶点是源点，顶点是汇点，我们称为切割或混合切割。由边和顶点组成的集合S的所有边容量和所有顶点容量的总和称为集合的容量，并将扩展为。切割或混合切割的容量简单地用代替来表示。
此外，我们给出一些定义：
定义2.5 如果网络的每个边缘具有相同的容量，则称该网络的值为。
定义2.6 如果无向网络的顶点的每个关联割都具有相同的容量，则其N的值将为。
如果无向图的每个顶点的度数都是相同的值，则称其为度数的正则。 无向图的因子是度数的扩展正则子图。
定义2.7[8] 无向网络的值为的1因子网络是值为的统一子网络，使得子网络的图是网络图的1因子。
如果无向图的节点集可以划分为两个不相交的子集和,使得它的每个边的两个端点分别在和中，则将其成为二分图。我们将二部图称为，其中是的边集。如果无向网络的图是二分图，则称其为二分图。对于二分图，如果中没有一对边具有公共端点，则其边集的子集与匹配。然后，中的每个边的端点被认为是饱和的。
下一个引理是正则二分图的Konig定理的变体
引理2.8[8] 如果二分网络的值是的偶数，则是通过对反复进行以下运算获得的1因子网络的有限数量之和。这些1因子网络的总和值是。
(操作)
- 找到一个匹配的，其中中的所有顶点都是饱和的。
- 通过将中的最小边容量作为中所有的边容量来获得1因子网络。
- 从减去1因子网络
(停止操作)
从现在开始，被假定为有向网络。从顶点到顶点的流（顶点是源点，顶点是汇点）通常被定义为从网络的边集到非负实数的函数。但是，在本文中，我们将流定义如下：
定义2.9[8] 具有值的路径流是值的统一网络，因此是从顶点到顶点的有向路径。
定义2.10[8] 从顶点到顶点的流定义为网络，它是路径流,，hellip;, 的总和。这些路径流之和被定义为。
如果是网络的子网，则我们说是中的一个流。网络中从到的流的最大值用表示，称为终端容量，或者称为从到的容量。根据最大流量最小割定理，从到的的容量等于中割的最小容量[5]。
定义2.11 令为网络的割或混合割。令为的子网络，使得的每个边都在或与中的一个顶点有关。 然后，称为的截流，其值由定义。
显然，的截流最大值为。 可以将的切向流视为一对顶点集之间而不是一对顶点之间的流。 在图1的网络中，我们考虑一个割集，其中。 图1（b）的网络是的截流，其值为12。
2.2 路流
在[8]中给出了该小节的所有结果（定义，定理和引理，以及计算切割的边沿m路径容量的方法）。
定义2.12[8] 从到的基本路由流定义为的子网，它是个边不相交的路径流之和，每个边流具有相同的值。“路径流和是边不相交的，”这意味着和是从到的不相交的路径。基本m路由流的值定义为。
定义2.13[8] 从到的边-路由流是的子网，因此该子网是从到的基本边-m路由流的总和。这些基本的边-路由流的值之和称为边-路由流的值。
在定义2.12和2.13中，通过将术语“edge-m-route”和“edge-disjoint”替换为“vertex-m-route”和“ internally-disjoint”，定义了基本的顶点-m-路由流和顶点-m路由流。
图2（a）的和图2（b）的的网络都是从到的基本边-3路由流，并且也是基本顶点-3路线流。图2（c）的网络是边-3路由流，其等于和之和。和的值分别为3和9。因此，的值为12。
两个顶点之间的边-m-路由流的最大值对应于具有m路由通信通道的两个终端之间的最大通信量。
定义2.14[8] 令是从到的一个流或者是一个切割流，如果
对于的每条边，其中的值，我们称为边-级流或边-级切割流。此外除了，),如果
为在中的每个顶点的顶点，和除外,我们现在叫为一个点--级流或点--级切割流。
显然，边--流是边--级流，而点--路由流是点--级流。
定义2.15[8] 一个切割的边--路由容量是边--级切割流的最大值，而一个混合切割的点--路由容量是点--级切割流的最大值。
由于边-m-级割流是割流，因此我们有，其中代表的边-路由容量。类似地，我们有，其中代表的点-路由容量。考虑图1(a)中的。可以很容易地看出 图1(b)的切割流是在中的最大的边-3-级切割流，其中。所以在中，。
定理2.16[8] 从到的边--级流最大值等于切割的边-路由容量的最小值。
定理2.17[8] 从到的边--路由流最大值等于切割的边-路由容量的最小值。
定理2.17是定理2.16的推论，因此，我们得到以下结果：边--级流最大值等于边--路由流的最大值。第3.2节中的方法对此给出了的建设性证明。定理2.16和2.17也适用于点-路由流。
在下文中，我们考虑如何评估切割的边-路由容量。令中的切割的所有边都是,,hellip;,，使得
如果，我们定义
(切割的边-路由容量的评估)
1 序列，即的序列定义如下：
2 我们定义路由索引为的最小值，使得
注意到如果，我们定为任一序列定义
3 那么，是，即的边-路由容量。
(评估结束)
因为，所以我们有。这意味着总有满足。且当且仅当时，。下一个引理对于下面的讨论是有用的:
引理2.18[8] 令为的切割的路由索引。
1.当时，
2. 当时，
我们给出了边-路径容量方法正确性的证明草图：如果是切割的边--级切割流的容量，则满足
然后，可以很容易地看出，存在一个边--级切割流，其上的值满足。因此，由于，所以的最大值满足等式,并且等于边--级切割路由容量，足以表明等于,。由于使用引理2.18 ，,hellip;, ,以及，,hellip;, ，用这些代替与，我们有
-
因此，对于给定的，满足。此外，由于方程式，
所以，。
还以类似于边-路由容量的方式评估了混合切割的点-路由容量。考虑在中具有边,,hellip;,，和顶点,,hellip;,，的混合切割。为了我们的目的，我们用，，hellip;,,和，，hellip;，表示容量，通过，，hellip;, 以值的非递增顺序索引。然后，和使用代替，我们可以将边-路由容量的方法应用于点-路由容量[8]。
3.如何获得最大边-路由流
3.1 边-路由流量最大值的评估
我们开发了一种方法，用于评估指定顶点对之间的边-路由流量的最大值。该方法包括计算这些顶点之间的普通流动的最大值。如果在中具有值的最大流量的边没有容量大于，则最大流量是最大的边-级流量，因此是边-路由流量的最大值。否则，在将每个大于的边容量设置为正好为之后，我们评估中的最大流量，并检查流量的边容量是否不大于其值的。如果边的容量大于该值的，则必须迭代相同的操作。但是，它并不总是以有限的迭代次数终止，如下所示。方法的关键点是：在迭代中，我们将边缘容量更新为，其中定义为
的值由等式（如果，则）。取而代之的是，如果我们给赋予上述值，其中是相对于容量的最大流的值，那么生成的算法并不总是以有限的迭代次数终止。由于是通过减小的边容量或等于来获得的，因此不大于。如果小于，那么中的最小割有一些边的容量大于中这些边容量。在中，这些这些边容量是。这样，算法将永不停止。因此，在第k次迭代中，如果，则；因为中的最小割具有一些容量为的边，得出，这意味着。为避免无限次迭代，我们假设在第k次迭代中，最小切割至少具有k条边，且容量大于，他由等式设置。相反，对于正确的假设，下面给出的方法最多以m次迭代结束的正确的解决方案。
[边-m路由流量的最大值的评估(方法)]
设s和t为不同的顶点，而顶点s为源，顶点t为给定网络中的汇点，且。
- 在中计算从到的普通流量的最大值。设该值为。
- 设。然后，按顺序对，重复以下过程，直到该过程停止。
（过程）令为通过将中的大于的边缘容量减小到而获得的网络。计算在中从到的普通流量的最大值，然后将该值设为。
- 如果
- 如果
(程序结束)
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[254384]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
