（2）节点连通度。

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

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

　　（1）算法的基本思想。

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

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

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

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

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

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

　　第2步：对所有节点对，，重复上述步骤计算，最后计算：，即网络的边连通度。需要注意的是：由于，对于含有个节点的图，第2步中需要计算的共有个。

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

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

　　由构图规则可知，在新的网络中，从发点到收点的包含节点的一条路由，必定包含一个顶点拆成的两部分之间的那条弧。并且原图的一对相邻点及其间的边被转换成等效的由4个节点组成的“8”字形有向回路。因此，一个链路割集在切断中到的所有有向路由方面，与在原始无向图中去掉节点割集有相同作用，即中等于中。综上，可得网络节点连通度算法计算步骤如下。

　　第1步：对原网络的任一节点对和，按上述规则构造新的有向网络，并用标号法求中分离和的最小链路数，即中分离和的最小割点集点数。

　　第2步：对所有节点，计算，即得的边连通度。

　　3 结论

　　本文讨论了通信网络可靠性的层次划分与影响因素，针对性的分析了拓扑层可靠性的指标与测度，指出了“连通度”作为拓扑层可靠性基础测度，以及其对其它测度设计的重要性。同时，详细分析了节点连通度与边连通度的计算思想与算法步骤。最后，通过一个相对简单的算例演示了通过边与节点连通度计算来评价某一通信网络拓扑可靠性的主要流程。

　　参考文献

　　[1]罗鹏程，金光，周经伦.通信网可靠性研究综述[J].小型微型计算机系统，2000，21（10）：1073-1077.

　　[2]陈建国.通信网络拓扑抗毁性评估算法研究[J].通信系统与网络技术，2006，32（1）：6-7.

　　[3]饶育萍，林竞羽，周东方.网络抗毁度和节点重要性评价方法[J].计算机工程，2009，35（6）：14-16.

---

期刊库（http://www.zgqkk.com），是一个专门从事期刊推广、投稿辅导的网站。
　　本站提供如何投稿辅导，寻求投稿辅导合作，快速投稿辅导，投稿辅导格式指导等解决方案：省级投稿辅导/国家级投稿辅导/核心期刊投稿辅导//职称投稿辅导。

---

　　【免责声明】本文仅代表作者本人观点，与投稿辅导_期刊发表_中国期刊库专业期刊网站无关。投稿辅导_期刊发表_中国期刊库专业期刊网站站对文中陈述、观点判断保持中立，不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。请读者仅作参考，并请自行承担全部责任。