论文部分内容阅读
在该文中,我们设计了三个有效算法,并且对于算法的正确性以及时间复杂度给出了严格的证明,从而充分保证了算法的准确高效.在第一章中,我们首先给出对于该文中所使用的基本术语和概念的说明,然后针对我们描述的算法所涉及的分支领域,我们用两节的内容分别阐述了对集理论和连通度理论中相关研究的历史与最新进展.在第二章中,我们依据耳朵分解原理,可以得到如下结果,如果G是一个具有二分类(X,Y)的偶图且M是G的一个完美对集,G是1-可扩图当且仅当G有如下耳朵分解G=e+P<,1>+P<,2>+…+P<,r>,使得e∈M并且P<,i>是一条起始及终止于非对集边的M-交错路.文中给出了一个高效算法判定一个偶图是否为1-可扩图,并找出该图的耳朵分解.算法的时间复杂度为0(|E|<2>).判定一个图的圈边连通度问题是否为P问题是一个长期没有解决的问题,即使对于正则图到目前为止也是如此.在第三章中,我们依据宽度优先搜索策略,可以得到如下结果,对于每个e∈E(G),至多有O(k<4>|V|<2>)个包含e且长度不大于4(1og<,k-1>v+2)的圈.文中给出了第一个判定k-正则图(k≥3)中圈边连通度的有效算法.算法的时间复杂度为O(k<11>|V|<8>),尤其在立方图中其时间复杂度为0(|V|<8>).在第四章中,我们首先刻划了具有无穷圈边连通度的图,可以得到如下结果,如果G是一个连通图,且δ(G)≥3,g(G)≥5,那么cλ(G)≠∞当且仅当v(G)≥2g(G);如果G是一个连通图,且δ(G)≥3,g(G)=4,令C=wxyzw是圈,那么v(G)≥2g(G)当且仅当cλ(G)≠∞除非G-V(C)是一个星K<,1,r>(r≥3).文中给出了判定一个一般图中是否具有有限圈边连通度的高效算法,从而向设计判定一般图的圈边连通度的有效算法迈进了一步.算法的时间复杂度为0(|V|E|).在第五章中,我们对文中设计的三个有效算法进行了概要性总结,同时指出了算法中所存在的不足之处,希冀对今后的研究有所帮助.