平面图圈边连通度的有效算法

圈边连通度cλ（G）是指图G中所有圈边割中的最小势，即最少割掉多少条边使得图G的两个连通分支中都各有至少一个圈。求一般图的圈边连通度至今仍未找到有效算法。本文提出了一个多项式时间的算法求解平面图的圈边连通度。该算法的时间复杂度是O（｜V｜^2）。

具有两个同阶轨道的双轨道图的圈边连通度(英文)

一个边割被称为圈边割,如果该边割能分离图的两个不同圈.如果一个图有圈边割,称该图为圈边可分离的.一个圈边可分离图G的最小圈边割的阶数被称为圈边连通度,记作cλ(G).定义:ζ(G)=min{w(X)|X导出G的最短圈},其中w(X)为端点分别在X和V(G)-X中的边的数目.如果一个圈边可分离图G使得cλ(G)=ζ(G)成立,称该图是圈边最优的.Tian和Meng在文章[11]以及Yang et al在文章[15]中研究了两种不同的双轨道图的圈边最优性.本文我们将研究具有两个同阶轨道的双轨道图的圈边连通度.

图的圈边连通度和圈弧连通度

令G是一个简单图.G的圈边连通度cλ(G)定义为E(G)的一个子集F的最小基数,其中G−F不连通且至少有两个分支包含圈.令D是一个有向图.D的圈弧连通度λ_(c)(D)定义为A(D)的一个子集S的最小基数,其中D−S不强连通且至少有两个强连通分支包含有向圈.在文章中,我们研究了无向二元Kautz图、无向de Bruijn图和无向二元广义de Bruijn图的圈边连通度.而且,我们获得了Kautz有向图、de Bruijn有向图和广义de Bruijn图的圈弧连通度.

全图的圈连通度(英文)

对于一个图G,它的一个圈边割是一个边集,将该边集去掉之后能够分离出两个圈.如果G有一个圈边割则称G是圈可分离图.设G是一个圈可分离图,其圈边连通度cλ(G)是G的最小圈边割的基数.圈点割和圈点连通度cκ(G)可以类似定义.本文给出了全图T(G)的圈边连通度和圈点连通度的上界和下界.

同阶双轨道连通图的超圈边连通性

对于图G,如果G-F是不连通的且至少有两个分支含有圈,则称F为图G的圈边割.如果图G有圈边割,则称其为圈可分的.最小圈边割的基数叫作圈边连通度.如果去除任何一个最小圈边割,总存在一分支为最小圈,则图G为超圈边连通的.设G=(G_1,G_2,(V_1,V_2))为双轨道图,最小度δ(G)≥4,围长g(G)≥6且|V_1|=|V_2|.假设G_i是k_i-正则的,k_1≤k_2且G_1包含一个长度为g的圈,则G是超圈边连通的.

2—可扩平面图

证明了所有具有偶顶点数的5—连通平面图是2-可扩的,并给出了非2-可扩的4-连通平面图。

一种正则网络性能的评价方法

正则图是一种特殊构造的图,被广泛的使用于网络的拓扑结构的设计中,这种网络被称为正则网络。文章提出了一种正则网络性能评价方法,主要针对正则网络的可控制性和健壮性两个方面进行定性定量的评价,并根据上述方法设计了一个计算正则网络可控制性和健壮性的算法。最后举例说明了算法在正则网络评价中的应用。