（应用数学专业论文）图的连通参数的相关研究.pdf

西北工业大学硕士学位毕业论文摘要 摘要 在计算机网络或通讯网络的设计与维护过程中，网络的抗毁性是一项重 要的性能指标网络设计的基本思想之一就是使其在受到外部攻击时不易被 破坏，而且，在万一遭到破坏时也能够容易得到修复我们通常用无向连通图 来表示网络，其中图的顶点代表网络站点，边代表网络站点间的直通线路在 此数学模型之下，人们开始讨论抗毁性的有关测度，早期的研究主要是围绕 图的连通度和边连通度展开的伴随着研究的深入，人们发现用这两个参数 刻画图的抗毁性存在明显不足之处后来，人们引入了一些其它的参数，如坚 韧度、离散数、完整度、粘连度这些参数不仅考虑了网络被破坏的难易程 度，而且还考虑到了网络遭受的毁坏程度，相比图的( 边) 连通度而言，是些 较为合理的刻画网络抗毁性的参数 本论文在总结和比较以上连通性参数的基础上，引入了能比较客观、相对 简单的刻画图的连通性的一个新参数图的相对粘连度，并对这个参数进 行了初步的研究论文第一章分析了图的连通性参数的研究背景和实际意义 并介绍了论文所需的一些相关知识和本论文的主要结果论文第二章介绍了 图的连通度、边连通度、坚韧度、边坚韧度、离散数、完整度、边完整度、 粘连度、边粘连度等图的连通性参数，对它们做了比较归纳和系统分析论文 在第三章详细研究了一些特殊图( 完全图、圈、路、星、彗星、完全二部图、 完全k 一部图) 的相对粘连度，讨论了圈的相对粘连度的界，图的运算的相对粘 连度，树的相对粘连度的算法，相对粘连度与其他参数的关系第四章讨论了 图的相对粘连度意义下的最值网络的构造以及关于图的相对粘连度的 n o r d h a u s g a d d u m 型问题的结果第五章对图的边相对粘连度进行了定义并 做了一些简单研究第六章讨论了相对粘连度的计算问题，证明了图的相对 粘连度的计算是n p 完全问题最后，在结束语里我们对图的连通参数的定义 进行了归纳统一，并提出了进一步研究的问题 关键词，网络抗毁性，连通度，离散数，坚韧度，完整度，粘连度，相对粘连度 边相对粘连度 i i l 西北工业大学硕士学位毕业论文 a b s t r a c t a b s t r a c t i nt h e p r o c e s s o f d e s i g n i n g a n d g u a r d i n gc o m p u t e r s o rc o m m u n i c a t i o n n e t w o r k s ，t h e v u l n e r a b i l i t y o ft h e mi sa l l i m p o r t a n tp e r f o r m a n c e c r i t e r i o n t h e r e f o r e ，o n eo f t 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 t e 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 l a t t a c ka n d ，t h e s ea r ee a s i l yr e c o n s t r u c t e di ft h e yd o r e a l l yg e td i s r u p t e d w eo f t e nm o d e l e dt h en e t w o r k sb yc o n n e c t e dg r a p h s ，w h e r e t h ec o m m u n i c a t i o ns t a t i o n s a r e r e p r e s e n t e db y t h ev e r t i c e sa n dt h ed i r e c t c o m m u n i c a t i o nl i n k sa r e r e p r e s e n t e db yt h ee d g e s u n d e rt h i s m a t h e m a t i c a l m o d e lo f n e t w o r k s ，p e o p l eb e g a n t of i n ds o m ec r i t e r i at om e a s u r et h e v u l n e r a b i l i t y o fn e t w o r k s a tt h e b 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 y a n d e d g e c o n n e c t i v i t y a r et w op a r a m e t e r so f t e nu s e df o ri t b u t r e c e n t l y , p e o p l e f o u n dt h a tt h e s et w op a r a m e t e r sd on o td o v e r y w e l lf o r i t ，s os o m en e w p 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 e g r i t y , t e n a c i t yh a v eb e e n i n t r o d u c e di nt h ep a s td e c a d e a l lo ft h e s ep a r a m e t e r sa r em o r er e a s o n a b l et h a n 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 y , f o rt h e yc a l l m e a s u r en o to n l yt h e a 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 w b a d l yt h en e t w o r ki s d a m a g e d i nt h i st h e s i s ，b ys u m m i n g u pa n dc o m p a r i n go f t h em a i nr e s u l t sa b o u tt h e s e p a r a m e t e r s ，w ei n t r o d u c ean e wc o n n e c t e dp a r a m e t e r , t h er e l a t i v et e n a c i t yo f g r a p h s ，w h i c hi s c o n v e n i e n ta n do b j e c t i v et om e a s u r et h ev u l n e r a b i l i t yo fn e t - w o r k si ns o m ee x t e n t ，a n dd os o m ep r e l i m i n a r yr e s e a r c ho ni t i nc h a p t e r1 ，w e a n a l y z et h es i g n i f i c a n c ef o rd i s c u s s i n gt h ec o n n e c t i v i t yp a r a m e t e r s ，t h e np r e s e n t t h em a i nr e s u l t si nt h i st h e s i s i n c h a p t e r2 ，w es u r v e y t h er e s u l t so ft h e c o n n e c t i v i t yp a r a m e t e r s ( t 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 e g r i t y , t e n a c i t y ) i n c h a p t e r3 ，w ed e t e r m i n e t h er e l a t i v et e n a c i t yo fs o m es p e e i f i cf a m i l i e so f g r a p h s ( s u c ha sc o m p l e t eg r a p h s ，c y c l e s ，p a t h s ，s t a r s ，c o m e t s ，c o m p l e t eb i p a r t i t eg r a p h s a n dc o m p l e t e k p a r t i t eg r a p h s ) t h eb o u n d so f t h er e l a t i v et e n a c i t y , t h er e l a t i v e t e n a c i t y o ft h e o p e r a t i o n o fg r a p h s ，t h e r e l a t i o n s h i p b e t w e e ni ta n do t h e r p a r a m e t e r s ，t h er e l a t i v et e n a c i t ya n d i t sa l g o r i t h mf o rt r e e sa r ea l s oi n v e s t i g a t e d i nt h i sc h a p t e r ，i nc h a p t e r4 ，t h em a x i m u ma n dm i n i m u mn e t w o r k sw i t hg i v i n g i v 西北工业大学硕士学位毕业论文 a b s t r a c t o r d e ra n dr e l a t i v et e n a c i t ya r ea l s oc h a r a c t e r i z e d i nc h a p t e r5 ，w ed i s c u s st h e e d g e r e l a t i v et e n a c i t yo fg r a p h s ，a n di nc h a p t e r6w e d i s c u s st h ec o m p u t a t i o no f t h er e l a t i v et e n a c i t yo f g r a p h s f i n a l l y ，s o m ei d e a sa r ep r o p o s e df o rf u r t h e rs t u d y o ft h er e l a t i v et e n a c i t yo fg r a p h s k e y w o r d s ：v u l n e r a b i l i t ya n ds t a b i l i t y o fn e t w o r k s ，c o n n e c t i v i t yp a r a m e t e r so f g r a p h s ，c o n n e c t i v i t y ，s c a t t i n g n u m b e r ，t o u g h n e s s ，i n t e g r i t y , t e n a c i t y , r e l a t i v e t e n a c i t yo fg r a p h s ，e d g e r e l a t i v et e n a c i t yo fg r a p h s v 西北工业大学硕士学位毕业论文 第一章引言 第一章引言 述 在计算机网络或通讯网的设计过程中，网络的抗毁性是一项重要的性能 指标网络设计者既要考虑网络在受到外部攻击时不易被破坏而免受巨大损 失，又要考虑万一网络遭到破坏后其能够容易修复而承受较小的代价因此。 关于网络抗毁性研究已逐步引起人们的高度重视 我们通常用无向连通图来表示网络，其中图的顶点代表站点，边代表直 通线路众所周知，网络的抗毁性与其对应连通图的连通性有十分密切的关 系，一般来说，一个图的连通性越好，它对应的网络稳定性就越高因此，研究 图的连通性有十分重要的实际意义图的连通性是图所具有的基本属性之一 目前有两种截然不同的方法来研究一个图的抗毁性一种方法基于确定性理 论，而另一种是基于概率方法本文只讨论前一种方法，并且我们约定本文用 到的图、网络及网络图是等同的确定性理论的基本思想是姆某些被认为合 理的图的不变量作为刻画图的连通性的参数，文中介绍的图的连通度、边连 通度、离散数、坚韧度、边坚韧度、完整度、边完整度、粘连度、边粘连度 以及我们新引入的相对粘连度和边相对粘连度均可有效地刻画图的连通性 本论文在介绍、总结和比较以上连通性参数的基础上，引入了能比较客 观、相对简单的刻画图的连通性的新参数图的相对粘连度并对这个参 数进行了初步的研究论文第一章分析了图的连通性参数的研究背景和实际 意义，并介绍了论文所需的一些相关知识和本论文的主要结果论文第二章 介绍了图的连通度、边连通度、坚韧度、边坚韧度、离散数、完整度、边完 整度、粘连度、边粘连度等图的连通性参数，对它们做了比较归纳和系统分 析论文在第三章详细研究了一些特殊图的相对粘连度( 完全图、圈、路、 星、彗星、完全二部图、完全k 一部图) ，讨论了图的相对粘连度的界，图的运 算的相对粘连度。树的相对粘连度的算法，相对粘连度与其他连通参数的关 系，在第四章讨论了图的相对粘连度意义下的最值网络图构造和有关 n o r d h a t i s g a d d t t m 型问题的结果第五章对图的边相对粘连度进行了一些讨 1 西北工业大学硕士学位毕业论文第一章引言 论第六章讨论了相对粘连度的计算问题，证明了图的相对粘连度的计算是 n p 完全问题最后，在结束语里我们对图的连通参数的定义进行了归纳统 并提出了进一步研究的问题 1 2 基本概念和术语 为了便于阅读，我们在这里先介绍本论文用到的一些图论基本概念和术 语，文中未加说明的参见r o n d y 和m u r t y 9 1 一个无向图g 是指个有序三元组( 矿( g ) ，e ( g ) ，妒( g ) ) ，其中v ( g ) 是非空 的顶点集，e ( g ) 是不与v ( g ) 相交的边集，缈( g ) 是关联函数，它使g 的每条边 对应于g 的无序顶点对( 不必相异) 若e 是一条边，而“和v 是使得缈( e ) = u p 的顶点，则e 称连接“和v ，顶点“和v 称为e 的端点边和它的端点称为关联 的；与同一条边关联的两端点或与同一顶点关联的两条边称为相邻的两端 点重合的边称为环，端点不相同的边称为连杆，既没有环也没有连杆连接同 一对顶点的图称为简单图v ( g ) 中元素的个数和e ( g ) 中元素的个数分别称 为图的阶和边数每一对不同的顶点都有一条边相连的简单图称为完全图 一个疗阶完全图记为k 。阶数为1 的简单图称为平凡图，边数为0 的图称为 空图，一个h 阶空图记为e 若一个图的顶点集可以分成两个非空子集x 和 r ，使得每条边都有一个端点在z 中，另一个端点在j ，中，称其为二部图，把这 样的一种分类( x ，y ) 称为图的一个二分类完全二部图是具有二分类 ( z ，r ) 的简单二部图，其中x 的每个顶点都与j ，的每个顶点相邻；若l z - 聊 而忸1 = n ，则这样的图记为k 。特别地称k 一。为星类似地，可以定义完全 k 一部图彗星图c 。，是指将路尸，的一个端点与星状图k l ，的中心节点合并丽 得到的图边数和阶都有限的图称为有限图本论文讨论的是有限简单图 图g 的顶点v 的度如( 是指g 中与v 关联的边的数目，每个环算作两条 边。通常用6 ( g ) 和( g ) 分别表示图g 的顶点的最小度和最大度 西北工, 3 k 大学硕士学位毕业论又第一章l 言 两个图g ( 矿( g ) ，e ( g ) ，y 。) 和h ( 矿( h ) ，e ( 日) ，_ ；f ，。) 称为同构的( 记为 g 兰h ) ，如果存在两个双射0 ：v ( g ) 寸v ( h ) 和妒：e ( g ) 寸e ( h ) 使得对于 任意a e ( g ) ，= 力铮( 娟口) ) = ( c ) ，哆) 耳印称图h 是g 的子 图( 记为h g ) ，如果v ( h ) y ( g ) ，e ( h ) e ( g ) ，并且h 是g 上的限 制g 的生成子图日是指满足v ( g ) = v ( h ) 的子图设v 是矿( g ) 的非空真子 集，以矿为顶点集并以g 中两端点均在v 中的边为边集的子图称为g 的由 v 导出的子图，简称导出子图，记为g v ，导出子图g v v 】记为g y 设 f 是e ( g ) 的非空子集，以f 为边集并以g 中由f 中边的端点为顶点集的 子图称为g 的由e 导出的子图，记为g e 。】，g f 表示从g 中删去e 中的边 ( 但不删去端点) 后得到的子图图g 的补图百是指和g 有相同顶点集v 的 一个简单图，而且在召中两个顶点相邻当且仅当它们在g 中不相邻简单图 g 称为自补的，如果g 兰百 设g 。和g ：是g 的子图若g 和g ：没有公共顶点，则称他们是不相交的； 若g 和g ：没有公共边，则称他们是边不重的g 和g2 的并图g u g ：是指g 的一个子图，其顶点集为v ( g 。) u v ( g ：) ，其边集为e ( g i ) u e ( g 2 ) 类似可以 定义g 2 和g ，的交图g 1r 、g 2 不相交的两个图g ，和g ：的联图g t + g ：是指在 g lu g ：中，把g l 的每个顶点和g ：的每个顶点连接所得到的图图g ：和g 。的 笛卡儿积g ，g 。是一个简单图，其中粥g 2 ) = 瞒) x 啊q ) ，且 对，屯矿( g 1 ) ，x 2 ) y 2 v ( g 2 ) ，( 瓴，而) ，挑，儿) ) 目，g l g 2 ) 铮或者x - = m 且 ( x 2 ，_ y 2 ) e ( g 2 ) ，或者x 2 = y 2 且( x l ，y 1 ) e e ( g 1 ) 类似的，我们可以定义h 元笛 卡儿积，如n 维立方体姨一k 2 x k 2 x k 2 是( 共丹个k 2 ) ，它是一个非完 全的2 一部图 1 西北工业大学硕士学位毕业论叉第一章引言 g 的一条途径是指一个有限非空序列缈= q 巳屿，一 , e k v k ，它的项交替 为顶点和边，使得对1 i k ，e 的端点是v h 和1 ，f ，称w 是从v 。到v 。的一条 途径，或一条( v 。，v 。) 途径顶点v 。和v 。分别称为w 的起点和终点，而 v l ，v 2 ，h i 称为的内部顶点整数k 称为的长若途径的顶点互不相 同，则称为路，记为pk ，我们把一条起点为v 。，终点为v ；的路称为( v 。，v 。) 路g 的两个顶点“和v 称为连通的，如果在g 中存在( “，v ) 路连通是顶点 集v ( g ) 上的一个等价关系，于是就存在v ( a ) 的一个分类，把v ( a ) 分成非空 子集v i ，v 2 ，吃，使得两个顶点是连通的当且仅当它们属于同类子图 g 巧】，c v 2 ，g 【圪】称为g 的连通分支若g 只有一个连通分支，则称g 是 连通的；否则称g 是不连通的g 的连通分支数记为由( g ) ，最大连通分支的 阶数记为m ( g ) 称一条途径是闭的，如果它有正的长且起点和终点相同若一条闭途径 的起点和内部顶点各不相同，则称它为圈长为k 的圈称为k 圈；3 圈常称为三 角形包含g 的每个顶点的路称为h a m i l t o n 路；类似的，g 的h a m i l t o n 圈是 指包含g 的每个顶点的圈一个图若包含h a m i l t o n 圈，则称这个图为 h a m i l t o n 图， 若v 的子集使得g v - 不连通，则称为g 的顶点割k 顶点割是指有 k 个元素的顶点割完全图没有顶点割。若g 至少有一对不相邻的顶点，则g 所具有的七顶点割中最小的k ，称为g 的连通度，记为r ( g ) ；否则定义r ( g ) 为 v 一1 于是，当g 不连通时，r ( g ) = 0 若r ( g ) 七，则称g 为k 连通的对v 的子 集s 和f ，用【s ，f 】表示一个端点在s 中，另一个端点在s 中的所有边的集 所谓g 的边割是形如( 墨两的子集，其中s 是y 的非空真子集，且s = v s ，一 个k 边割是指有k 个元素的边割若g 非平凡且f 是g 的一个边割，则g e 。 不连通；于是g 的边连通度a ( g ) 定义为g 的所有七边割中最小的k 若g 是 - 4 西北工业大学硕士学位毕业论文第一章引言 平凡的，则定义五( g ) 为0 若旯( g ) t ，则称为k 边连通的 设定v ( g ) ，如果图g 的每条边都与k 中某点关联，则称莨是g 的 一个覆盖，如果g 中没有适合l k i k 的覆盖k 。，则称k 是g 的最小覆盖，此 时记( g ) ：刊k f ，称为g 的覆盖数设s y ( g ) ，如果s 中任意两个顶点在 g 中均不相邻，则称s 是g 的一个独立集，g 中最大的独立集的顶点数，称为 g 的独立数，记作口( g ) 1 3 本论文主要结果 第章分析了图的连通性参数的研究背景。并讨论了研究图的连通性参 数的实际意义，最后介绍了论文所需的一些相关知识 第二章介绍了图的连通度、边连通度、坚韧度、边坚韧度、离散数、完 整度、边完整度、粘连度、边粘连度等图的连通性参数，对它们进行了比较、 分析和系统归纳 第三章首先定义了图g 的新连通参数图的相对粘连度 6 ( g ) 2 s m 。c a x ( g s ) 一i s l m ( g s ) ，其中c ( g ) 表示g 的点割集然后就 特殊图类( 完全图、星图、路、圈、完全二部图、彗星图、完全k 一部图) 进 行了讨论，随后研究了一般圉的相对粘连度的界，并对运算图( 子图、笛卡儿 积、格子图、立方体图、联图、笼子图) 的相对粘连度做了界定，最后讨论 了图的相对粘连度与有关参数的关系，探讨了树的相对粘连度的算法在第 三章得到结果如下： 1 ) 对于完全图足。伽2 ) 来说，6 ( e ) = - ( n 一1 ) 2 ) 对于配巍郧扩 二笔冀 3 ) 对于路只来说，鹕，= 倍冀装 4 ) 对于星图k i 川来说，有6 ( 置一。) = 一3 5 西北工业大学硕士学位毕业论文第一章引- 2 5 ) 对于彗星图c ，来说，6c e j 2 f ：二：羹鲁萋： 6 ) 设g 为完全女部图k 。，贝l jb ( k 。) ：n ，。一妻。，1 ，t i o 7 ) 设g 是完全二部图k 。，则6 ( g ) = m n 一1 ：其中m 月 8 ) 设g 是”阶连通图，则抛一 一l 6 ( g ) ! 二竺塑业，其上界在星图取 得；下界在完全图取得 9 ) 设g 是n 阶连通图，则卜n 蔓b ( g ) h 一3 上、下界分别在星图和完全 图取得 1 0 ) 拧阶连通图g 的相对粘连度b ( 6 ) 的次上晃疗一4 和次下界2 - 玎不可达 到除此之外，介于它们之间的任意整数，b ( g ) 均可达到 1 1 ) 如果h 是g 的支撑子图，则b ( h ) b ( g ) 1 2 ) 设1 珊n ，贝0 6 ( g m g n ) = 啪+ n m h f 三 1 3 ) 对于任意正整数吩 2 ，一七) ，有嗽邺2 仁，珥窑冀数 1 4 ) 对于n 维立方体q ( h ) 来说，有b ( q ( 。) ) = 6 ( p 2 尸2 p 2 ) 2 1 1 5 ) 设g 和g 2 分别是m 和n 2 阶的非平凡的连通图，则就其联图g t + g z 有：b ( g 1 + g 2 ) = m a x 氆( g 1 ) 一”2 ，b ( g 2 ) 一玎1 ) a e 毫卜沪引， “1 l荔j 一，、f 一1 ，一峨偶数， 1 7 ) 设g 为k ：c 一则6 ( 足2 。c 一) 2 ；r j ，为- j ；蟊 1 8 ) 设g 为笼子图c 。c 。( m 疗) ，则 西北工业犬学硕士学位毕业论文第一章引言 b ( g ) = 1 ， m n 且m ，”均为偶数 一( 了m + 2 ) ， 一( 詈+ 2 ) ， ( 旦兰+ 2 ) 聊 n 且为偶数，n 为奇数 m n 且m 为奇数，n 为偶数， m 2 6 ) ，贝l j 6 ( g ) n 一2 5 一l ，此界在当g 为n 阶 昙正则图时取得到 z 2 2 ) 设g 为非完全h 阶连通图，其中n 4 ，其最长路的长为p ，则 b ( g ) n p 一1 若图g = ( v ，e ) ，其中v ( g ) = v l ，v 2 ，v 2 ，”拍+ l ，1 ) ； 竺s | s 塑： 32 篇馏2 k ：l i 豸三戮i 防2 饿妒i0 ( m o d 2 ) ，矗2 v 。v ， w ，+ ，n ，至少取一个( 1 ，2 t ，= 。1 结论取等号，即6 ( g ) = n c 1 2 3 ) 若g 为n 阶非完全连通图，则 1 - 8 _ 蹦g ) _ 哪6 ( g ) + 6 ( g ) 一1 7 ) 若g 是其补图也连通的”阶连通图，则 ( 3 - n ) ( n - 5 ) 6 ( g ) 6 ( 0 3 - 而一； ( h ) ，( k mh ) = p - r + l ( 其中，= m a x n 1 ，n 2 ，) ) 定理2 4 4 对于胛维立方体幺，有1 ( 0 。) s 1 + 2 ”1 定理2 4 5 【2 1 设g 是一个月阶图，则 ( a ) ，( g ) = 1 ，当且仅当g 为空图时 ( b ) ，( g ) = 2 当且仅当g 的所有非连通分支都是边或者唯一的非连通分支是 星图时， ( c ) 当且仅当g 为非完全图且g 的围长不小于5 时，i ( g ) = n 一1 ( d ) 当且仅当g 为完全图时，i ( g ) = 图的完整度的概念的引入【4 1 的灵感来自于通讯中断，但其定义并不要求 图是连通的后来，有人又对完整度作了更深入的研究，得到了许多有用结果 【2 l 其中包括，最大图问题，完整度与其它参数的关系，图的运算的完整度 等等围的完整度用来刻画图的连通性，对某些图类优于图的连通度一般情 况下，完整度愈大，图的连通性愈好当然，关于图的完整度的计算问题实际 上是一个n p 完全问题1 1 3 】至于边完整度，与图的完整度一样有许多好的结 1 3 西北工业大学硕士学位毕业论文第= 章圈的连通性参数 果，详见参考文献 3 ，4 ，7 ，1 7 ，2 0 ，2 3 关于边完整度的计算问题也是n p 。完全问 题，详见文献【2 】值得一提的是后来有人又提出了平均完整度的概念，也 有人提出了一个可以同时代表完整度、边完整度和平均完整度的综合性参数 2 5 图的粘连度和边粘连度 t ( 0 0 = = m l i is 烈i + g m ( 一g 回- s ) 心ec ( g ) ； 对于满足丁( g ) = 盟辫的s 称为g 的r 一集 定义2 5 2 对于一个连通图g ，图的边粘连度定义为 r ( g ) ；m i l i s 印l + r e ( 一o f - ) s ) ：y c _ e ( 0 3 ： 对于满足兀g ) = 坐三辫的s ”称为g 的丁- 集 定理2 5 3 ( a ) t ( k 。) = 珂；( b ) 丁( 一) = 忑2 定理2 5 4 【珊设k 。是个完全k 部图， 其中 l + 九， 女2 ，n - 1 ，f = l ，2 ，一，t ，r ( k 一n ，一t ) = 半 图的粘连度的提出不仅考虑到了对网络的破坏情况，而且考虑了网络 遭到破坏后剩余部分的情况，相l i ：z t ；是- - 个较为合理的刻画图韵连通性的 参数f l l 】而边粘连度的大多数结论是关于图的边粘连性的，边粘连的图类似于 正则图，是十分稳定的，其实在实际中许多高度稳定的通讯网络或计算机网 络的拓扑结构大都是边粘连的2 “当然，无论粘连度，还是边粘连度的计算问 题均为n p 完全问题 1 4 西北工业大学硕士学位毕业论文第三章图的相对粘连度 第三章图的相对粘连度 3 1新参数的引入 对于网络的稳定性研究的一个重要指标就是其抗毁性，而描述其抗毁性 的一个重要测度就是网络图的连通性从上一章我们知道曾有好多参数被用 来刻画图的连通性。它们从不同的出发点和不同的角度界定着图的连通性， 可以说各有侧重、各有特点但它们无非想回答两个基本问题：( 1 ) 网络的 若干节点( 或边) 遭到破坏后，仍有多少节点可以相互通讯( 2 ) 重新使网 络连通存在多大困难如果我们用图g = ( 矿，e ) 代表网络，令s u ( g ) 或 e ( g ) ，m ( g s ) 表示g s 的最大连通分支的阶，国( g s ) 表示g s 的连通 分支的数目那么从某种程度讲，i s i 和m ( g s ) 的实际含义就是要破坏网络 所付出的“代价”；而国( g s ) 则是表明网络被破坏后的“毁坏程度”或“破 坏效果”为了有效地刻画网络的抗毁性，我们引入新的连通性参数一图的 相对粘连度b ( g ) = m a x 。、 c o ( g s ) 一 s i - m ( g s ) ) ，其中c ( g ) 表示g 的 j e l u ， 点割集此参数虽然类似于图的粘连度，但它作为图的连通性参数在描述和 刻画图的连通性时会显得更客观、更方便些，一方面，图的粘连度在计算时 采用比式，相对而言此参数在计算时比较容易些；更主要的是，对于某些图 来说，用此参数描述其连通性相对而言比较客观一些如对于长为n 一1 的路 p n 而言，用粘连度刻画的结果是：对于任意大于2 的整数女，r ( p 2 。) = l ， 而7 1 ( p 2 。) = 竺；旦；而用此新参数描述6 ( ) = 0 ；6 ( 艺。) = 1 ，显然，前者区分 k 度好，但后者较合情理另一方面，对于同一个图g ，其相对粘连度b ( g ) 在 某种程度相似于其粘连度t ( g ) ，但是，它们确实是两个不同的参数，考虑图 g l = k 1 + ( k 。一；u b ) 和图g ：= k 2 + ( k _ 3 u e ) ，显然b ( g ，) = 6 ( g ：) ，但 1 5 西北工业大学硕士学位毕业论叉第三章图的相对粘连度 我们容易知道t ( g i ) t ( g 2 ) ，除非”= 2 b + 1 而对于下面的图g 3 和图g 。，显然 1 有t ( g ) = t ( g ，) = ，但b ( g ，) = 3 b ( g 2 ) = 4 当然，引入图的相对粘连度的动 z 机并不仅在于此，从后面各章节我们会看到此参数在描述和刻画图的连通性 以及其他方面有更广泛的应用 t ( g 3 ) = 1 2 b ( g ，) = 3 t ( g 。) = i 2 b ( g 。) = 4 3 。2 特殊圈的相对粘连度的讨论 首先，我们约定下文考虑的图均为非平凡的连通简单图，对文中所用术 语和记号，如未说明，均可参见文 9 下面先给出几个相关定义，然后讨论 几类特殊图的相对粘连度 定义3 2 1 设g 是连通图，s 亡矿( g ) ，当g 不是完全图时，若g s 不 连通，则称s 是g 的点割集当g 为完全图k 。时，足。的任一”一1 个点的子集 称为k 。的点割集 记g 的所有点割集的集合为c ( a ) 定义3 2 2 图的相对粘连度6 ( g ) ：- s m “a x 6 ) 妇( g s ) 一i s 卜m ( g s ) ， 显然，6 ( g ) 值愈大，说明此图g 对应的网络的稳定性愈差，对于破坏者来说 就愈容易成功 ：g s c c ( g ) 且6 ( g ) ：= k 姆一d i s i - m ( g 一曲) ，称s 为g 的一个6 一集 定理3 2 3 对于完全图k 。0 2 ) 来说，b ( k 。) 2 一伽一i ) 一1 6 西北工业大学硕士学位毕业论文第三章图的相对粘连度 证明：因为对于任意s c ( k 。) 有 s n 一1 ，m ( k 。一s ) = 1 和c o ( k 。一s ) = 1 故 b ( k 。= w m a ( x 扫( 彪。一s ) 一i s f - m ( x 。一s ) = 一( 疗一1 ) 定理s z 。对于圈c 。，来说，。c ，2 二：完孚萋： 证明：对于任意s c ( g ) ，设is = ，记e s 的0 9 个连通分支为 u ，k l = 1 ，z ，缈) a 若月为偶数 ( 1 ) 如果，i n ，贝| j 邢。删r 且对于任意f l 2 ，州彬( g 驯l 孚j 从而 2 m 。a x c 一【孚p 叱 l ，l ，j ( 2 ) 如果，三，则国( c 。一s ) 蔓n r 且对于任意f “，2 ，脚 ，i y ( g t ) i l 从而 b ( c 。) 2 m 。a x ( n r 一，一1 ) 2 1 一s ，e n b 若疗为奇数 ( 1 ) 如果，t n - 1 姒c - s ) - 2 a - r - 1 由于a ( k 。) = 1 ，t c ( k h ) ；1 ；a ( k l ，1 ) = n 一1 ，彭( k i h ) = 1 代入即证其上 界星图取得：下界在完全图取得一 推论3 3 2 设g 是n 阶连通图，则1 一n l ，f 1 ，记k = g ，设v ( k ，) = “，叱，“。 ，v ( k ，) = v 。，v ：，v 令 显然有 f = s u ( 虬，v ) ， 。，v ：) ，o 。，v ，一，) u ( “，v ，) ， ：，v ，) ，诎。，v ，) s 。i = 1 s + j + ，一2 ，烈k 。，k 。一s ) = 烈瓦，k n s ) + l ， m ( k 。x k 。一s ) m ( k 。k 。一s ) 下面讨论l s i 和m ( k x k s ) ：我们用记号b ，y 】表示整数z ，( x sz 蔓y ) 由于c 。是如一s 的一连通分支，故有s 2 n ，s 】p + l ， 卜，b + l ，m 】d ，】 又因 从而有 于是有 s 1 s ( n f ) + ( m s ) t = s ( n2 + n 3 + + r t m ) + ( m 2 + m 3 + + 埘。) f 2 5 ( 国一1 ) 十( 一1 ) f = ( c o 一1 ) ( 5 + f ) m ( k ：蟛一s ) - i c f | _ s t s + f 一2 s + t - 2 0 2 ， s i + ，玎( k 。k 。一s ) 珊( k 。k 。一s ) ( s + t 一2 ) s l + r e ( o - s ) 1 ) ，则以以一s 必有另一分 支q 为k ，k 。，( n ， 1 ) ，否则+ i 2 ，小t = m ”= 羔；n ，= 为7 方便令肌t = s ，”t2 t ， 设y ( c 。) = 如，v 。) ，辑，v 。) ，( 甜，v 。) i y ( c ，) = 缸b ， 1 ) ， 。，v ：) ，u b , v , ) j ， 其中“6 仨缸，“：，虬) ，k 硅 v ，v ：，v 。 取s = s u ( “，v 。) ) u ( “。，_ ) 一 ( “，u ) ) ， 于是 拶i = 1 s i + 1 ，顶如k f ) s ，心巧一s ) ，埘( k k f ) = ( k 髟一s ) + 1 从而有甜( k 吃一s 。) 一l 刚一m ( k e - s ) m ( 巧k 一妒j s i 叫如k 一| s ) 即s 也为k m x k 的6 一集且叫kx k - s ) = 烈k x e 一回+ l ，这与s 的取法 矛盾故有若仇= l 必m 。= 1 d 西北工业大学硕士学位毕业论文第三章目的相对粘连度 综上讨论有k 。k 。一s 的所有分支g 型为k k ( n 。1 ) ，从而iv ( c ，) 卜月， c o ( k ，k s ) = m , i s l = m n 一：_ 7 7 一只”，( k 。k 。 故有 占c k 。k 。，= m + ”一，”一f 景 定理34 3 对于任意正整数n t ( i = 1 , 2 ，c ) ，有 。( ，：，乞，只。) 2 ! ；，。，姜瓣 出h 证明：因为若图g 包含一条h a m i l t o n 路，则g x 只也含一条h a m i l t o n 路， 所以只只：只。必含一条h a m i l t o n 路只m ， ， 由定理3 4 1 有： 6 ( 丘气) 6 ( 只西j 。) f0 ，? l i ( f _ 1 , 2 ，七) 全为奇数 一1 1 ，吩( f = 1 ，2 ，七) 至少有一偶数 又因为若g 和h 是二部图，且其二部划分分别为乜，b l 【c ，d 】，则g x h 是 以 ( a x c ) , o ( b x d ) ，( a x d ) u ( 口c ) 】为二部划分的二部图，所以 f x 生坠二生! 坚垒二：坐! ， 一( f = l ，2 ，) 全为奇数， 喊。 k 二二州川，2 至少有一偶“ 由定理3 4 1 有 m p - 驴怫拦嚣蔷莩写翥 从而对于任意正整数n i ( f _ 1 2 ，k ) 有 p 。p 。y p 、j 0 ，仇全为奇数， 鹕。丘”“墨) 2 1 一i ，。主少有一偶数 推论3 4 4 对于n 维立方体q ( n ) 来说，有 一2 5 西北工业大学硕士学位毕业论文第三章圉的相对粘连度 b ( q m ) = 6 ( p 2 只尸2 ) = 一1 定理345 设g 和g ：分别是h ，和h ：阶的非平凡的连通图，则其联图 g ，+ g 2 的相对粘连度为 b ( g ，+ g2 ) = m a x 弘( g ，) 一 2 ，b ( g2 ) 一胛1 ) 证明：i ) 当g 和g ，都是完全图时，由于b ( k 。) = 1 一n ，结论显然成立 i i ) 当g 和g ：都不是完全图时，设s 是g ，的b 一集，则 6 ( g i ) = 畎g f s i ) 一i s ij - m ( g , 一s ) = 以g + g ：一( su g ( o ：) ) ) - i s ，u 以g 2 1 + p ( g 2 一坝g l + g 2 一( s lk 3 v ( g 2 ) ) ) 兰6 ( q + g ) + 啦 即b ( g l 十g 2 ) b ( g 1 ) 一n 2 ； 同理b ( g 1 + g 2 ) b ( g 2 ) 一疗i 故 b ( g l + g 2 ) _ m a x b ( g 1 ) 一”2 ，b ( g 2 ) 一n i 另一方面，设s 是g ，+ g ：的b 一集，由g ，+ g