文档介绍：西北工业大学
硕士学位论文
关于网络稳定性参数的研究
姓名:魏宗田
申请学位级别:硕士
专业:应用数学
指导教师:李学良
20030320
摘要引入了一些新的连通性参数,主要有联结数,离散数,完整度和边完整度,粘连度和边粘连度,坚韧度等。这些参数同时反映了一个网络可能遭到的最大程度的破坏和被最大程度破坏后剩余部分的工作状态,因此更好地刻画了图的连通性。入图的邻域连通度概念,甕域完整度和边邻域完整度概念,于是又出现了~系列研究成果,使网络稳定性研究迈进了第一章绪论部分介绍图的连通性和稳定性方面的研究现状,指出本文研究工作的背景第二章集中讨论复合图的邻域完整度,给出了一般情形下复合图邻域完整度的上下界,路状,圈状等特殊复合图的邻域完整度,还纠正了第三章引入图的邻域离散数概念,给出几类基本图的邻域离散数值,并就树的邻域离第四章主要定义图的边邻域离散数,给出一些基本图的边邻域离散数值,图的边邻域点邻域完整度在网络的设计与建造过程中,稳定性是一个必须考虑的重要因索。一个网络可以模拟成一个连通图,其中图的顶点表示组件,边表示连接组件的信道。因而图的连通性与稳定性一‘真是图论的一个热点。围绕这个问题,除了早期的点连通度外,人们后来又相继然而考虑一些特殊网络,比如间谍网的上述性质时,情况完全不同了。因为倘若某个间谍被捕了,与其相邻的间谍必然会全部失去作用。以此为背景,。本文在前人工作的基础上,着重研究了邻域场合下图的稳定性,得到一些相关结果,在一定程度上丰富了已有图的稳定性理论。本文的主要内容是:及意义。的几个错误。散数进行较为深入的研究。离散数的界,树的边邻域离散数的一个多项式算法。关键词点连通度点邻域连通度邻域离散数边邻域离散数树边邻域离散数算法复合图
瑃—.——簐籧·,甅,甒·瓸..—.,甌瑂琫—.,,,甀珿——..,甋,,.·,產瓵,瑃—,瓼,....猻—瓵琲畉.
第一章绪论一个网络可以用一个连通图来表示,其中图的顶点表示网络中的组件。边的网络就越稳定,因此研究网络的稳定性实质上就是研究图的连通住。通性的参数。最早的图的连通性参数是连通度和边连通度,等人在这方面做了大量卓有成效的工作。但随着研究的不断深入,人们发现仅用这两个参完整度,粘连度,边粘连度,坚韧度及边坚韧度等。这些参数同时反映了一个提高其稳定性嗉纯够傩,使其在受到外在攻击时不易被破坏,一旦真的遭表示连接两个组件之间的通信信道。很明显,一个图的连通性越好,它所代表连通性是图所固有的基本属性之~,目前有两种方法研究图的连通性,一种方法基于确定性理论,另一种则是基于概率论。本文的研究工作也是基于第一种方法之上的,并约定,网络与图是两个等同的概念。确定性理论的基本思想是将某些被认为合理的图的不变量作为刻画图的连数刻画图的连通性有明显的不足。为解决这个问题,又有人相继引入了一些图的其它连通性参数,主要是:联结数,离散数渤葡喽远狭讯,完整度,边网络可能遭到的最大程度的破坏和被最大程度破坏后剩余部分的工作状态,因此更好地刻画了图的连通性。年,等人把间谍网模拟为图,即用图的顶点表示间谍,图的边表示两个直接联络的间谍之间的联络方式。此种网络的特殊性在于,若一个间谍叛变或被破坏,与其直接联络的所有间谍都将失去作用。显然用已有的连通性参数无法衡量其稳定性。于是图的邻域连通度,边邻域连通度,邻域完整度,边邻域完整度便应运丽生。这些参数与通常意义下图的连通性参数截然不同,它们不刻画图的连通性,却能够深刻反映邻域意义下图的稳定性。为了叙述方便,我们把它们称作图的稳定性参数,引言稳定性是衡量一个网络好坏的重要指标,因此网络设计的基本思想之一是到破坏,也能够较易修复。西北工业大学硕士学位论文
,当占,≥篯时,兄,糲琧瑀,≤痌,旯;≤萞:洲。—≥,其中国—表示猄兄。磇獂F渲小獄硎綠—牧ǚ种鐸矿琁其中勘硎径詘取整。鑨,峭糋中不相邻的两个顶点,则乞,,。其中%,表上述两类参数均得到了广泛的研究,相对而言,对连通性参数的研究更深关系,⒉问蹈ǎ乖熳畲最小纾此郊滴侍猓、参数的算法。本章以下分两个部分介绍这一领域的研究现状。本文未加定义而直接用到的图的基本概念、术语及符号均来自】。图的连通性参数及研究现状⒘ǘ扔氡吡ǘ峭本文所涉及的图都是有限、无向、连通、简单图,以后不再说明矿珽直鸨硎綠的顶点集与边集,牧ǘ葂ㄒ逦#:支数。若涣ǎ騲籊阶完全图时,茁月一与此类似,图谋吡ǘ華ㄒ逦#≥保艷是涣ǖ模琟輗时,称莚一边连通的。和缙谠谡夥矫娴难芯恐械玫搅诵矶嘤判愕慕峁示心诓康悴唤坏瑈返淖畲筇跏瑃,表示凶钚瑈掷爰入。一般来说,已有研究工作着重解决以下几个方面的问题:⒒就嫉牟问值,⒉问胪嫉牧ㄐ稳定性、参数的取值范围及与图的其它参数之若涣ǎ蚨ㄒ尻。蹵为淖钚《サ愣西北工业