图的孤立断裂度

来源 :山西大学 | 被引量 : 0次 | 上传用户:blueblood008
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
设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  在第三节中研究了树与余树孤立断裂度之间的关系.
其他文献
学位
学位
本文中研究具有成批到达且服务率随时间变化的MX/M/1排队系统,即任意t时刻的服务率取值为μφ(X(t)),φ(x)是有界函数,μ>0,而{X(t),t∈[0,T]}是Ornstein-Uhlenbeck扩散过程.若记L(t
学位
学位
学位
学位
学位
本文主要考虑由二维随机微分方程驱动的最优机制转换问题.其方法是通过泰勒展开将由该随机微分方程的无穷小生成元得到的二元偏微分方程转化为含参量的一元常微分方程组,并利