通信网络拓扑可靠性问题可抽象为图的可靠性问题，用图

G（V，E）来描述拓扑结构。

其中，

V 表示网络中节点的集合，例如用户终端、服务端、路由服务器等；E 表示连接网络

中节点的边（链路）集合。同时，本节主要讨论拓扑可靠性的非概率（静态）测度，即不考
虑上层业务或下层设备影响，将问题视角完全限定在拓扑层面。

 

　　目前，关于拓扑可靠性的静态测度研究很多，可谓仁者见仁，测度设计的侧重点各不
相同。例如：连通度（

vertex connectivity）、坚韧度（toughness）、完整度（integrity）、粘连

度（

tenacity）、离散数（scattering number）、膨胀系数（expansion coefficient）等。其中，连

通度是拓扑的基础指标，后续的测度均建立在对连通性的充分考虑的基础之上。因此，本节
以连通度为重点展开讨论。

 

　　

2.1 边连通度与节点连通度的定义 

　　（

1）边连通度。 

　　记为，其大小等于使网络成为不连通图所需去掉链路（边）的最少条数。它反映网络节
点间的内聚程度，是网络可靠性的一个基本度量指标。例如：通过分析可知，所示的网络分
割至少需要移除

3 条边，即边连通度。 

　　（

2）节点连通度。 

　　也成为点连通度，记为，其大小等于使网络成为不连通图所需去掉的节点的最少个数。
同理，网络的连通度。从某种意义上讲，点连通度是比边连通度更重要的网络可靠性度量指
标，这是因为在网络中去掉某个节点就意味着与之关联的所有链路将失去意义。

 

　　

2.2 边连通度与节点连通度的算法 

　　（

1）算法的基本思想。 

　　通常，要求给定网络的边连通度，需要首先确定任意不同两点的链路割集。设和是的两
个不同节点，所谓的一个链路割集是指这样的链路集合：若去掉其中所有链路，网络将被
分割成两个分支，一个包含节点；另一个包含节点。假设是中所有链路割集中链路的最小数，
则就是切断和之间所有路由所需从中删去的最小链路数，故网络的边连通度可按（

1）式计

算：

 

　　

2）网络边连通度计算步骤。 

　　由前所述，计算网络边连通度的算法思路是：先按标号算法求分离任两点的最小链路
数，然后，再求所有这些数的最小数即可。但是，上述求的算法是针对有向图给出的，而网
络边连通度是针对无向图的，因此，算法需首先将原无向网络转换成等效的有向网络。具体
计算步骤如下：

 

　　第

1 步：对给定网络，任选一对节点和，按下面的步骤求分离和的最小链路数：

 

①首先将转换成有向图。方法是：将链路集中以为端点的链路转换成中以为起点的到相应节
点的有向链路，将中以为端点的链路转换成中从相应节点到节点的有向链路，又将中其他
链路转换成中

2 条有向链路和。 

　　

②用标号算法，求中分离与的最小链路数。 

　　第

2 步：对所有节点对，，重复上述步骤计算，最后计算：，即网络的边连通度。需要

注意的是：由于，对于含有个节点的图，第

2 步中需要计算的共有个。 

　　

3）网络节点连通度计算步骤。 

　　算法的思路是：将割点问题转换成割边问题，从而使求网络节点连通度的问题转换成
求网络的边连通度问题。转换的方法是：在网络中任选一对节点和，首先，类似于边连通度
算法一样，将转换成有向网络，然后，再将构造另一个有向图，构图规则是：将中除和外
的每个节点拆成

2 个新的中的节点和，并用中的有向链路将它们连接起来。将中每一链路换

成中的链路，并把标为，标为。

 

　　由构图规则可知，在新的网络中，从发点到收点的包含节点的一条路由，必定包含一