蔡学鹏， 刘梦瑶， 杜濛雨

新疆农业大学 数理学院， 乌鲁木齐 830052

在本文中， 术语图和网络可以互换使用． 所有的图都认为是无向的简单连通图， 对于未说明的图论符号和术语， 可参见文献[1-3]．

设G=(V(G)，E(G))是一个图． 对于图G中的任意顶点u∈V(G)， 设集合{v∈V(G){u}： (u，v)∈E(G)}和集合{(u，v)∈E(G)：v∈V(G){u}}分别表示顶点u的邻点集和邻边集， 记作NG(u)和NEG(u)．dG(u)=|NG(u)|称为图G中顶点u的度． 对于图G的子图K， 设

分别表示子图K在G中的邻点集和邻边集．

图G的经典连通度κ(G)和边连通度λ(G)是衡量网络可靠性和容错性的两个重要参数[4-5]． 连通度κ(G)和边连通度λ(G)越大， 网络的可靠性就越高． 但是， 这两个参数有明显的不足之处， 比如， 在互连网络的实际应用当中， 与一个处理器相连接的所有处理器(链路)同时发生故障的可能性较低， 所以用这两个参数衡量网络可靠性和容错性是不精确的． 为克服这些不足之处， 可以通过对G-S的每一个分支强加一些限制条件来推广图G的经典连通度(边连通度)， 这里S⊂V(G)(S⊂E(G))． 文献[6]首次考虑了这个问题并且提出了图G的条件连通度(边连通度)的概念．

设S⊂V(G)(S⊂E(G))且g是非负整数， 如果G-S是不连通的， 且G-S的每个连通分支中至少有g+1个顶点， 则称S是G的一个Rg-割(Rg-边割)． 若G存在Rg-割(Rg-边割)， 则G的所有Rg-割(Rg-边割)中基数最小的Rg-割(Rg-边割)的基数称为G的g-外连通度(g-外边连通度)， 记为κg(G)(λg(G))． 明显地， 如果G不是完全图， 则κ0(G)=κ(G)且λ0(G)=λ(G)． 因此，g-外连通度(g-外边连通度)可以认为是经典连通度(边连通度)的一种推广形式， 并且能更加精确地衡量大型并行处理系统的可靠性和容错性． 网络(图)的g-外连……