（应用数学专业论文）韧性度理论及其在交通运输网络中的应用.pdf

摘要 对于网络系统，要考虑的一个基本问题是系统的牢靠性，要使网络构造得尽 可能稳定，不仅与最初的损坏有关，还与损坏后重构的难易程度有关为了描述网 络系统的连通性，人们提出了许多参数，如点连通度和边连通度但这两个参数存 在者不足t 因为它们没有涉及到去掉点或边后网络圈遗留下来的分支+ 为了克服这 个不足，1 9 7 3 年c h v a t a 引入了圈的坚韧度，1 9 8 7 年b a r e f o o t 等提出了整度，1 9 9 4 年许进提出了核度但这些参数没有考虑到网络围遗留下来的最大的分支，于是， 9 9 5 年c o z z e n s 提出了韧性度，1 9 9 5 年p i a z z a 等提出了边韧盹度，这些参数的g 入进一步深刻地从整体e 刻画了网络图的连通性 本文针对韧性度的理论及其在交通运输网络中的应用问题进行了研究，其 i 耍内容为： 1 介绍了韧性度和边韧性度的一些基本理论，如：完全图，星图，完全图的 积和径，h a r a r y 图的韧性度和边韧性度，韧性度和边韧性度的取值范围等： 2 求解一类特殊图的边韧性度； 3 综述了交通运输网络中交叉路口的基本知识； 4 将韧性度的优化设计理论运用于交通运输网络 关键词：韧性度；边韧性度：道路交叉口 t h et h e o r yo f t e n a c i t yw i t ha p p l i c a t i o nt ot r a f f i cn e t w o r k a b s t r a c t t h es t a b i l i t yo fan e t w o r kc o m p o s e do fn o d e sa n dl i n k si so f m ei m p o r t a n c et o n e t w o r kd e s i g n e r s t h u s ，i ti sd e s i r a b l et h a tn e t w o r k sb ec o n s t r u c t e dt ob ea ss t a b l ea s p o s s i b l e ，n o to n l yw i t hr e s p e c tt ot h ei n i t i a ld i s r u p t i o n ，b u ta l s ow i t hr e s p e c tt ot h e p o s s i b l er e c o n f i g u r a t i o no ft h en e t w o r ka f t e rd i s r u p t i o n m a n yg t a p ht h e o r e t i c a l p a r a m e t e r sh a v eb e e n u s e dt od e s c r i b et h e s t a b i l i t yo fn e t w o r k ，s u c ha si n t e g n t y ， t o u g h n e s s ，c o d t y ，b u tt h e yd o n tt a k ei n t o a c c o u n tw h a tr e m a i n sa f t e r g r a p hi s d i s c o n n e c t e d i n1 9 9 5 ，t e n a c i t yw a si n t r o d u c e db yc o z z e nt oc o p ew i t ht h i sd i f f i c u l t y t h i sp a p e rs t u d i e st h et h e o r yo ft e n a c i t ya n di t sa p p l i c a t i o nt ot r a f f i cn e t w o r k t h e m a i nc o n t e n t sa n dr e s u l t sa r es sf o l l o w s ： 1 s t u d ya n do b t a i ns o m es p e c i a lt h e o r yo ft e n a c i t ys u c h8 sc o m p l e t eg r a p h s t a r g r a p h ，c o m p l e t eb i p a r t i t eg r a p h ，g n d sa n dt o r lo fc o m p l e t eg r a p h ，t h er a n g eo fv a l u eo f l h et e n a c i t y ，t h es t p a c t u r e so ft h et e n a c i t ya n dn e t w o r kg r a p h 2 d i s c u s st h et e n a c i t yo fac e r t a i nk i n do fg r a p h 3 i n t r o d u c e st h eb a s i ck n o w l e d g en fi n t e r s e c t i o ni nt r a f f i cn e t w o r k 4 a n a l y z ea n ds t u d yt h et r a f f i cn e t w o r ks y s t e mb yu s i n gt h eo p t i m a lt h e o r yo ft h e t e n a c i t y + k e yw o r d s ：t e n a c i t y ；e d g e - t e n a e l t y ；i n t e r s e c t i o n v 大连海事大学学位论文原创性声明和使用授权说明 原刨性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成博士，硕士学位论文= = 翅世廑堡监厘基垄变通垂箍圈缝主鲍廑晨! ：。除论文 中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均己在文 中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公 发表或未公丌发表的成果。 本声明的法律责任由本人承担。 论文作者签名：年月 同 学位论文版权使用授权书 本学位论文作者及指导教师宛全了解“大连海事犬学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位 论文的复印件和电子版，允许论文被查阅和借润。本人授权大连海事大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，也司采用影印、缩印或 扫描等复制手段保存和汇编学位论文。 保密口，在年解密压适用率授权书。 本学位论文属予；保密口 不保密口( 请在以上方框内打“”) 论文作者签名；导师签名： 周期：l 卅6 年；月 1 1 1 辩 参引 引言 l ，研究背景及意义 仔细观察和思考现实世界中所存在的系统，无论是在自然界还是现实生活中， 绎常会遇到涉及某些研究对象之间具有特定关系的问题如一个浏家或地医内， 城市之间是否存在交通线、通讯线；球赛中，两个球队之削是否比赛过等等这些 关系是对称的，即对象甲对对象乙有某种关系，也意味着对象乙对对象甲有这种 芙系，对象之间的关系可以用一个图形来描述用点来表示对象，若对象甲和对象 乙之间有所研究的关系，那么就在代表对象甲和乙的两个点之间连一条线因为我 们感兴趣的是对象之间是否有某种特定关系，所以，两点之间有无连线是重要的， 而连线的长短曲点则是无关紧要的这些网络系统对象之间的关系用图描述，用图 抽象成模型后，便可以运用图论的知识解决其中有关人们感兴趣的问题因而图论 的研究非常有意义，其用途也非常广泛，可以毫不夸张地薛，图论几乎可以用于 人类社会的各个角落特别是近代计算机的出现和发展，使得犬规模问题的求解成 为可能，图论及其应用的研究得到了飞速发展，更显示了它的巨大威力图论的虚 用己渗透于系统工程，建筑：【程，通信工程运筹学，电路网络，计算机科学鼓 经济学社会学，心理学等各个领域，井使这磐领域的研究取得了巨大的甚至革 命性的突破 对网络系统，要考虑的+ 个基本问题是系统的牢靠性，即系统在发生某些损 坏的情况下仍能正常工作的性能对网络系统牢靠性的研究通常归结为它的删络 拓扑图的连通性的研究 设x 是一个系统，其主要元素为，z 2 ，如果t 与x ，之问有关系且为相互 的，就用j 。z 表示由此，可构造一个无向网络图g ，其顶点集合为矿( g ) ，边集为 e ( g ) 一 x , x ，i 其中x 与x 在j 中有关系) 这里与x 有关系是广义的概念，可能 是互相认识，也可能是两零件x ，与z 相互连接等，应根据x 的性质而定这样，我 们便称无向网络图g 为系统x 的网络图 设g 一，e ) 表示无环，无重边的简单图其中v 表示顶点集合。e 为g 的边 集合，设s 为边集合或点集合的一个子集，g s 表示从g 中移去s 集合中的边或 点毗后所得到的图如果g s 不连通， i ( g s ) 来表示g s 最大分支的顶点数 1sl 表示移去的点或边的个数 则我们称5 为g 的个边或点割集j 【 ；| 用( g s ) 来表示g s 连通分支数；用 删络图的连通性与构成它的点和边有关当网络失去某些点或边以后，将损害 它的有效性要使网络构造得尽可能稳定，不仅与最初的损坏有关，还与损坏后飘 构的难易程度有关为了描述网络系统的连通性，人们提出了许多参数，如点连通 度和边连通度但这两个参数存在着a ；足，因为它们没有涉及到去掉点或边后网络 图遗留_ 卜来的分支为了克服这个不足， 9 7 3 年c h v a t a ”引入了图的坚韧度，1 9 8 7 年b a r e f o o t l 2 】等提出了整度，1 9 9 4 年许进 3 1 提出了核度但这些参数没有考虑到网 络图遗留下来的最大的分支，于是，1 9 9 5 年c o z z c n s l 4 提出了韧性度，1 9 9 5 年 p i a z z a 5 1 等提出了边韧性度，这些参数的引入进一步深刻地从整体上刻画了网络圈 的连通性这些参数涉及到两个根本性的问题( 1 ) 网络图在失去r 某些点或边后的 连通性? ( 2 ) 重构网络使之连通的困难程度有多大? 各种参数的定义如下： 连通度或边连通度： k ( g ) 一m 血 i si ：s 为g 的点割集，x ( c ) zr a i n isi ：s ：0 6 的边割集 举韧度或边坚韧度：f ( g ) 。m i n t s l , u ( g - s ) ：s 为g 的点割集 r ( 6 ) 一m i n _ | s t o j ( g s ) ：s 为g 的边割集 核度：h ( g ) - m a x 伽( g s ) 一i s l ：s 为g 的点割集) 点整度或边整度：，( g ) t r a i n i s i + f ( g s ) ：s 矿( g ) 韧性度或边韧性度：f ( g ) 一m i n l ! ：i ；! 象墅：s y ( g ) 焖州n 堕嚣骞：s 鲫g ) )甜l u j 在峰韧度或核度中，对“进攻者”来说，毁坏s 的“代价”是s 的大小得 到的“成果”是破坏s 后遗莳f 柬的分支( 嗣为产生较多的分支将难于重构一个网 络图) 在韧性度中，“代价”也考虑到最大的遗留分支，因为较大的遗留分支意咪 2 着“进攻者”不太成功整度不考虑“成果”，“进攻者”希望代价与成果的比率尽 町能小，而网络设计者希望最小比率值尽可能大 关于连通度和边连通度1 6 - 1 3 1 ，坚韧度和边坚韧度 1 4 - 3 1 j ，核度o n t ，挞度和边 整度( 4 l 。1 等参数问题的研究目前仍吸引了大批的学者从事这方面的工作 白从c o z z e n s 、p i a z z a 等提出了韧性度和边韧性度以来，理论上得到了迅猛的 拉展这种发展的个重要原因在于，韧性度不仅考虑了网络图遗留下来的分支， 也考虑到了网络图遗留下来的最大分支这样韧性度较其它参数而言，更能深刻地 枞整体上揭示网络系统的牢靠性能在韧性度的研究上，c o z z e n s ，c h o u d u m 等工 作最为出色c o z z e n s i 靼等得到了h a r a r y 图的韧性度c h o u d u m1 5 9 1 等求出了完全图 的积和径的韧性度，并刻划了在网络图顶点数和韧性度给定的条件下，网络所具 有的最大边数在边韧性度的研究上，p i a z z a t “1 等还得到了边韧性度的一个较低的 f 界作者对韧性度和边韧性度的理论及应用作了进h 步的研究 道路与道路相交的部分称为道路交叉口，道路交叉| ：_ 】足人流车流集散的地 方，可视为一个小中心点道路的运输效率通行能力，行车安全，车速及运营费 用很大程度上取决于交叉口的正确规划和良好设计，但由于经济的快速发展，蹿 硎规划和建设的不合理和不完善，伴随着车流量的增加等原因，往往造成道路交 叉口在使用过程中不能满足需要，进而涉及到改造设计问题，改造的合理与雨直 接影响道路的使用”本文将应用韧性度理论对改造之后的交叉口是甭优化，可靠 进行了研究 2 主要研究内容 本文针对韧性度的理论及其在交通运输网络中的应用问题进行了研究，得到 了一些研究成果，具体包括如下内容： ( 1 ) 介绍了韧性度和边韧性度的一些基本理论，如：完全圈，星圈，完全图的积和 径h a r a r y 图的韧性度和边韧性度，韧性度和边韧性度的取值范围等； ( 2 ) 求解一类特殊豳的边韧性度； ( 3 ) 综述了交通运输网络中交叉路口的摹本知识 6 2 “】； ( 4 ) 将韧性度的优化设计理论运用1 j 交通运输网络”“ 3 基本概念和记号 3 设g - ，) 是一个图，若e - 缸，v 是圈g 的条边，则称“和v 是相邻的，边 e 和点“，v 相邻接，n 和v 称为边e 的端点点y 的顶点度数d ( v ) 定义为：与点v 相邻 的所有点的个数通常把具有p 个顶点的图g 称为p 阶图一个圈称为连通的，如 果对于g 中任意一对顶点m ，v ，在g 中存在u v 路为了清楚和方便，下面列出本 文所出现的基本概念，记号等 若k ( c ) 女，则称g 为k 点连通度： 若f ( g ) ，则称g 为女点举韧度； 若r ( g 1 t ，则称g 为k 点韧性度： 若h ( g ) ，则称g 为k 点核度； 若l ( c 1 k ，则称( ；为k 点整度； 图g 的顶点最小度数：6 ( g ) 一m m 仁( v ) ：v g ； 星图：记作置。它是一种特殊的完全二部图，其中第一个独立集仅有一个 顶点，第二个独立集有p 一1o 2 ) 个顶点： 完全图：记作k 。( p 个顶点) ，任两个顶点皆相邻的图； 完全二部图：已作k 。，它的顶点集出2 个两两甄不相交的子集，k ( 均菲空， = 2 ) 构成，这罩l k i - t n ，i 匕i ， ，每个都是k 。的独立集，若对 “，r 矿( k ) ，如果“，v 不同属于某一个，则必相邻； 图的笛卡尔积：记作g 。x g ：g ，它有顶点集7 ( 6 ，) y ( g ：) y ( g ，) ， 两个顶点“一( 自，g 苫，) ，v 一。，h 2 ” ，) 相邻当且仅当只对一个j ，g 。_ 札j ( g ，h ，) 为g 中的一条边： 生成子图：给定图g i 缈，e ) ，若矿s 矿，e _ 缸v e “，v y 。 ，则稚g ；。，e ) 是g 中出矿1 生成的子图 4 第1 章网络图韧性度的基本理论 1 1 几类特殊圈的韧性度及韧性度的取值范围 s 矿( g ) ，s 的痕记作：s e ( s ) - 卧s i + r ( g s ) 】【( g s ) 】s o ( s ) = 丁( g ) ， s 被称作g 的t 一集c o z z e n s 等在 4 中得到了几类特殊图的韧性度及韧性度的取 值范围： 命题1 1 4 如g 是的生成于图，则r ( g ) st ( h ) 命题12 【4 1 对任何图gr r ( g ) z 点等等 a ( g ) 是g 的诎立数 命题1 _ 3 【4 1 如g 不是完全图，则7 1 ( g ) s 掣 命题1 。4 ”1 g 是p 阶连通图，则j 鸶5 r ( g ) p - 证明因为1s 口( g ) 5 p k ( g ) 2 1 ，所以结论成立 命题15 d 1 如小in ，则r 弧。) 。必 定理1 1 州对任何圈g ，r ( g ) 2 “g ) + i 高。 定理12 设g 是一个有p 个顶点的非平凡，非完全的图，v 为任意个顶 点，则7 1 ( g v ) r ( g ) 一； 定理1 3 4 1 如果g 是个= 部r f 则，r 一连通p 个顶点的圈，则 r ( g ) 。出 证明从 6 6 可得出f ( g ) 1 ，这样由定理l + l 知r ( g ) z 1 + = 面1 - 容易推出 口( g ) 。罢，这样r ( g ) 啦设s 是一部分集的一个那么，因为g 是卜一正则的， z口 所以i s i - 詈rr ( a - s ) - 1 一m ( g - s ) 詈因此r ( g ) - 旦 这个结果给出了许多有趣的推论： 推论1 1 4 1 如果g 。是个二部、h 一正则、_ 一连通a 个顶点的圈，g ，是 个二部、m 一正则、m 一连通p ：个顶点图，贝u r ( g ，g ：) 。旦业 p l p 2 推论1 2 ”1 对任意整数n ，丁( q 。) 一兰笋 推论13 川对任何偶数n 、m ，丁( c x c ) ：竺盟 n m 推论14 对任何偶整数n ，r ( c 。x k 2 ) 。! 型 月 下面将获得一些图的积的韧性度的界，第个不等式是定理1 1 的一个推论 定理1 4 m 如果nz m ，则m ；+ m j n i - 2 m + 2s r 僻。咒) s ：二刿m z ，” 定理15 4 1 设 g 。g ，+ g 2 ( i y ( g ) | _ p ，l v ( c f ) 卜_ p i , a ( c 。) - 嘶，t ( g 。) - r 。，g l _ k 。i - 1 ，2 ) ，如 叩那么m i n 堕，堕1 + 1 r ( g ) 尘旦+ 三 、p 1p 2 ，“2“2o f 2 利用完全- 2 部图的韧性度，c h o u d u m 得到了路和径的韧i t 度： f l 、n 为奇数 定理1 6 ”1 对任何整数n 如2 2 ) 7 ( 只) 旦生，n 为偶数 【“ 定理l7 对任何非负整数t i , ”- h 。， f l n ，为奇数 r ( ，。只z ”。只) 。 生坠：生! ! ，一些珥为偶数 6 1 2 韧性度与网络图的结构 本节将讨论简单韧性度与一些简单类型圈的结构关系通过这些关系，j i 侗 看到用韧性度可以刻划网络图的基本结构，而且也为进一步探讨韧性度与网络图 的结构打下基础 定理1 8 6 7 1 设g 是p 阶连通图( p22 ) ，则r ( g ) 一p 当且仪当g 磐完全图 岸。- 证明必要性 由命题1 3 知r ( g ) s 旦二堑丝， 、。 a ( g 、 从而( g ) 5 1 又对任何连通图g ，均有n ( g ) z 1 ， 故a ( g ) 一1 ， 从而g 望k 。 充分性显然 定理19 设g 是p0 3 ) 阶连通圈，r ) - ，当且仪当g 氅星圈 p 一1 k 1p l 证明必要性 出命题1 2 与命题1 3 知生! 三s ls 旦二旦妲! ! ! o ( “)p 一1“( ( ? ) 由此解得口( g ) - p - 1 ，k ( g ) t 1 ，所以g 塑k 充分性显然 定理1 1 0 呻7 设g l 黾p ( p 4 ) 阶连通图，则7 ( g ) 。主j ，当且仅当g 足出 k ，上添加一条边，或者剖分k ，m 上一条边所得的图 证明必要性 设s 是g 的r 一集，肄l 7 型! ! 堕= 旦。土 ( g s ) p 一2 。r 阿一s ) 1 ，f s i + ( g s ) 5 p o 一2 ) l s i - 知( g s ) - ( p 一2 ) r ( a s ) 3 ( p l s i 一( p 一2 ) ) i s 忙2 - + i s i - 1 或i s l - 2 如i s i 一1 ，则3 甜( g s ) 一( p 一2 ) 0 + z ( g s ) ) c 乳跏攀山等小等咄壶 f ( g s ) 一1 ，3 ( o s ) z2 如；f ( g s ) - 1 ，则甜( g s ) 一p l 与3 0 d ( g s ) * ( p 一2 ) ( 1 + r ( g s ) ) 矛盾 r ( g s ) - 2 ，( g s ) a p 一2 如i s l - 2 ，则3 m ( g s ) t 扣一2 ) ( 2 + r ( g s ) ) l s 。( g s ) 。3 , o t g - s 燮一2 ：! ! 幽2 ；1 p zp z r ( g s ) - l0 4 6 一s ) 一p 一2 出g 的连通性，g 必由k ，上舔加条边，或者剖分k b 。中的一边( 所谓 剖分圈的一条边e ，是指对e 中间添加个新的顶点，如边e 一“p ，给e 上增加点w 使p 变成两条边) 如图卜1 容易看到，有且只有这两种情况 ( 卜oo o o “v“wv f “v 已i = “wq = w v 幽11 剖分幽的边 充分性，显然 定理11 1 ”1 设g 是p 仁4 ) 阶连通图，圈g 的顶点最巾度数6 ( g ) ，p 一2 ， 则r ( g ) - 掣 证明充分性设6 ( a ) - p 一2 ，则g 中任意两个不楣邻的顶点必与其余顶点 相邻这样r 任意p 一3 个顶点都不可能构成g 的点割集，于是有k ( g ) t p 一2 ，议 v s c ( g ) 则有i s 忙k ( a ) p 一2 ，于是有：m ( g s ) s p i s b2 ， 创! ! 堕= 盟：旦= ! ! ! 。型 ( g s ) 22 r ( g ) z 掣 记v 是g 中度数最小的一个顶点，r ( v 1 是它的邻域，则 u ( g r p ) ) - 2 ，r ( v ) l 6 ( 6 ) - p 一2 ，f ( g r 扣) ) - 1 ，故有 丁( g 、；! ! q ! i ! ! f g ：! ! ! ! ! 。旦蔓 、 ( g r ( v ) ) 2 嚏22 最小度数为4 的8 阶鬻 r ( g ) = _ p - i 反过来不成立，如图 2 2 “，p t8 ，dt 4 r ( 以b ) 一；- t p - 1 ，但d 一4 一p _ 2 9 定理11 2 设g 是p ( p 7 ) 阶连通圈，则r ( g ) ；。一，当且仅当g 是由 口一j k t , p - t 上添加二_ ：= 条边( 此两边端点不共点) 或剖分k 1 p - 3t 二条边所得的图 证明必要性 设s 是g 的r 一集，则 所以 如l s i 一2 1 1 j ! ! 蜓二里，王 ( g s ) p 一3 s i + ( g s ) s p ，r ( a s ) 1 ( i s i + r ( g s ) ) ( p 一3 ) 3 ( p i s i ) ( p 一3 ) ( 1 s i + 1 ) s3 ( p - i sd s b2 + 苎，1 s t 。1 ，或1 5 i 。2 p 肌( c - s ) - 等孚也等小南m 毒 p一，p一3p 一，口一j r ( g s ) - 1 与( g s ) 一p 一3 矛盾 锄l s i - l ，则f ( g s ) 。掣小塑半_ 1 _ 兰。2 + 三s 3 p jp一)pjp j 如r ( g s ) 3 ，则与甜( g s ) q 二掣矛盾 j 女口r ( g s ) - 2 ，月0c o ( a s ) p 一3 如( g 咽| 1 瞄m ( g 删- p - 1 与觜t 三p - 3 矛盾 所以t ( g s ) - 2 ，( g s ) p 一3 故g 必由k ，。上添加二条边，或剖分置。伊，中的一条边所得 充分性显然 第2 章边韧性度的基本理论 2 ，1 引言 g 的边一韧性度( e d g e - t e n a c i t y ) ，这个概念是p i a z z a 等人提出来的，提出这 个概念的目的是为了研究网络图的稳定性记作： r ( g ) t m i n s c 怛) jse 三( g ) ) 其中5 c 口) 一坚辫称作s 的痕：( g - s ) 表示g s 中连通分支的个数 r f g s ) 表示g s 中最大的一个分支的顶点数 图的边一连通性的稳定性的最基本的测量是边连通度( t h e e d g e - c o n n e c t i v i t y ) ，而边一连通度在测量图的边一连通性上存在着严重的不足，因 为它没有考虑到去掉边以后网络图遗留下来的分支为了克服这个不足，p i a z z a 等 人提出了边一韧性度( e d g e - t e n a c i t y ) 的概念边一韧性度不仅考虑了去掉边以后网络 翻造留f 来的分支，也考虑了遗留下来的最大分支，因为最大的遗留分支意味着 “进攻者”不太成功， 如果r ( g ) 一s c ( s ) ，s e ( o ) ，就把s 称作r 集合：如果r ( g ) 一s c 忸( g ) ) 就 把g 称为边韧性度图；如果e ( v ) 是满足t ( g ) 一s c ( e ( g ) ) 中的难集合，就把g 称 勾严格边一韧性度图g 的边一连通度，记作a - ( g ) ，用m 和r 分别代表( l i ( g s ) ， z ( g s ) ；用p ，q 分别代表顶点数和边数 下面给出边韧性度的取值范围： 定理2 1 设g 是连通图且s e ，则s e ( s ) 1 且等号成立当且仅当g 是一 棵树且s - 推论21 如果g 是连通的，那么丁。( g ) 1 且等号成立当且仅当g 足一棵树， 定理2 2 t 5 1 如g 是h 的支撑予图，则t 1 ( g ) s t ( h ) 定理23 对任何图g ，t ( g ) z ( 阍+ ( 1 p ) 定理24 1 5 对任何图g ，t ( g ) 5 ( q + 1 ) 加 定理24 对任何图g ，t ( g ) s ( q + 1 ) 肪 第2 章边韧性度的基本理论 21 引言 g 的边一韧性度( e d g e t e n a c i t y ) ，这个概念是p i a z z a 等人提出来的，提出这 个概念的目的是为了研究网络圈的稳定性记佧： 了1 ( g ) 1 m i n s c ( s ) i s 压( g ) 其中s c ( s ) 坐辫称作s 的痕：哪哆一s ) 表示g s 中连通分支的个数 r ( g s ) 表示g s 中最大的一个分支的顶点数 圈的边一连通性的稳定性的最基本的测量是边一连通度( t h e e d g e c o n n e c t i v i t y ) ，而边一连通度在测量图的边一连通性上存在着严重的不足，因 为它没有考虑到去掉边以后网络图遗留下来的分支为了克服这个不足，p i a z z a 等 人提出了边一韧性度( e d g e - t e n a c i t y ) 的概念边一韧性度1 i 仅考虑了去掉边以后网络 圈遗留下来的分支，也考虑了遗髑下束的最大分支，因为最大的遗留分支意味着 “进攻者”不太成功 如果丁( g ) ts c ( s ) ，s e ( g ) ，就把s 称作r 。集合：如果r 1 ( g ) - s c ( 辱( g ) ) 就 把g 称为边韧性度图；如果e ( g ) 是满足r 。( g ) 一s c ( e ( a ) ) 中的唯一集台，就把g 称 勾严格边一韧性度图g 的边一连通度，记作 - ( g ) ，用甜和r 分别代表珊( g s ) ， f ( g s ) ；用p ，q 分别代表顶点数和边数 下面给出边韧性度的取值范嗣： 定理21 设g 是连通图且s e ，则s c ( s ) 1 且等号成立当且仅肖g 是一 棵树且s - e 推论2 1 如果g 是连通的，那么r y g ) 1 且等号成立当且仅当g 是+ 棵树 定理2 2 1 5 1 如g 是h 的一支撑子圈，则t 。( g ) 丁i h ) 定理2 3 对任何图g ，( g ) 2 ( a 2 ) + ( 1 p ) 定理24 1 5 对任何图g ，t ( g ) i ( q + 1 ) p 定理25 如g 是一边韧性度图且g c d ( p ，q + 1 ) 一1 ，则g 是严格边韧性度圈 下面的定理给出了对e 中任何两集之阊的瘫的一个关系这个结果给了一个 判别哪些集为r 集的一个工具 定理2 6 5 1 设s 和s 是e 中子集，使得i s | - i s i - d ，( g s + ) 一( g s ) 一b ， t ( g s 。) 一f ( g s ) 一一c ，那么t s c 岱。) ts c ( s ) 当且仅当【0 一c ) l b l s o ( s ) ； s c ( s ) 一s c ( s ) 当且仅当【0 一c ) t b 】 5 c p ) ； s c ( s 卜s c ( s ) 当且仅当一c ) 肛】) s c ( s ) 推论2 2 如s 是一个r l 集且c 是g s 中的一一个非平凡分支，则 ( c ) t ( g ) 推论23 如s 是一连通图的r 。一集，那么g s 不舍任何桥 推论24 如s 是一连通的r 一集，g 为非平凡图，g s 有一最大阶的唯一的 分支，那么c 是3 一边连通的 推论25 如存在一连通图g 的r 。一集s ，r ( g s ) 一3 ，那么g s 含至少三个 彤如k ，的分支 推论26 如存在一连通图g 的r 一集s ，t ( g s ) 一4 ，那么g s 含至少二个 平凡分支 定理27 f 5 1 如s 是一连通图g 的丁1 一集，p29 ，甜( g s ) 。pr 则 r ( g ) j ( x z ) + 【3 t s , 一6 】 2 2 边韧性度图 本节给出些边韧性度图没有特别说明，下面所有的图都是连通的下面两 个定理给出了非边韧性度圈的最小下界这些结果是最好的 定理28 ( ”如一连通图g 的阶最多是1 0 ，那么g 是边韧性度圈进步如g 的阶最多是9 ，则g 是严格边韧性度图 定理2 8 是最好的结果，因为圈g ( 民，5 ) ，g ( b ，4 ) ，c ( k ，一日，4 ) ，g ( r 。，3 ) ， g ( k 。一e , 3 ) 是阶为1 1 的非边韧性度图( 事实上这些图是阶为1 l 的仅有的一些非韧 性度图) 定理2 9 如一连通图g 的大小至多为】7 ，那么g 是边韧性度图 这个结果是最好的，因为图g ( 2 k 。，5 ) ，g ( k ，8 ) 为q 一1 8 的非边韧性度图( 事 实上这砦图是阶为1 8 的仅有的非边韧性度图) 下面的两个引理和定理指出如个图是足够稀疏，那么它定为边韧性度图， 定理的结果是最好的 引理2 1 ”如g 是一q p + 1 的连通图，s l e 是g 中的一个桥 ，那么由 g s 的非平凡分支导出的子倒有下面的一些形式： ( i ) 两个不相交圈的并 ( i i ) 两个圈，它们的交是一顶点 ( i i i ) 两个圈，它们的交是一个路 引理2 2 如果g 是一连通图且q p + 1 ，那么g 中没有任何予图足3 一边连 通的 定理2 1 0 5 1 如g 是45 p + 1 的连通图，那么g 是严格边韧性度图 上面的结果是最好的，因为图g ( 3 k ，m ) ，巩2 1 0 ，qs p + 2 为非边韧性度图 叉g ( 3 k ，9 ) 是边韧性度图，但不是严格边韧性度图， 现在证明所有的h - j f 则，一边连通图是边韧性度刚 定理21 妒1 如g 是r 一币则且r 一边连通的，那么g 是严格边韧性度图 由定理2 1 1 知，在运输、交流网络设计中许多高可靠度旮勺阚络图是边韧性度 圈 推论27 完全图膏，和完全n 一部图k 。，o m n ) 是严格边韧性度图 推论28p 一圈的n 个乘方c ：是严格边韧性度图( 1 sn5 f p 2 1 ) 推论29 如g ，是l 一正剡、一边连通的o t l 2 ，”) ，那么g ，g ：g ，； 恳严格边韧性度图 推论2 1 0n 一立方体是严格边韧性度图 推论2 - 1 1 如g 是，- 正则、r 一边连通膨胀圈，那么g 足严格边韧性度图 定理2 1 2 吲k 。枷n ) 是严格边韧性度图 下面将定理2 1 1 中的，一边连通、，正则的条件减弱，得到一些有用的结果 首先定义个图f ( r ，m ，n ) p 2 , 1 s ( r 2 ) ，m t2 ) 如下： 矿( r ，m ，n ) ) 。u k ，e ( f ( r ，m ，”) ) 一u ( 四。一m 。) u c + m m 女- l 女- 】 f - l k - 忆i o s f s r 吼。扣。v 。ios ；cjsr ， m 。扣v 。10s i n 一1 j tc 。一p k ， 0 s is 月一i i ， l l s m 七的所有的运算都是在m 州伽，的意义f 进行的，设g 。= ( k ) ，图f ( r , m , n ) 是 从? 个k ，+ t 中构造而来；通过从薄个完全图中删去h 个边，得出u g 。，然后增 加n 个边连接着在g 。和q + 中降低度数的顶点结果得到的是一个r 一正则、 一2 ，l 的图 定理2 1 3 5 1 对，2 ，1 s nsr 2 ，t n 2 ， t 。怛( r ，m ， ) ) ； 。+ 型，。二。，堡立! 型 ”i “j “。( r + 1 x r - z , z ) i + 而1 ，舵 j 芏| 21 f ( r ，| ，n ) 1 4 从定理2 1 1 可看到，如一个图的边连通度的条件减弱，那么这个图可不必为 边韧性度圈例如，由定理7 1 3 知： f ( r ，m ，n ) t r23 ，n 【2 r ( r + 2 ) 】【( r + 1 ) ( ，一2 h ) 】为r 一正则，a * 西t ：弗边韧性度图因为任何f 则图的边连通度是偶数，所以，为奇数、n - p w z ，为偶数、n 一【( ，一2 ) 2 】，这些情况提供了非边韧性度i f f j 、蛾大可能的边连通度 的图的例子 定理2 1 4 如，为奇数，那么存在，一正则、f r 一1 1 一边连通度、非边韧性度 陧；如r 为偶数，那么存在r j 棚4 、( r 一2 卜边连通度、非边韧性度图 定理21 5 5 1 列任何正有理数a b ，a b ，存在一个罔g 使得r ( g ) 一a b f 面，将去掉定理2 1 l 中的，一正则，r 2 的条件，但保留 ( g ) - r 的条件 在这个条件下，每个顶点的度数至少为r 给定 ；，22 的图，考虑 ：，d 一p r + s ，d l 是顶点u 的度数定义。为使a - r ，：，d 。s + f 是边韧性 度图的最大的对 一1 可定义相类似的概念在这种情况下，对 - 1 的固定的 阔，考虑：，d - 2 ( p 一1 ) + s - 定义q 为使a 一1 ，：，d 。2 ( p 一1 ) + s 是边韧性艘 图的最大的s 下面对和，的界证明几个结果 定理21 6 ，一4 定理217 ”3 设g 是a2r 和：d ，- p ，+ 的连通圈，如 t4 ( p + 3 ) ( p 一6 ) l 那么g 是严格边韧性度图 出定理2 1 7 知： 推论2 1 2h a r a r y 图h ( p ，女、是严格边韧性度圈 定理2 1 8 例对r 2 ，m a x r ，4 ) 定理21 9 例对r 2 ，s s2 r 推论21 3f ，- 4 第3 章严格边韧性度图的究要条件 31 严格边韧性度图的充要条件 首先给出一些定义和记号； 设r ( g ) - m i n s c ( s ) i s e e ( g ) ，如t ( g ) - s c ( s ) ，s e c ：e ( g ) ，就把g 中的s e 称为g 的r + 一集如果r ( g ) 一s c ( s ) ，就把s 称作丁集合：如槊 r ( g ) 一s c ( e ( g ) ) 就把g 称为边韧性图：如架( g ) 是满足丁( g ) - s c 陋( g ) ) 中的 唯一集合，就把g 称为严格边韧性圈 定理3 1 t 6 7 1 设g 是一个图，s 是g 中的r 。一集假设h 足g s 中所有非，f 凡分支的并，那么 生丛s c ( s ) p ：刍且仅当! ；! ! 旱s l 生( p 叫y ( 尉) l , q l m i e ( h ) i ，甜- ，埘( ) ，z - 。z i f o ) 口- - ( 1 1p 为了证明定理3 1 ，需要下面的引理 引理3 1 设口，b ，r ，y 是非负髌数，) 。，y 6 ，那么 兰s 竺当且仅当旦s 三 v y d 扫 y 这个结果的证明只颁经过简单的算术运算即可 定理3 1 的证明假设对g 中的t 一集s ，生坚5 c ( s ) 让h 是g s 中的所 有非平凡分支的并，如p p 1 ，f 一。p ，那么望；掣5 q + l p - - 0 1 p 否则，令x 是s t e ( a ) 一e ( h ) 中r 一集的基数，则可- q + z ，血i ( g s ) p p + 埘 r ( 6 一s ) 一r ( 日) - 一因此 型邻卜丙q-q而+rpp p j + 由引理3 1 知 q - v + ls 里盟 p 一p 相反令s 是将g 分解成( g s ) 个分支日，：，一，h 。，的r 一集， t - 珊( g s ) ，假设h 1 ，h 2 ，h r ( 1 f s f ) 是非平凡分支，令h 是打1 ，h 2 ，h ，的 并集那么 g = 型二! 堕：墅! ! ；型 p 一( f f ) 一和( g s ) 一( e r ) ) p e 目引理3 1 知 型；! 堕二! ! ! 倒 p( g s ) 因此， 里生s c ( s ) p 定理证毕 注解令g 是一个图，令s 是g 中的r 一集假设是g s 中所有非平凡分 支的并如 型。必 p - 0 p 那么 望蔓ts c ( s ) o - i v ( h ) l ，q - i e ( h ) 阿。旧) ，一。f ( h ) ) p 由此得出下面推论 推论31 设g 是4 个图，且设s 是g 中的7 1 一集假设g s 至多有- 个非f j , l s t 支r 如对g - s 中任何非平凡分支h 。0 d y ( h 川，岍* l e ( h ) | ，i - 1 , 2 ，k ： 七山、 一。型+ ! p 一lp 成立，那么g 是严格边韧性度图 证明假设g s 有k o