论文部分内容阅读
随着信息网络的飞速发展,网络连通性与容错性越来越受到人们重视.本论文从连通度和非分离子图两个方面来研究图的连通性及其容错性.设G为图,如果G的点集S满足G-S不连通,则称S为G的一个点割.最小点割包含的点数称为G的连通度,用κ(G)表示.如果G的子图H满足G-V(H)仍连通,则称H为G的非分离子图.这两个概念分别从不同角度描述了网络的可靠性.第一章,首先介绍了(边)连通度在最优网络设计中的重要性及相关概念和主要研究进展;然后介绍非分离子图相关的著名的Lovasz可去路猜想及其相关进展和结果.第二章,研究了最优－κ性和超－κ性的点容错度.如果图G满足κ(G)=δ(G),则称G为最优－κ.如果G的每个最小点割都是某个点的邻点集,则称G为超－κ.如果对最优－κ图(或超－κ图) G的任意阶数不超过m的点集S都有G-S仍为最优－κ(或超－κ),则称G为m－最优－κ(或m－超－κ).使得G是m－最优－κ(或m－超－κ)的最大的整数m称为G的关于最优－κ(或超－κ)的点容错度,记作Oκ(G)(或Sκ(G)).本论文研究了Oκ(G)和Sκ(G)的上下界,以及它们之间的关系.另外还证明了对下界与上界之间的任何一个值,都存在一个图G使得Oκ(G)(或Sκ(G))等于这个值.最后,对任意正整数a,b,给出了存在图G使得Oκ(G)=a且Sκ(G)=b的一个充分必要条件.第三章,研究了非分离子图.关于非分离子图,Lovasz有一个很著名的可去路猜想,即对任意正整数κ,存在一个最小的整数f(κ)使得对任意f(κ)－连通图G以及G的任何两个点s,l都存在一条连接s和l的路P使得G-V(P)仍然为κ－连通.本文考虑Lovasz可去路猜想的三种推广或变形：第一种：对任意正整数κ,l,存在一个最小的整数f(κ,l)使得任意f(κ,l)－连通图G以及G的κ阶点子集X与不和X中点关联的一条边e,存在一个圈C使得e∈E(C),V(C)∩x=(?)且G-V(C)为l－连通.本论文第三章利用linkage理论证明了f(κ,1)≤10κ+1,f(κ,2)≤10κ+11.第二种：对任意正整数κ,l,存在最小的整数g(κ,l)使得任意g(κ,l)－连通图G以及任意G的任意κ阶点子集X都存在一个圈C使得V(C）∩X=(?)且G-V(C)为l－连通.本论文通过找收缩边的方法证明了g(κ,l)≤2κ+l+2,并当l=1时有g(κ,1)=κ+3.事实上还刻画了(κ+2)－连通图中不存在这样的圈的反例图.第三种：对任意正整数κ,l存在一个最小的整数h(k,l)使得任意h(k,l)-连通图G以及G中任何κ阶点子集X都存在一个连接X的树T使得G-V(T)为l－连通,其中连接X的树是指叶子点包含在X中一颗树.本论文第三章证明了h(κ,1)=κ+1,h(κ,2)≤2κ+1.