（应用数学专业论文）图的邻域参数研究.pdf

中文摘要 摘要 在交通、计算机或通讯等网络的设计与维护过程中，网络的稳定性( 抗毁性) 是一项重要的性能指标。网络设计的基本思想之一就是使其在受到外部攻击时不 易被破坏，如果被破坏也能够容易得到修复。我们通常用无向连通图表示网络， 其中点代表网络中的对象，边代表它们之间具有的特定关系，这样就可以运用图 论知识研究网络系统。人们提出了许多参数衡量网络的稳定性，早期的研究主要 是围绕图的连通度和边连通度展开的，但这两个参数存在着不足，因为它们没有 涉及到去掉点或边后网络图遗留下来的分支。为了克服这个不足，人们相继引入 了许多新的参数，如坚韧度，离散数、完整度和韧性度等。这些参数不仅考虑了 网络破坏的难易程度，而且还考虑了网络遭受的破坏程度，相对图的( 边) 连通 度而言，是一些较为合理地刻画网络稳定性的参数。 1 9 9 0 年c 础等人研究了间谍网的网络模型，即用图的顶点代表间谍，图的 边代表两个间谍之间的直接联络。这种网络模型的特点是，若一个间谍背叛或被 俘获，那么与该间谍直接联络的所有间谍都将不再被相信，从而失去作用。显然 已有的连通性参数无法衡量此类网络的稳定性，因此该图的邻域连通度、边邻域 连通度、邻域完整度、边邻域完整度、邻域离散数和边邻域离散数便应运而生， 但这些参数衡量某些网络的稳定性时还存在着缺陷。 本文主要内容为： ( 1 ) 介绍了以上邻域连通性参数的研究背景和意义，并对各参数做了比较归纳 和系统分析。( 2 ) 介绍、总结和比较以上邻域连通性参数的基础上提出了一个新的 邻域参数邻域破裂度，着重研究了邻域情况下图的稳定性。给出了几类基本图 的邻域破裂度，也给出了联图的邻域破裂度，讨论了邻域破裂度的上界和下界，还 讨论了邻域破裂度与其它参数的关系。( 3 ) 本文同时定义了边邻域破裂度，给出一 些基本图的边邻域破裂度，并得出一些相关的结论。( 4 ) 本文还介绍了一个相关的 参数图中度平方和的界，给出了相对较大新的下界，同时给出了利用图中度平 方和的界精确确定一个图及其补图中三角形个数的简单应用及相关的一些结论。 关键词： 邻域整度；邻域离散数；邻域破裂度；图中度平方和的界 英文摘要 ar e s e a r c ho nn e i g h b o rp a r a m e t e r so fg r a p h s a b s t r a c t i nt h ep r o c e s so f d e s i g n i n ga n dm a i n t a i n i n gt r a n s p o r t a t i o n , c o m p u t e ro rc o m m u n i c a t i o n n e t w o r k s t h es t a b i l i t y ( v u l n e r a b i l i t y ) o ft h e mi sa ni m p o r t a n tp e r f o r m a n c ec r i t e r i o n t h e r e f o r e ，o n eo ft h eb a s i ci d e a st od e s i g nn e t w o r k si st h a tt h e yd on o te a s i l yg e t d i s r u p t e du n d e re x t e r n a la t t a c ka n dt h e ya r ee a s i l yr e c o n s t r u c t e di ft h e yd or e a l l yg e t d i s r u p t e d an e t w o r ks y s t e mc a nb em o d e l e db yac o n n e c t e dg r a p h , i nw h i c hv e r t i c e s r e p r e s e n tm o d u l e sa n de d g e sr e p r e s e n ts o m es p e c i a lc o n n e c t i o nb e t w e e nt h em o d u l e s ， t h e nw ec a ns o l v et h ep r o b l e mt h r o u g ht h eg r a p ht h e o r y u n d e rt h em a t h e m a t i c a lm o d e l o fn e t w o k s ，p e o p l eb e g a nt op u tf o r w a r ds o m ep a r a m e t e r st om e a s n r et h es t a b i l i t yo f n e t w o r k s a tt h eb e g i n n i n g ，v e r t e x c o n n e c t i v i t ya n de d g e - c o n n e c t i v i t ya r et w op a r a m e t e r s o f t e nu s e df o ri t b u tt h et w op a r a m e t e r sh a v es o m ed e f i c i e n c i e s ，b e c a u s et h e yd on o t t h i n ko f t h es u r v i v a l s u b g r a p ha f t e rr e m o v i n gt h ev e r t i c e so re d g e s ho r d e rt oo v e r c o m e t h ed e f i c i e n c i e s ，p e o p l eh a v ei n t r o d u c e ds o m en e wp a r a m e t e r s ，s u c ha st o u g h n e s s ， s c a t t e r i n gn u m b e r , i n t c g a t y ，t e n a c i t yi nt h ep a s td e c a d e a l lo f t h e s ep a r a m e t e r sa r em o r e r e a s o n a b l et h a nv e r t e x - c o n n e c t i v i t ya n de d g e c o n n e c t i v i t y ，b e c a u s et h e yc a l lm e a s u r en o t o n l yt h ea m o u n to fw o r kd o n et od a m a g et h en e t w o r kb u ta l s oh o wb a d l yt h en e t w o r ki s d a m a g e d i n1 9 9 0 ，c o z z e u si n t r o d u c e dt h ei d e ao fm o d e l i n gas p yn e t w o r kb yag r a p hw h o s e v e r t i c e sr e p r e s e n tt h ea g e n t sa n dw h o s ee d g e sr e p r e s e n tl i n e so fc o m m u n i c a t i o n c l e a r l y ， i f as p y i s d i s c o v e r e d o ra r r e s t e d ，t h ee s p i o n a g e a g e n c y c a n n o l o n g e r t r u s t a n y o f t b es p i e s w i 山w h o mh eo rs h ew a si nd i r c c tc o m m u n i c a t i o n a n ds ot h eb e t r a y e da g e n t sb e c o m e e f f e c t i v e l yu s e l e s st ot h en e t w o r ka saw h o l e i ti so b v i o u st h a tw ec a n n o tm e a s u r et h e s t a b i l i t yo fs p yn e t w o r ku s i n gt h ea b o v ep a r a m e t e r s w i t ht h eb a c k g r o u n ds t a t e da b o v e ， p e o p l ei n t r o d u c e ds o m en e wp a r a m e t e r s ，s u c ha sv e r t e x - n e i g h b o r - c o n n e c t i v i t y ，e d g e - n e i 。 g h b o r - c o n n e e t i v i t y ，v e r t e x - n e i g h b o r - i n t e g r i t y , e d g e n e i g h b o r - i n t e g r i t y ，v e r t e x - n e i g h b o r - s c a t t e r i n gn u m b e r , e d g e - n e i g h b o r - s c a t t e r i n gn u m b e r b u tt h e s en e i g h b o rp a r a m e t e r sh a v e s o m ed e f i c i e n c i e st om e a s u r et h es t a b i l i t yo f s o m en e t w o r k s t h em a i nc o n t e n t so f t h i st h e s i sa r es h o w e da sf o l l o w s ： ( 1 ) w ei n t r o d u c et h eb a c k g r o l l l l da n ds i g n i f i c a n c eo f t h en e i g h b o r - c o n n e c t i v i t yp a r a m 。 e t e r s ( v e r t e x - n e i g h b o r - c o n n e c t i v i t y ，e d g e - n e i g h b o r - c o n n e c t i v i t y ，v e r t e x - n e i g h b o r - i n t e g r i t y , 英文摘要 e d g e - n e i g h b o r - i n t e g r i t y , v e r t e x - n e i g h b o r - s c a t t e r i n gn u m b e r , e d g e - n e i g h b o r - s c a t t e r i n g n u m b e r ，v e r t e x - n e i g h b o r - r u p t u r ed e g r e e ) a n dp o i mo u tp r e s e n tr e s e a r c hs i t u a t i o no f c o n n e c t i v i t ya n ds t a b i l i t yo fn e t w o r k s m e a n w h i l ew es u m m a r i z ea n da n a l y s et h em a i n r e s u l t sa b o u tt h e s ep a r a m e t e r s ( 2 ) b ys u m m i n gu pa n dc o m p a r i n go ft h em a i nr e s u l t s a b o u tt h e s en e i g h b o r p a r a m e t e r s ，w ei n t r o d u c ean e wn e i g h b o rp a r a m e t e r , t h en e i g h b o r - r u p t u r ed e g r e e b a s e d o nt h e s ea c h i e v e m e n t s ，t h i sp a p e rm a i n l yc o n s i d e rt h es t a b i l i t yo fn e t w o r k sw i t h n e i g h b o rc o n d i t i o na n dn e i g h b o r - r u p t u r ed e g r e eo f s e v e r a ls p e c i f i cc l a s s e so f g r a p h sa r e d e t e r m i n e d f o r m u l a sf o rt h en e i g h h e r - r u p t u r ed e g r e eo f j o i ng r a p h sa n ds o m eb o u n d s o ft h en e i g h b o r - r u p t o r ed e g r e ea r eg i v e n w ea l s od i s c u s st h er e l a t i o n s h i pb e t w e e n n e i g h b o r - r u p t u r ed e g r e ea n ds o m eo t h e rp a r a m e t e r s ( 3 ) t h ec o n c e p to fe d g e - n e i g h b o r - r u p t u r ed e g r e ei si n t r o d u c e d ，a n dt h ev a l u e so f e d g e n e i g h b o r - r u p t u r ed e g r e eo fs o m es i m p l e g r a p h sa r eg i v e n m e a n w h i l e ，w eg e t s o m er e s u l t sa b o u ti t ( 4 ) w ea l s oi n t r o d u c ear e l a t i v ep a r a m e t e r - t h eb o u n do f t h es u mo f t h es q u a r e so f t h e d e g r e e si nag r a p ha n dg i v et w ob e t t e rl o w e rb o u n d sa n ds o m er e s e a r c hr e s u l t s w ea l s o a p p l yt h ec o n s e q u e n c e st ob o u n d i n gt h et o t a ln u m b e ro ft r i a n g l e si nag r a p ha n di t s c o m p l e m e n t k e yw o r d s ：n e i g h b o r - i n t e g r i t y ；n e i g h b o r - s c a t t e r i n gn u m b e r ；n e i g h b o r - r u p t u r e d e g r e e ；t h eb o u n do f t h es u mo f t h es q u a r e so f t h ed e g r e e si nag r a p h 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文：国的壑堡叁数研究：。除 论文中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均己 在文中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体己 经公开发表或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：为爵州1 7 年j 月竹日 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位 论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或 扫描等复制手段保存和汇编学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于；保密口 不保密时( 请在以上方框内打“”) 论文作者签名；马永恫1 导师签名：匆恙季 日期：2 净妒2 ( f 日 图的邻域参数研究 第1 章绪论 1 1 引言 现实世界中很多系统都可归结为网络系统，网络系统的一个基本问题就是稳 定性问题，即系统在发生某些破坏的情况下仍能正常工作的性能，它是衡量一个 网络系统好坏的重要指标。因此网络设计的基本思想之一是提高其稳定性( 亦即 抗毁性) ，使其在受到外在攻击时不易被破坏，一旦真的遭到破坏，也能较易修复。 从而稳定性的研究就具有重要的理论意义和实用价值。 量化一个图或网络的稳定性，始于对图的连通性的研究和m e n g e r 与w h i t n e y 的理论。由于图或网络的稳定性具有重大的理论和实际意义，许多专家纷纷致力 于这方面的研究，提出了很多衡量网络稳定性的参数，得到了许多有意义的结果。 而这些研究工作主要是围绕点连通度、边连通度和局部点( 边) 连通度进行的， 但随着图的连通性研究的不断深入，人们越来越觉得仅用点( 边) 连通度存在着 很大的局限性，因为它们仅仅反映了系统被破坏的难易程度，而没有反映出系统 遭受破坏的程度，即没有涉及到去掉点或边后网络图遗留下来的分支。为了克服 这个不足，人们提出了许多新的参数，如坚韧度、离散数、完整度和韧性度等。 这些参数不仅考虑了网络破坏的难易程度，而且还考虑了网络遭受的破坏程度， 相对图的( 边) 连通度而言，是一些较为合理地刻画网络稳定性的参数。 1 9 9 0 年，c o z z e n s l l 】等人把间谍网模拟为图。即用图的顶点表示间谍，图的边 表示两个直接联络的间谍之间的联络方式。这种网络的特殊性在于，若一个间谍 背叛或被捕获，与其直接联络的所有间谍都将不再被相信，从而失去作用。显然 用已有的连通性参数无法衡量这种模型的稳定性，于是图的邻域连通度、边邻域 连通度、邻域完整度、边邻域完整度、邻域离散数和边邻域离散数便应运而生。 这些参数与通常意义下图的连通性参数有着很大的不同，它们不刻画图的连通性， 却能深刻反映邻域意义下图的稳定性，因此网络稳定性邻域参数问题的研究就显 得尤为重要。目前，国内从事这一领域研究的人很少，国外也不多，而且理论结 果有待丰富和完善。本文在介绍、总结和比较以上邻域连通性参数的基础上，引 入了能够比较客观、相对简单地刻画邻域情况下图的稳定性的新参数邻域破 裂度，并对这个参数进行了初步的研究。本章以下几个部分分别介绍了论文所需 绪论 的一些相关知识，邻域连通性和边邻域连通性的研究现状及本论文的主要研究工 作。 1 2 基本概念和记法 本文用到的一些图论的基本概念和术语，如未加以说明，请参见b o n d y 和 m u r t y t 2 。 设g k 毋是一个图，其中乃e 也分别记为坎g ) 和e ( g ) ，它们分别表示图 g 的点与边的集合。若萨 “，v ) 是图g 的一条边，其中“，v v ( g ) ，则称和v 是 邻接的，边e 和点h , v 相关联，甜和v 称为边e 的端点。同一顶点关联的两条边也 称为相邻的。两端点重合的两条边称为环，两个结点方向相同的若干条边称为平 行边或重边。无环并且无平行边的图称为简单图。以g ) 中元素的个数和耳g ) 中元 素的个数分别称为图的阶和边数。点1 ，的顶点度数d ( v ) 定义为与点v 相邻的所有点 的个数。如果对于图g 中任意一对顶点 ，v ) ，在g 中存在“- v 路，则称该图是连 通的。下面列出本文所出现的基本概念及记法。 ( 1 ) 只有一个孤立结点的图称为平凡图。 ( 2 ) 仅有一些孤立结点的图称为零图或空图，一个拧阶空图记为易。 ( 3 ) 图g 的顶点最小度数a ( a ) = m i n d ( v ) ：v g ；图g 的顶点最大度数 ( g ) = m a x d ( v ) ：v g ) ( 4 ) 若图的顶点集可以分成两个非空子集z 和l 使得每条边都有一个端点 在x 中，另一个端点在y 中，称其为二部图，把这样的一种分类( 墨y ) 称为图的一个二分类。 ( 5 ) 完全二部图是具有二分类( 墨玢的简单二部图，其中姗q 每个顶点都与y 的每个顶点相邻；若n = m 而i r i 铆，则这样的图记为j 岛，。 ( 6 ) 星图是一种特殊的完全二部图，其中第一个独立集仅有一个顶点，第二 个独立集有胛 丝) 个顶点，记作局， ( 7 ) 任何不同两结点都有边相连的简单无向图称为完全图。一个含有胛个顶 点的完全图记作墨。 ( 8 ) 彗星图是指将长为t 的路尸f 的一个端点与星状图蜀，的中心结点合并而得 到的图，记作g ，。 2 图的邻域参数研究 ( 9 ) 用啊f g 十蜀表示肿1 阶轮图，即为蜀的唯一顶点邻接g 的每一个顶点 而成的图。 ( 1 0 ) 设g l 和g 2 是g 的子图。若g l 和g 2 没有公共顶点，则称它们是不相交的； 若g 1 和g 2 没有公共边，则称它们是边不重的。g l 和g 2 的并图g lug 2 是指 g 的一个子图，其顶点集为z ( g 1 ) uv ( g 9 ，其边集为耳g 1 ) u e ( g 2 ) 。类似 可以定义g 1 和g 2 的交图g l ng 2 。 ( 1 1 ) 不相交的两个图g l 和g 2 的联图g l + g 2 是指在g l ug 2 中，把g l 的每个顶点 和g 2 的每个顶点连接所得的图。 ( 1 2 ) 图g l 和g 2 的笛卡儿积为图g = g l g 2 ，其中图g 满足：坎g 户v ( g 1 ) x 坎g 2 ) ；g 中的两个顶点( 口，b ) 和( c ，d ) 是邻接的当且仅当萨c 且 6 ，田 e ( g 2 ) 或者b - - - d n a , c ) e ( g 1 ) 。类似的，可以定义行元笛卡儿积。 ( 1 3 ) g 的生成子图日是指满足日g ，且忡坎凹的子图。 ( 1 4 ) 设巧v 且k 矿，以n 为顶点，以两端点均在n 中的全体边为边集的g 的子图，称为n 的导出子图，记作g v d 。 ( 1 5 ) 设5 e 且巨矽，以局为边集，以e 1 中的边关联的全部顶点为顶点集 的g 的子图，称为局的导出子图，记作g 匹l 】。 ( 1 6 ) 设g 是连通图， k ( g ) = r a i n i t i ：绳g 的点割 为g 的点连通度或连通 度；称爪g ) = r n i n j s j ：跪g 的边割) 为g 的边连通度。 ( 1 7 ) 在图g 的顶点集中没有任何两个顶点是相邻的，则称此顶点集是独立 的。在任何这样的集中顶点数最多的一个称为最大独立集。g 的最大独 立集的基数称为独立数，记作口( g ) 。 ( 1 8 ) 设g 是无环图，m 为边的非空子集，如果肘中任意两条边在g 中均不 相邻，则称m 是g 的一个匹配。若对图g 的任何匹配m ，均有i m j l s f ，则称s 为g 的最小点覆盖。最小点覆盖的基数称为 g 的点覆盖数，记作f l ( g ) 。 ( 2 0 ) 设g 毫( 矿固是无向简单图，三为e 的一个非空子集，若g 中的每个顶点 都与中某条边关联，则称为g 的边覆盖。如果g 中任何异于三的 边覆盖工，均有俐i lj ，则称l 为g 的最小边覆盖。最小边覆盖的基 数称为g 的边覆盖数，记作，( g ) 。 ( 2 1 ) r x 表示大于等于x 的最小整数，卜j 表示小于等于x 的最大整数一 1 3 图的点邻域连通度 把图的顶点和边统称为图的构成元素，通常意义下的图的连通性参数都是在 各元素间彼此“独立”的前提下定义的。换言之，从图中去掉一个点子集或边子 集不影响其它点或边的存留。但现实中许多网络( 图) 中元素并不相互独立，比 如前面提到的间谍网等。为衡量此种网络的抗毁性( 即稳定性) ，人们相继引入图 的点邻域连通度，边邻域连通度等新参数。这些参数都是从邻域的角度出发定义 的，因此不再是普通意义下的连通性参数，c o z z e n s ，g u n t h e r 等人是这一领域的奠 基者。 1 9 7 8 年g u n t h e r 和h a r t n e l l 3 1 ，1 9 8 0 1 9 8 6 年g u n t h e r 4 1 ，【5 1 介绍了模型化间谍网的 思想。他们将间谍网模拟成图，通过点代表间谍和边代表他们之间直接的通信连 线建立了这种模型。考虑到某个间谍背叛以后，与其直接联络的间谍都将不再被 信任，就会全部失去作用。因此，从此种图中移去一个点的同时，应移去其所有 相邻的点。 定义1 1 设爿哪) 为一个图，对于任意的1 i v ( g ) ， ) = v 矿( g ) v 甜且v 与”相邻) ，称为甜的开邻域， 7 【甜】= 扣) u i v ( 称为z ，的闭邻域。相应地，书2 s = v l ， ，v 埘) 坎g ) ，定义0 “) 为s 的开邻域，记作；s u 为s 的闭邻域，记 1 2 j 作【明。 定义1 2 设点“坎g ) ，如果从g 中移去点甜的闭邻域 ”】，我们称点甜被 破坏。相应地，对于任意一个顶点的子集s v ( g ) ，如果s 中的每一个点都被破 坏，也就是说g - , i s ，记作g 俘( 下同) 不连通( 即d o ( g s ) 2 ) ，或者是一个团、 4 图的邻域参数研究 空图，我们称s 为g 的一个顶点破坏策略( 也称s 为g 的一个邻域点割集) 。 定义1 3 1 6 1i s g i 拘邻域连通度板g ) 定义为g 的最小邻域点割集所含的顶点数， 用k ( g ) = m i n i s ：s 为g 的一个邻域点割集 ( 这里要考虑图g 的所有邻域点割集) 表 示。 定义1 4 如果无向图g 的连通度颤g ) 劲( ，p 1 ) ，称图g 是刀连通的或g 为栉 连通图。若a ( g ) 砷萨1 ) ，称图g 是f 边连通的或g 为n 边连通图。 定义1 5 若板g ) 2 珊则称g 是m 邻域连通的，简记为m - n c 。一个图g 称为 临界卜邻域连通的，假如题啉且对任一u 坎g ) ，k ( g u ) = k - 1 ，其中 g u = g - m u 】( 下同) 。 s h u s h i hy w u 等1 1 给出了由聆卜连通图构造肚邻域连通图的方法： 把图g 的下列运算记作e 由e 作用在g 上产生的所有图的集合记作g e 。一 个新图g e g e 由下列步骤产生： ( 1 ) g 的每个点廓用一个阶数不小于d ( v ) ( v 的点度) 的团g 替代； ( 2 ) q ，c 吃最多有条边相连，当且仅当h 与吃在g 中相邻时，c i 和c v 2 有一条边相连； ( 3 ) c v 中的每个顶点最多与一条不完全含于g 中的边相邻。 在文献【1 】中给出的一个重要定理是：g 是m 连通图，g p 是e 作用在g 上得 到的图，则g e 是一个m - 邻域连通图。 这样，我们就建立起二者之间的关系，可以由一个m 连通图构造出相应的m 邻域连通图。 g u n t h e l l 4 , 5 , 7 进一步研究了图的结构与邻域连通度，我们用下面一个例子来说 明图的邻域连通度与其边数的微妙关系。 比如对下面图1 1 ，圈g o ，其点连通度k ( g o ) ，点邻域连通度酸a o ) ，边连通 度五( c l 。) 以及边邻域连通度a ( g 。) ( 见定义l ，8 ) 均是2 1 但是给c l o 添加一条边砂 后，如下面图1 2 ，得到图g l ，仍有七 1 ) = 彳( g 1 ) - - 2 ，但取g 1 ) = a ( g 1 ) ；l ；如果再给 g l 添加一条边删如图1 3 ，得到图g 2 ，其连通度和边连通度还是2 ，而 日g 2 ) = a ( g 2 ) = 2 = k ( c l o ) 2 a ( c 1 0 ) 。 绪论 _ k 。 图的邻域连通度和边邻域连通度往往是不等的，容易看出，这两个参数越大， 网络就越稳定。当然，这里的稳定与非邻域意义下的稳定是不同的。如对完全图 蜀，在非邻域情况下是最稳定的网络，但完全图本身就是一个团，所以顾蜀) ：o ，也 就是说在邻域场合下完全图是最不可靠的网络。 我们也可以看出，非邻域情况下对网络稳定性衡量的方法不能直接应用到邻 域情况下，因此提出了许多邻域参数用来衡量网络的稳定性，这也是我们的研究 意义所在。 1 5 本文主要工作 网络稳定性理论有着重要的应用价值，多年来一直是图论科学中一个很活跃 的课题。从事这一领域研究的人很多，研究范围也日趋广泛，理论成果也是日臻 丰富与完善。以此为背景，本文就邻域情况下网络的稳定性作了进一步的研究。 主要工作有： 第1 章是绪论，概括性地介绍了邻域情况下网络稳定性的研究背景，并讨论 了研究邻域情况下网络稳定性的实际意义，简单介绍了论文所需的一些相关知识， 给出邻域连通度、边邻域连通度的一些研究结果。 第2 章介绍了邻域完整度和边邻域完整度的产生背景、概念和意义，介绍了 几类基本图、图的笛卡儿积、联图、复合图和线图的邻域完整度与边邻域完整度 的相关结论。 第3 章介绍邻域离散数和边邻域离散数产生的背景和意义，给出了几类基本 图、树和区间图的邻域离散数，图的邻域离散数和一些已知参数之间的关系及边 邻域离散数的有关结论。 第4 章提出一个新的邻域参数邻域破裂度，对该参数与另两个邻域参数 7 第1 章绪论 作了简单的比较并给出了几类基本图和联图的邻域破裂度，并给出了邻域破裂度 的界及相关的一些研究成果。同时，本文定义了边邻域破裂度并给出了几类基本 图的边邻域破裂度及有关结论。 第5 章讨论了一个相关的参数图中度平方和的界，介绍了图中度平方和更 为精确的上界并对图中度平方和的下界进行了研究，给出两个改进的下界，并简单 介绍了利用图中度平方和的界精确确定一个图及其补图中三角形个数的简单应用 及相关的一些结论。 图的邻域参数研究 第2 章图的邻域完整度与边邻域完整度 2 1 问题的提出 图的完整度概念引入的灵感来自于通讯中断，是由三位美国数学家 c a b a r e f o o t ，r e n t r i n g e r 和h s w a r t 9 1 于1 9 8 7 年为研究图的脆弱性提出来的，他们 对图的这一参数的研究已经取得了许多非常有用的结果，后来，k s b a g g a ，w d g o d d a r d 和h c s w a r t 等 1 0 , 1 1 , 1 n y 对完整度作了更为深入的研究。 定义2 1 对于一个图g 兰( kd ，其点完整度定义为 ，( g ) 2 。m 州i n g ) i s l + m ( g s ) ) ， 其中m ( g 一研表示g s 最大连通分支的顶点数。 定义2 2 对于任一连通图g 毫( e 习，其顶点集m 一个子集，如果满足，( g ) = is * i + m ( g - - s ) ，则称，为图g 的一个完整度集( 厶集) 。 1 9 8 7 年c a b a r e f o o t ，r e n t r i n g e r 和h s w a r t 在研究完整度的基础上提出图的 边完整度的概念，并且他们给出了关于边完整度的一些结果。图的边完整度既是 一个与完整度平行的概念，又是一个与完整度相独立的概念。 定义2 3 对于一个图g 主( k 曰，其边完整度定义为 ，( g ) 2 捌x l + m ( o x ) ) ， 其中聊( g 一厕表示g x 最大连通分支的顶点数。 定义2 4 任一连通图g 毫( 巧助，其边集e 的一个子集f 称为图g 的一个边完整度 集( ，集) ，如果r 满g = 1 ( g = if i + 珊( g r ) 。 为刻画间谍网的稳定性，1 9 9 6 年m b c o z z e n s 等【1 3 】引入图的邻域完整度的概 念。这个概念是在图的邻域连通和图的完整度两个概念的基础上产生的衡量图( 网 络) 稳定性的新参数，这是完整度概念向邻域情况的扩展，也是邻域意义下第一 个比较理想的网络稳定性参数。它从邻域的观点刻画了如何以最小的代价使图( 网 络) 遭受到最严重的破坏。对于邻域情况下网络稳定性的研究，目前较多的是点 ( 边) 邻域完整度，下面是有关的研究现状。 2 2 ( 点) 邻域完整度 定义2 5 图g 的顶点集的一个子集s 称为g 的一个点破坏策略，假若s 中的 9 第2 章图的邻域完整度与边邻域完整度 点及其所有邻点( s 的闭邻域) 都从g 中移去，记g 的剩余部分为g s 。 定义2 , 6 一个图g 毫( kd 的邻域完整度，用e n i ( g ) 表示，其定义为 v n i ( g ) = s r a 州i n g ) s + r e ( g s ) ， 其中s 为g 的任意一个顶点破坏策略，m ( g s ) 表示g s 最大连通分支所包含的顶 点数。 定义2 7 对于一个图g 毫( k 目，若顶点的某个子集s v ( g ) ，满足v n r g ) = l ，i + 搠( g ) ，则称s 为g 的一个邻域完整度集，简记为聊- 集，一个图的删- 集一般不是唯一的。 2 2 1 几类基本图的邻域完整度 c o z z e n s 等在 1 3 1 【1 6 1 中研究了几类基本图的邻域完整度，邻域完整度与图的 其它参数的关系等，主要结果有： ( 1 ) ( a ) e n i ( k ) = i ；嘞v n i ( k ，护2 ； ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( c ) 聊以) ：2 丽1 4 础；( d ) 1 1 = 1 2 石 一3 肝5 v n i ( g ) = 2 珂= 4 ； 1 盯= 3 ( c ) v n z ( 。) = l 。 在所有h ( 庀1 ) 阶树中，r 的邻域完整度最大。 对任意整数，l s ，2 i 再 一4 ，都存在一棵甩阶树t ，1 1 e v n i ( t ) = i 。 任一连通，非完全的n ( n 3 ) 舢f lg ，其v n i - 集必是g 的一个邻域点割 集。 v m ( 6 3 = l 当且仅当图g 包含一个星图为它的生成子图或者g 是一个完 全不连通图。 ( 6 ) 对任一图g ，聪g ) v n i ( g ) 5 i ( g ) 。 ( 7 ) 任一无孤立点的图g ，都有啪( g ) 幽2 ，w v i ( g ) 口( g ) ，w v l ( g ) s ( g ) ，其中口( g ) 和( g ) 分别表示g 的点独立数与点覆盖数。 1 0 图的邻域参数研究 2 2 2 图的笛卡儿积的邻域完整度 两个图的笛卡儿积是图运算中最基本的一类运算，利用图的笛卡儿积运算可 以用较简单的图来表达一个给定图的结构，给我们研究图的性质带来许多方便。 在 1 7 】中作者给出了下面的结论。 ( 1 ) 设崆3 ，g 为一个阶数为n 的圈，则完全图肠和g 的笛卡儿积k 2 g 的 邻域完整度满足：肿( g ) v n i ( k 2 e ) 胛。 ( 2 ) 协w 2 _ 2 ，r 为一条阶数为行的路，则完全图局和r 的笛卡儿积吃只的邻 域完整度满足：翰7 ( p ) v m ( x ：只) - 2 ) ，g 是g 的复制，i = 1 ，2 ，g 。 匕v ( g ) 在g 中的复制记为t ，作双射： 西：u t 辛g fi = l ，2 ，g ， 则v ( g ) ) = u 矿( g ) ， e 饵( g ) ) = i = ! e ( g f ) u 嵋0 a , i ，e ( 日) ，e 矿( g f ) 唧矿( q ) ) ， 其中n 矿( q ) = ，n e ( q ) = 。 从这个定义可以看出，坝g ) 实际上就是将目的每个顶点都用g 代替，日中的 每条边用连接两个g 所有顶点之间的边代替所得的图，其整体结构与日相同。而 上“g ) 与g ( 一般是不同的，即图的复合运算不满足交换律。 1 2 图的邻域参数研究 定义2 1 1 当复合图定义中的日为路时，我们称这样的复合图为路状复合图。 定义2 1 2 当复合图定义中的胃为圈时，我们称这样的复合图为圈状复合图。 关于复合图在 2 1 l 中给出了下面的一些结论。 ( 1 ) 日和g 是连通图，则v n t c h ( o d ) s 盯( 日) 仃( g ) ，其中c r ( h ) 和盯( g ) 分别 表示日和g 的点控制数。 ( 2 ) h 和g 是阶数不小于3 的图，则v n i ( h ( g ) 她图旧) 。 ( 3 ) 只 丝) ，c 它3 ) 分别表示胛个顶点的路和圈，则 n v n i ( p 2 , j - 【 9 一3 罔 1 ( 7 ) 1 ) n = 2 ，3 时，v n i ( g ( p 2 ) = 4 k 9 n 3 j i 9 n 2 ) 砬4 ，硷巩时，v n z ( g ( p 2 ) = 2 忑 一3 刀，其中6 。表示使玢坝g ( 尸力) 取值为厮卜恻蝴，且满足却仨翥! ：怒，。 ( 8 ) 当硷“时，v n i ( c k ( c ) ) = 2 磊 一3 ，其中巩的取值与上面结论( 7 ) 图的邻域完整度与边邻域完整度 中的相同。 一3 nk 9 n 4 k 9 n 七= 3 注：c 3 ( e ) = k 3 。 ( 1 0 ) 通过以上六种形式复合图邻域完整度的讨论，可以看出它们在邻域完 整度意义下都比较稳定，但还是有区别的，作者通过横向和纵向比较 懈) ，以c ap k ( k , , ) y i t i c k p , , ) ，以c a 六种形式复合图的邻域完 整度，得出当阶数一定时，圈的圈状复合图的邻域完整度最大，也就 是说这样构造的网络最稳定。 2 3 边邻域完整度 在研究图的邻域完整度的同时，1 9 9 4 年m b c o z z e n s 等【2 2 1 又提出了图的边邻域 完整度的概念。这概念同样是建立在图的边邻域连通和图的边完整度这两个概 念基础上的，它从邻域的观点同时反映了破坏图( 网络) 的难易程度以及图的遭 受破坏的程度。 2 8 1 边邻域完整度定义 定义2 1 3 设g = ( kd 为任一连通图，g 的边邻域完整度，用e n i ( g ) 表示 e n d ( g ) 2 x 翌驰) 阁+ m ( g x ) ) ， 其中x 为g 的任一边子集，所( 似) 表示g x 最大连通分支的顶点数。 定义2 1 4 若边的某个子集x ，满足互m ( g ) = l f i + 删，g r ) ) ，则称为g 的一个边邻域完整度集，简记为e n i - 集。 2 3 2 边邻域完整度有关结论 c o z z e n s 等在给出边邻域完整度概念的同时对其进行了研究，在文献 2 2 3 q b 给 出了一些研究成果，主要结果有； ( 1 ) e n i ( k 取。) = ：1 n 埘，刀+ 1 ：三：。 厮纠 ，、【 i lk 盯刚9 图的邻域参数研究 ( 2 ) e m 假) = 2 万瓦1 3 。 ( 3 ) 缆刀阶树，则2 s 踟( d 型l 呱r ) 。 ( 4 ) 对任意正整数，2 ，f 2 ；i - 1 3 ，都存在一棵栉阶树z 使脚呱7 ) 2 ，。 m b c o z z c n s 和s y w u 2 3 1 还给出了边邻域完整度的界： ( 1 ) ( a ) v n i ( k 1 ，+ l 产1 伦3 ) ；( b ) e n i ( k 1 ，+ 1 闩伦3 ) ； ( c ) 啪( 墨沪1伦1 ) ； ( d ) e m = 伦1 ) 。 对任意图g = ( 旧，有下面的结论。 ( 2 ) ( a ) a ( g ) s e m ( g ) ，如果a ( g ) = e n i ( g ) ，那么g f f j 每个 e n i - 集，为g 的 一个最小邻域边割集并且g r = ； c o ) 融h g ) s e 嗽g ) ，如果吼取g ) _ 脚( g ) ，那么g 的每+ e n l - 集，一定 为g 的一个匹配；