关于正则图的圈边连通度判定算法

摘要

一个网络可以用一个连通图来表示，其中图的顶点表示网络中的组件，边表示两个组件之间的通信信道。图的连通度可以衡量网络的稳定性。一般来说，一个图的连通性越好，它所代表的网络越稳定。然而，连通度衡量网络的可靠性是有缺陷的。于是，学者们先后引入各种连通度，包括圈边连通度。与连通度相比，圈边连通度不受图的最小度限制，从而可以更好地衡量网络的连通性。 长期以来，关于一般图的圈边连通度判定是否为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—正则图的情形，并且实现该算法。

目录

文摘

英文文摘

声明

第1章引言

1.1选题背景

1.2研究现状

1.3研究意义

1.4论文结构安排

第2章预备知识

2.1基本概念和术语

2.2有关连通度的一些结论

2.3一些有用的引理

2.4本章小结

第3章3-正则图的圈边连通度判定算法

3.1已有的算法

3.2改进的算法

3.3算法的正确性证明

3.4算法的时间复杂度分析

3.5本章小结

第4章K-正则图的圈边连通度判定算法

4.1算法的设计

4.2算法的正确性证明

4.3算法的时间复杂度分析

4.4算法的实现

4.5本章小结

第5章结束语

5.1总结

5.2展望

参考文献

附录

硕士期间论文及科研情况

致谢