二部分裂图的边脆弱性参数

来源 :新疆大学 | 被引量 : 1次 | 上传用户:kwx313
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
一个计算机网络或者通讯网络,可以用一个连通图来表示,其中图的顶点表示通讯站,边表示两个通讯站之间可以直接通讯的通讯线路。对于一个网络,它的稳定性常用它所对应的图的脆弱性参来数描述。在脆弱性参数方面的早期研究,主要是围绕连通度和边连通度展开的。这两个参数被广泛的使用来描述图的脆弱性,但是这两个参数不能用来说明网络被破坏以后的状态。由于这两个参数在描述图的脆弱性方面具有局限性,近来人们陆续引入了一些其它的脆弱性参数,主要包括了坚韧度和边坚韧度,离散数,完整度和边完整度,粘连度和边粘连度以及连通度的各种变形。这些参数不仅考虑了网络被破坏的难易程度,还考虑了网络遭受破坏的状态,已经证明对一般图计算这些参数是NP-困难间题,因此研究特殊图类的这些参数是有意义的。本文中,我们主要讨论了二部分裂图的边脆弱性参数。一个图称为二部分裂图,如果它的点集可以划分为三个独立集I、Y和Z ,使得I导出的子图是空图、Y∪Z导出的子图是完全二部图。本文第一章简单讨论了研究图脆弱性参数的意义,简略的介绍了图的边脆弱性参数研究现状和本文的主要结果。我们记G = (Y∪Z,I,E)为连通非完全二部分裂图。本文第二章,研究二部分裂图的边脆弱性参数:其中第一节中,我们证明了二部分裂图的边连通度等于它的最小度;第二节中,证明当|Z|≥|Y |≥(2/3)δ时二部分裂图的边坚韧度等于,同时用例子来说明条件|Z|≥|Y |≥(3/2)δ是不能去掉的;第三节中,我们证明若|Y∪Z| < 2δ,则二部分裂图的边完整度等于它的阶数,并且给出确定的图来说明我们的这结果是不可改进的。
其他文献
众所周知,利用伪随机数的传统蒙特卡罗(MC)方法收敛速度比较慢,收敛速度为O(N-1/2)。为了克服这个缺点,我们利用超均匀随机数来代替伪随机数以取得较好的效果。在MC方法中利用超均匀序列称为拟蒙特卡罗(QMC),我们可以给出QMC的理论上确界,但不能计算它的误差估计。为了弥补MC收敛速度慢和QMC不能计算误差的缺点,我们可以通过对拟随机数进行随机化(加扰),这种方法我们称之为随机化拟蒙特卡罗(R
众所周知,研究各种离散时间的种群动力学模型不仅具有广泛的生物理论意义,还具有重要的实际应用价值.近年来,越来越多的学者对离散时间种群动力学模型的研究产生了兴趣,得到了非常多的研究成果.本文,我们将继续这类研究,讨论一般的非自治离散时间多种群Kolmogorov模型的持久性以及两类离散周期模型的周期解的存在性.主要内容可以概述如下:在第一节中,我们首先介绍了离散时间种群模型的生物背景.然后介绍了各种
本文共分二章.第一章分二节.第一节回顾可靠性理论的历史.第二节中首先介绍补充变量方法,然后提出本文要研究的问题.第二章共分二节.第一节首先介绍由一个可靠机器,一个不可靠机器与一个缓冲库构成的系统的数学模型,接着引入状态空间,算子及其定义域,然后将该模型转化成Banach空间中的抽象Cauchy问题,最后介绍其他学者有关于此模型的研究成果.第二节首先研究此模型主算子的特征值,证明±(?)-γη1-μ
随着信息网络的飞速发展,许多与之相关的理论性问题越来越引起人们的重视,其中之一就是网络稳定性.一个网络的稳定性是在已知某些网络节点损坏的情况下衡量该网络是否能够正常工作的能力.这是网络设计和构造的基本思想之一.一个网络可以模型为一个图,网络的稳定性可以由该图的各种连通性指标来衡量.在本文中我们研究了其中一个参数,就是限制性边连通度.一个连通图G = (V,E)的一个边子集S叫做一个k限制性边割,如
在本文中我们考虑的都是有限的无向简单图.一个图G的全图T(G)的顶点集是V (G)∪E(G),其中任意的两个点相邻当且仅当它们在G中相邻或关联.吴和孟把全图进行推广提出了变换图的概念.在本文中,我们将研究一个图G的一种变换图G+??.变换图G+??的顶点集是V (G)∪E(G),两个点u和v在G+??中相邻如果满足下面的任何一个条件:(i) u,v∈V (G)并且它们在G中是相邻的, (ii) u
本文建立了一类带有漏隙接种的非终生免疫的年龄结构的SEIR传染病模型,讨论了这个模型的解的适定性.首先把问题(P)化为等价的积分方程组(H),通过定义算子将问题(H)转化成一个算子不动点的唯一性问题;然后利用算子不动点证明积分问题(H)局部解的存在唯一性,进而得到积分问题(H)的解的整体存在唯一性、解关于初值的连续依赖性及C1光滑性,从而得到问题(P)的解的适定性.在对模型稍作简化的情况下讨论了无
本文只考虑简单图,有向图可以有环,但没重弧(弧具有相同的头和尾)。网络往往模型化为无向图或有向图。衡量网络稳定性的经典参数为图的连通度和边连通度,为了进一步研究,人们提出了各种各样的高阶连通度概念,如超点连通性、超边连通性、超混合连通性、hyper-连通性、限制性边连通度等等。本论文主要研究图图的高阶连通性。本文共分三章。第一章引言主要介绍稳定性参数的一些背景和一些基本概念。第二章主要研究了两种特
一个网络可以模型为一个图,网络的稳定性可以由该图的各种连通性指标来衡量.在本文中我们研究了其中一个参数,就是3-限制性点边连通度.一个连通图G = (V,E)的一个边集S叫做一个k-限制性边割,如果G ? S是不连通的,并且G?S的每一个分支至少含有k个点.一个图的k-限制性边连通度,记为λk(G),就是最小的k-限制性边割所含边的数目.从这个参数的最近一些研究结果来看,λk越大,网络就越稳定.定
匹配理论是图论的核心内容之一.由于得到应用领域的支持,并与其他理论课题发生密切联系,受到众多学者的关注,产生出许多含义丰富而深刻的理论结果.例如,刻画偶图具有完美匹配的Hall定理、刻画一般图具有完美匹配的Tutte定理、不具有完美匹配图的Gallai-Edmonds结构定理、求偶图最大权匹配的匈牙利方法、求非偶图最大权匹配的开花算法等,都是影响深远的传世之作.同时关于匹配的一系列研究专题不断涌现