随着信息网络的飞速发展，许多关于网络的理论开始越来越受到人们的重视，其中之一就是网络的可靠性，即网络在它的某些部件发生故障的条件下仍能工作的能力。网络拓扑结构通常被模型化为图或有向图。一般来说，一个图的连通度越大，它所代表的网络就越稳定，因此图的连通度是研究网络的稳定性的重要参数。
最早的图的连通度和，定义是这样的：设图，连通度，同样可定义边连通度。但是它们至少有两个缺陷。首先，一个点的若干邻点同时出错的概率是很小的。例如，n阶图G至少有t个点达到最小度k。如果G中有k个出错的点，则这k个点恰好是某个点的邻点的概率是t/nk,当n很大时这个值会很小。连通度和边连通度是人们研究网络可靠性的工具，为了使网络可靠性的研究更具有实际意义，适应现实网络的复杂性，提出了更加复杂的连通度的概念并得到了相应的一些好的结论。
圈边连通度是所有圈边割的最小基数，圈边割满足G-F至少有两个分支含有圈。图G是否是圈可分图，在相关的论文中可以看到相应的结论。对于任意圈可分图G，有,。显然，在网络设计中，构造高连通性网络也是提高网络可靠性的方法之一，变换图是图论中构图法中非常巧妙而且实用的一种方法
设图G=（V(G),E(G)）,|V(G)|和|E(G)|分别表示图G的点数（阶数）和边数，dG(v)表示点v的度，NG(v)表示点v的邻点集。（G）表示图G的最小度，（G）表示图G的最大度，（G）表示图G的边连通度。对任意点集X,YV(G)，满足XY=,记[X,Y]={e:e=uvE(G),uX,vY}.Pn,Cn分别表示阶为n的路和圈，K1,n称为星图。
对任意viV(G),dG+-+(vi)=2d(vi);对任意eij=vivjE(G),dG+-+(eij)=|E(G|+3-(dG(vi)+dG(vJ)).
引理1 变换图G+-+连通的充分必要条件是G不含孤立点。文献[2]中可查找此结论。
定理1 变换图G+-+是连通圈可分图的充分必要条件是G不含孤立点且不是星图和三角形。此定理由作者自己证明得出，下面是证明过程。
证明 情况1 图G中存在两条独立边vivj和vsvt，则G+-+中存在两个点不交的圈vivjeij和vsvtest。
情况2 图G中不存在两条独立边，由引理1知G+-+连通时，GK1,n或K3。经检验，（K1,n）+-+和（K3）+-+都不含两个点不交的圈。
定理得证。
定理2 设G+-+是连通圈可分图，则此定理由作者自己证明得出，下面是证明过程。
证明 对任意圈可分图G，有所以我们可以通过找最短圈C，求得，得到上界。
取G中的一条边e=vivj，使得中存在最短圈C=vivjeij，且有
定理得证。
参考文献
[1]Wang B,Zhang Z.On cyclic edge connectivity of transitive graphs[J].Discrete Math.2009,309:4555-4563.
[2]Wu Baoyin,Meng Jixiang.Basic properties of transformation graphs[J].数学研究，2001,34(2):109-116.
论文作者:朱文慧
论文发表刊物:《教育学文摘》2019年第10期
论文发表时间:2019/11/21
标签：网络论文; 定理论文; 可靠性论文; 不含论文; 图论论文; 星图论文; 最小论文; 《教育学文摘》2019年第10期论文;