论文部分内容阅读
一个网络可以用一个连通图来表示，其中图的顶点表示网络中的组件，边表示两个组件之间的通信信道。图的连通度可以衡量网络的稳定性。一般来说，一个图的连通性越好，它所代表的网络越稳定。然而，连通度衡量网络的可靠性是有缺陷的。于是，学者们先后引入各种连通度，包括圈边连通度。与连通度相比，圈边连通度不受图的最小度限制，从而可以更好地衡量网络的连通性。
长期以来，关于一般图的圈边连通度判定是否为P问题还没有得到解决。LOU和WANG[1]给出了第一个关于K正则图的圈边连通度的判定算法，其时间复杂度是O(k11｜V｜8)，此复杂度在实际应用中稍大。因此，进一步提高算法的执行效率具有重要意义，也是本文要研究的问题。本文设计的改进算法将在前人工作的基础上，通过对正则图的结构作更深入细致的分析，来达到改进算法的目的，新算法的时间复杂度是O(k9｜V｜6)。在研究的过程中，我们证明了以下一个引理：
引理4.2.1图G是连通的k—正则图。如果cλ(G)<(k—2)g，则删除一个最小圈边割S，G—S有两个连通分支，每一个连通分支各包含一个圈C。如果C是奇圈，则｜V(C)｜≤2｜logk-1v(G)｜+5；如果C是偶圈，则｜V(C)｜≤2｜logk-1v(G)｜+6。
本文第一部分介绍图的连通度的研究现状和进展，指出本文的选题背景和研究意义。第二部分综述本文所需要的预备知识，包括一些关于图的基本概念和专业术语，有关连通度的一些基本结论和一些引理。第三部分基于文献[1]关于3-正则图的圈边连通度判定算法设计我们的改进算法，并且在理论上证明新算法的正确性，以及新算法的时间复杂度分析。第四部分把3-正则图的改进算法推广到k—正则图的情形，并且实现该算法。