论文部分内容阅读
设G是连通图,V(G)表示G的顶点集.S(∈)V(G),当G不是完全图时,若C-S不连通,则称S是G的点断集;当G=Kn时,Kn的任何(n-1)个点组成的集合,亦称为G的点断集.G的所有点断集组成的集合记为C(G).连通图G的孤立断裂度B(G)定义为B(G)=max{i(G-S)-|S|:S∈C(G)},其中i(G-S)表示G-S的孤立点数.孤立断裂度作为断裂度的改进,是网络可靠性的一个重要度量.孤立断裂度可以刻画具有相同连通度和相同断裂度的图在连通程度上的差异.本文研究了图的孤立断裂度. 在第一章我们给出本文用到的基本的概念和符号.第一节给出本文涉及到的图论的基本概念.第二节中给出了与韧度、断裂度、孤立韧度相关的定义及定理. 本文第二章在第一节中证明了对于n(≥2)阶连通图G,2-n≤ B(G)≤n-2,且对于满足n≥2,2-n≤L≤(n-2)且L≠±(n-3)的整数n和L,都存在一个n阶连通图G,使得B(G)=L.并研究了孤立断裂度与独立数、最小度、最长圈等参数的关系.在第二节中研究了孤立断裂度取±(n-5)时图具有的性质. 在本文的第三章中,给出了n阶连通偶图G的孤立断裂度与图G的独立数α(G)的关系式: B(G)=2α(G)-n;证明了连通偶图G有完美对集当且仅当B(G)=0;研究偶图的孤立断裂度与其子图孤立断裂度之间的关系;并确定了路与偶圈的孤立断裂度. 在第四章中得到了联图的孤立断裂度的计算公式:设G1和G2分别是n1和n2阶连通图,则G1与G2的联图H孤立断裂度B(H)=max{B(G1)-n2,B(G2)-n1}. 第五章主要研究了树的孤立断裂度.在第一节中我们给出了树的孤立断裂度的多项式时间算法.第二节研究了最大度为△的n阶树的最大、最小孤立断裂度,得到了下面的结论:(我们用T[n,△]表示最大度为△的n阶树的集合,r(n-1/△)表示n-1除以△后所得的余数.) 具有n(≥2)个顶点,且最大度为△的树可能具有的最大孤立断裂度为: maxT∈T[n,△] B(T)={n-2(n-1/△) r(n-1/△)=0n-2(「)n-1/△」-2 r(n-1/△)≠0 具有n(≥2)个顶点,且最大度为△的树可能具有的最小孤立断裂度为:min T∈T[n,△]△]B(T)={2△-n n≤2△-2{0 n为偶数1 n为奇数 n≥2△-1 在第三节中研究了树与余树孤立断裂度之间的关系.