（电工理论与新技术专业论文）任意无向图的r点连通扩充.pdf

abs tract wi t h t h e d e v e l o p m e n t o f i n d u s t ry g r a p h t h e o r y h a s m a n y a p p l i c a t i o n s i n t h e fi e l d o f s y s t e m e n i g n e e r i n g , t e l e c o m mu n i c a t i o n e n g i n e e r i n g , o p e r a t i o n s r e s e a r c h , c i r c u i t n e t w o r k s , c o mp u t e r s c i e n c e , e c n o mi c s , s o c i o l o g y , a n d p s y c h o l o g y . a t t h e s a me t i m e , t h e o p t i ma z i t i o n p r o b l e m i n g r a p h t h e o ry b e c a me t h e f o c u s o f r e s e a r c h n o wa d a y s . c o n n e c t i v i t y a u g m e n t a t i o n p r o b l e m , a l s o a p r o b l e m o f c o m b i n a t o r i a l o p t i m i z a t i o n t h e o ry, i s a n i mp o r t a n t p a rt o f c o n n e c t i v i t y t h e o ry i n t h e f i e l d o f g r a p h t h e o ry, w h i c h h a s g r e a t s i g n i f i c a n c e i n r e l i a b i l i t y a n a l y s i s a n d d e s i g n o f e l e c t r i c a l n e t w o r k s . w e d o s o m e r e s e a r c h o n r - v e r t e x - c o n n e c t i v i t y a u g m e n t a t i o n p r o b l e m ( r v c a p f o r s h o rt ) o f a n y u n w e i g h t e d c o n n e c t e d g r a p h s . g i v e n a n u n w e i g h t e d c o n n e c t e d g ra p h g o 二 ( v o , e o ) a n d a c o n n e c t iv ity re q u ir e m e n t m a t ri x r 二 ,# 1 ， a m i n i m u m s e t o f e d g e s e m a y b e g o + 二 二 ( v , e o 。 二 ) s a ti s f ie d 、 ( vi ， 竹 ; 民 + e ) : p j co m p lex ity o rd e r o f 0 (3 2 r iv ( g )is) is p rese n te d a d d e d t o g o s u c h t h a t a n a l g o r i t h m r u c a w i t h t i m e in t h i s d i s s e r t a t i o n . i n s o me c a s e s , w e c a n o b t a i n a m i n i m a l a u g m e n t e d g r a p h s a t i s f y i n g t h e c o n n e c t i v i t y r e q u i r e m e n t s . i n t h e o t h e r c a s e s , w e c a n g u a r a n t e e t h a t t h e a u g me n t e d g r a p h s a t i s f i e s t h e c o n n e c t i v i t y r e q i r e m e n t s . t h e m a i n i d e a s a r e a s f o l l o w s : f i r s t , w e c o n v e r t a g r a p h t o a d i g r a p h b y u s i n g u t d ; t h e n w e t r a n s f o r m t h e p r o b l e m o f v e r t e x t - c o n n e c t i v i t y a u g m e n t a t i o n i n t o t h e p r o b l e m o f e d g e - c o n n e c t i v i t y a u g me n t a t i o n wit h s p l i t c o n s t r u c t i o n . t h e m e t h o d o f a u g m e n t i n g a d i g r a p h t o r - v e r t e x - c o n n e c t e d o n e i s a s f o l l o w s : a d d a n e w v e r t e x a n d a u g m e n t t h e d i g r a p h fi r s t ; t h e n c h e c k i t . i f i t d o e s n t s a t i s f y t h e d e ma n d e d e d g e - c o n n e c t i v i t y , t h e n s p l i t i t i n t o a s e r i e s o f i r r e d u c i b l e s u b g r a p h s . e a c h o f s u b g r a p h s w i l l b e a u g m e n t e d s e p a r a t e l y ; t h e n t h e a u g m e n t e d s u b g r a p h s w i l l b e c o mb i n e d i n t o a n a u g m e n t e d d i g r a p h ; f i n a l l y , t h e d e m a n d e d r - v e r t e x - c o n n e c t e d m i n i m u m a u g m e n t e d u n w e i g h t e d g r a p h c a n b e e n o b t a i n e d a ft e r a d m i s s i b l e l i ft i n g , s p l i t r e v e r s e c o n s t r u c t i n g a n d u t d r e v e r s e o p e r a t i o n t o t h e a u g m e n t e d d i g r a p h . i n t h i s d i s s e r t a t i o n , t h e o p t i m u m r u l e o f d i g r a p h a u g m e n t a t i o n a n d t h e o p t i m u m d i s c u s s i o n o f r u c a a r e p r o v i d e d r e s p e c t i v e l y . b y t h e d i s c u s s i o n o f t h e r u c a s o p t i mu m a n d c o m p l e x i t y , w e c a n fi n d s o me o p t i m a l a l g o r i t h m t o s o v l e r v c a p p r o b l e m u n d e r s o m e c i r c u ms t a n c e , w h i c h h a s s i g n i f i c a n c e i n s o l v i n g r v c a p c o m p l e t e l y . o u r r e s u l t s a l s o h a v e b r o a d a p p l i c a t i o n r a n g e . b a s e d o n r u c a , c a d s o ft w a r e o f r e l i a b l e n e t w o r k s c a n b e d e v e l o p e d a f t e r w e i g h t e d c o r r e c t i o n . t h e r e f o r e , w e c a n a c q u i r e m o r e r e a s o n a b l e s o l u t i o n t o t h e p r a c t i c a l p r o b l e m s u c h a s n e t w o r k s r e l i a b i l i t y i m p r o v e m e n t o r r e l i a b l e n e t w o r k i n g we c a n a c h i e v e mu c h m o r e e c o n o m i c b e n e f i t s f r o m t h i s , e s p e c i a l l y f o r t h e c a s e o f v e r y l a r g e s c a l e o p t i m a l n e t w o r k i n g . k e y wo r ds : g r a p h t h e o ry , c o n n e c t i v i t y , g r a p h s , a u g m e n t a t i o n 独创性声明 本人声明所呈交的学位沦 文是本人在导师指导 下进行的 研究工作和取得的 研究成果， 除了文中特别加以标注和致谢之处外， 论文中不包含其他人己经发表 或 撰 写 过的 研究 成 果， 也 不 包 含为 获 得 - a 建k生一 或 其 他 教育 机 构 的 学 位 或 证 书而使用过的材料。 与我一同 一 卜 作的同 志对本研究所做的任何贡 献均己在论文中 作了明确的说明并表示了谢意。 学 位 论 文 作 者 签 名 : 刘撰签 字 日 期 : ; 科 年y 月/ 日 学位论文版权使用授权书 本 学 位 论 文作 者 完全 了 解止 k 圭垫数 有 关 保留 、 使 用学 位 论 文的 规定 。 特 授权 玉建.人生一 可以 将学 位论 文的 全部或 部分内 容编 入 有关 数 据库 进行 检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门 或机构送交论文的复印 件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名: 签字日期:. 2 0 0 4 - 年 x 11 殡 7月 / 日 导 师 签 “ 二牙 浮1舜洲 签 字日 期 : t,0 q 年 7月 / 日 天津大学硕士学位论文 第一章 绪论 第一章 绪论 本章主要简单介绍图论的历史和发展情况， 并介绍本文结构的安排和内容以 及本文工作的意义。 . 1图论与可靠通信网研究 图论是组合数学的一个分支，它 起源于 k o n i g s b e r g桥问 题。它将研究的对 象进行抽象， 将实物抽象为点， 将实物之间的联系抽象为连接点的边， 从而建立 相应的数学模型。 这样的 数学模型使得图论可以 渗透到现 代众多科研领域中， 比 如电理论， 分子理论，计算机科学，管理科学， 运筹学等等，最近还有人提出将 图论 应用到商业规则的制定上。 在图论使这些领域的研究取得巨大突破的同时， 其 自身也正在以空前的速度发展着。 图论的 研究分为代数和最优化两个方面。 这里研究的图的最小扩充 属于图 论 的最优化问 题。 图沦 最优化问题的中心就是要寻求优化算法， 因此研究该领域的 图论也称之为算法图论。 一个通信网，它是山诸如交换中心、集线器、终端以及连接它们的传输线路 所组成。 通信网的 可靠性是指在人为或自 然的 破坏作用下， 通信网 在规定的条 件 下和规定的时间内的生 存能力。 常用的生存能力判据有 :网 络指定的节点对 之 间至少存在一条路径; 网 络中 指定的节点能与一组节点 相互通信: 网络中 可以 相 互通信的节点数大于某一ft 值; 网络中任意两节点间 传输时延小于某一fm l 值: 网 络的吞吐量超过某-闲值。 七十年代以 来， 通信网的可靠性研究就逐步引起了人 们的重视， 在许多 研究方法中 提出了 不少有关通信网可靠性的测度， 已 取得的 研 究成果大致可以分为2 1 : 网络的 抗毁性! 1 3 4 1 ; 网 络的生存性 5 1 6 1 7 8 9 1 : 网 络的有 效性 1 0 1 1 11 1 2 1 ;网 络部件工作在多 模式状态的可靠性测度【 1 3 1 4 1 5 1 。通信网的可靠 性取决于网 络拓扑结构的可靠性、 网 络部件的设备可靠性以 及用户对网 络业务 性 能的要求，其中网络拓扑结构可靠性是最重要的。 通信网 络的抗毁性是指在人为破坏作用下的网 络可靠性。 抗毁性指出了网络 至少需要破坏儿条边或儿个节点刁 能中断部分节点间的通信， 即破坏一个通信网 的困难程度。 网络的 抗毁性主要由 可靠 性的确定 性测度 边连通度和点连通度 来表示。 天津大学硕士学位论文 第一章 绪论 第一章 绪论 本章主要简单介绍图论的历史和发展情况， 并介绍本文结构的安排和内容以 及本文工作的意义。 . 1图论与可靠通信网研究 图论是组合数学的一个分支，它 起源于 k o n i g s b e r g桥问 题。它将研究的对 象进行抽象， 将实物抽象为点， 将实物之间的联系抽象为连接点的边， 从而建立 相应的数学模型。 这样的 数学模型使得图论可以 渗透到现 代众多科研领域中， 比 如电理论， 分子理论，计算机科学，管理科学， 运筹学等等，最近还有人提出将 图论 应用到商业规则的制定上。 在图论使这些领域的研究取得巨大突破的同时， 其 自身也正在以空前的速度发展着。 图论的 研究分为代数和最优化两个方面。 这里研究的图的最小扩充 属于图 论 的最优化问 题。 图沦 最优化问题的中心就是要寻求优化算法， 因此研究该领域的 图论也称之为算法图论。 一个通信网，它是山诸如交换中心、集线器、终端以及连接它们的传输线路 所组成。 通信网的 可靠性是指在人为或自 然的 破坏作用下， 通信网 在规定的条 件 下和规定的时间内的生 存能力。 常用的生存能力判据有 :网 络指定的节点对 之 间至少存在一条路径; 网 络中 指定的节点能与一组节点 相互通信: 网络中 可以 相 互通信的节点数大于某一ft 值; 网络中任意两节点间 传输时延小于某一fm l 值: 网 络的吞吐量超过某-闲值。 七十年代以 来， 通信网的可靠性研究就逐步引起了人 们的重视， 在许多 研究方法中 提出了 不少有关通信网可靠性的测度， 已 取得的 研 究成果大致可以分为2 1 : 网络的 抗毁性! 1 3 4 1 ; 网 络的生存性 5 1 6 1 7 8 9 1 : 网 络的有 效性 1 0 1 1 11 1 2 1 ;网 络部件工作在多 模式状态的可靠性测度【 1 3 1 4 1 5 1 。通信网的可靠 性取决于网 络拓扑结构的可靠性、 网 络部件的设备可靠性以 及用户对网 络业务 性 能的要求，其中网络拓扑结构可靠性是最重要的。 通信网 络的抗毁性是指在人为破坏作用下的网 络可靠性。 抗毁性指出了网络 至少需要破坏儿条边或儿个节点刁 能中断部分节点间的通信， 即破坏一个通信网 的困难程度。 网络的 抗毁性主要由 可靠 性的确定 性测度 边连通度和点连通度 来表示。 天津大学硕十学位论文 第一章 绪论 一个图的边 ( 点)连通度定义为使该图变为不连通所需移去的最少边 ( 点) 数。一个通信网的连通度越大， 使通信网中断所需 破坏的连接线路 ( 站点设备) 就越多，通信网越可靠 。但连通度越大，所需网络的连接线路 ( 站点设备) 就越 多，相应其费少 月 也越大。因而在网络设i 一 卜 ，会有这样的优化问题:在满足连通 度要求下，设计一网络 ， 使总费用最小。而在实际中， 常常遇到这样的情况: 对 于一个现有网络，一方面，时常有新的用户加入:另一方面，该网络的可靠性指 标 己经不能满足实际要求。因而需解决的问题是:如何在该网络中增加新的边， 使得该网 络的可靠性满足新的要求， 并使总费 用最小， 这个问 题就是网络扩充问 题。 对于小规 模的可靠网络设计问 题， 采用人工的方法便可解决， 而当问 题的 规 模很大时， 人工的方法难以胜任，只能借助于计算机辅助设计技术，即寻找一个 有效算法，通过计算机来完成网络的设计工作。 算法的复杂性可表示为问题规模n ( 一般指图的点 数或边数) 的函数t ( n ) . 当 t ( n ) 是对数函数，线性函数或多 项式函数时，算法才有实 用价值， 称这样 的算法是有效的或者好的，否则， 若 t ( n )是n的指数函数或阶 乘函数， 则称 这样的算法是 坏的。 存在有效算法的问题称为p 类问 题， 即 该问 题可以通过多项 式时间复杂度的算法得到解决。 在尚未找 到有效算法的问题中有一类最难处理的 问题 ， 它们的复杂性是等价的， 即其中一个 问题得到解决将导致这类问题的解决， 这类问 题称之为n p c问题。 关 于n p c问 题的研究预示着这类问 题可能根本不存 在有敛算法。因此， 对于一个优化问题的研究无沦是找到了一个有效算法， 还是 证明了它属于n p c问题，都可以说该问 题得到了解答。 根据最优化图论的上述特点，对于一个待研究的问题一般采用 “ 双边法” 即 一方面寻求有效算法;另一方面试图 证明该问 题属于n p c问 题;直到在其中 一个方向_ 卜 获得成功。 这要求研究者根据自己的经验和对问题的认识， 随时把握 和调整研究工作沿着最有希望的方向努力。成功地应用 “ 双边法”可以避免研究 的 盲目 性， 随时掌握主动， 大大缩短研究时间。 但这需要研究者兼有构 造n p 完 全证明和设计 有效算法两方面的知识。 1 .2 本文的工作及意义 在第二章， 我们 研究了 不加 权无向图的r点连通扩充问 题，给出了r点连 通扩充算法 r u c a，能够得到极小 r点连通扩充图，对将来该问题的 p类算法 研究具有理论指导意义。算法首先利用 u t d变换将无向图转化为有向图，再把 有向图 经 s p l i t构造把点连通扩充问 题转化为 边连通扩充问题。 在对有向图的 天津大学硕十学位论文 第一章 绪论 一个图的边 ( 点)连通度定义为使该图变为不连通所需移去的最少边 ( 点) 数。一个通信网的连通度越大， 使通信网中断所需 破坏的连接线路 ( 站点设备) 就越多，通信网越可靠 。但连通度越大，所需网络的连接线路 ( 站点设备) 就越 多，相应其费少 月 也越大。因而在网络设i 一 卜 ，会有这样的优化问题:在满足连通 度要求下，设计一网络 ， 使总费用最小。而在实际中， 常常遇到这样的情况: 对 于一个现有网络，一方面，时常有新的用户加入:另一方面，该网络的可靠性指 标 己经不能满足实际要求。因而需解决的问题是:如何在该网络中增加新的边， 使得该网 络的可靠性满足新的要求， 并使总费 用最小， 这个问 题就是网络扩充问 题。 对于小规 模的可靠网络设计问 题， 采用人工的方法便可解决， 而当问 题的 规 模很大时， 人工的方法难以胜任，只能借助于计算机辅助设计技术，即寻找一个 有效算法，通过计算机来完成网络的设计工作。 算法的复杂性可表示为问题规模n ( 一般指图的点 数或边数) 的函数t ( n ) . 当 t ( n ) 是对数函数，线性函数或多 项式函数时，算法才有实 用价值， 称这样 的算法是有效的或者好的，否则， 若 t ( n )是n的指数函数或阶 乘函数， 则称 这样的算法是 坏的。 存在有效算法的问题称为p 类问 题， 即 该问 题可以通过多项 式时间复杂度的算法得到解决。 在尚未找 到有效算法的问题中有一类最难处理的 问题 ， 它们的复杂性是等价的， 即其中一个 问题得到解决将导致这类问题的解决， 这类问 题称之为n p c问题。 关 于n p c问 题的研究预示着这类问 题可能根本不存 在有敛算法。因此， 对于一个优化问题的研究无沦是找到了一个有效算法， 还是 证明了它属于n p c问题，都可以说该问 题得到了解答。 根据最优化图论的上述特点，对于一个待研究的问题一般采用 “ 双边法” 即 一方面寻求有效算法;另一方面试图 证明该问 题属于n p c问 题;直到在其中 一个方向_ 卜 获得成功。 这要求研究者根据自己的经验和对问题的认识， 随时把握 和调整研究工作沿着最有希望的方向努力。成功地应用 “ 双边法”可以避免研究 的 盲目 性， 随时掌握主动， 大大缩短研究时间。 但这需要研究者兼有构 造n p 完 全证明和设计 有效算法两方面的知识。 1 .2 本文的工作及意义 在第二章， 我们 研究了 不加 权无向图的r点连通扩充问 题，给出了r点连 通扩充算法 r u c a，能够得到极小 r点连通扩充图，对将来该问题的 p类算法 研究具有理论指导意义。算法首先利用 u t d变换将无向图转化为有向图，再把 有向图 经 s p l i t构造把点连通扩充问 题转化为 边连通扩充问题。 在对有向图的 天津大学硕十学位论文 第一章 绪论 边连通扩充中， 采用先扩充再检验的方 法， 如果不满足要求， 再分解成一系列子 图进行扩充， 最后再合并成一个总图， 扩充后的总有向图 经可行删除， s p l i t 和 u t d逆变换便可得到所求无向图的 r点连通扩充图。文中提出了新的可行删除 方法，据此可获衍极小 r边连通扩充有向图，在定条件 卜 ，可以获得最小 r 边连通扩充有向图。 第三章和第四章对第二章所提出的算法 r u c a和算法 r d c a的最优性进行 了证明 和分析，并给出了例题。 第三章给出了 算法 r d c a的最优性证明;同时 证明了算法 r u c a可得到极小的 r点连通扩充图，在一定条件下，可以得到最 小的r点连通扩充图。另外，给出了算法r u c a的c / c + 十 语言 实现说明。第四 章给出了 两个典型的例题， 用以说明 算法 r u c a 的 可行性和在一定条件下的 最 优性。 第五章，对全文工作进行简单总结并给出将来工作的展望。 概括起来，本文研究了不加权无向图 r点连通最小扩充问 题，给出了 一个 多项式复杂度的扩充算法， 在一定条件下具有最优性。 具体做了以下几方面的 工 作: . 提出了解决“ 连通不加权无向图的r点连 通扩充问 题” 的一个有效算法 r u c a ， 即 对 任意 的 连 通 不 加 权 无向 图g a 和任 意 连 通 矩 阵r ， 利 用算 法 r u c a总 能 求出 一 个 使民+ e 成为r点 连 通图 的 极小 边 集e ， 在一 定 条件下e 是最小的。 .算法 r u c a采用 了将无向图的 r点连通扩充问题与有向图 r边连通扩 充问题等效的方法， 使得问 题转化为扩充一个有向图， 使其满足r边连 通条件。 在对有向图 进行r边连通扩充时采用了 “ 分治法” ， 对任意复 杂的有向图首先按照余度对图中各点进行扩充， 然后将图分解为具有 “ 不可压缩尸性质的子图， 对每个子图利用最优增广扩充判据， 对不满 足边连通度要求的点对 进行增广扩充处理， 最后再合并 起来。 对得到的 总图进行有向可行删除，以及 通过问题的 等效反变换， 最终得到所求的 r点 连通扩充图。 同时我们还编制了算法r u c a的c / c + + 语言 程序， 它 能够对各种题设情况给出正 确的解答，从而验证了 算法 r u c a 的可行 性。 . 对有向最小增广扩充图的可行删除操作，提出了一种新的操作算法 l i f t 。 利用该算法， 可以 将增广扩充图 对增广点进行解雇， 使得解雇后 的有向图中任意两点n 1 的边连通度依然满足连通度要求。 该操作是极小 的， 在一定条件下是最小的。 连通扩充问 题在实际工程问 题上有着广泛的应用和重大的理论指导意义。 例 天津大学硕十学位论文第一章 绪论 如在构造一个可靠通信网的研究中， 要求网络具有一定的抗毁性， 即在线路或者 设备出现故障时， 依然可以保持通信功能的特性。对于该问题，我们可以将设各 抽象定义为图中的点， 将连接这些设备的线路抽象定义为图中的边。 这样网络的 抗毁性就可以用图的连通度来描述， 而连通扩充问题的研究就可以为可靠通信网 的研究提供理论基础。 连通扩充问 题依 据连通度要求不同， 可以 分为点连通扩充 问 题和边连通扩充问题。 点连通扩 一 充问 题是要寻求一 个边集， 使得在进行边集扩 充之后的图中， 点对之间的点连通度达到扩充要求; 而边连通扩充问 题则是要满 足边连通度扩充要求。由于边连通条件要低于点连通条件， 这就使得点连通扩充 问 题要难于边连通扩充问 题。点连通扩充问 题又可分为k点连通扩充问 题和 x 点连通扩充问题。对于 k 点连通扩充问题 ，对全图的点连通度要求是一致的， 即要求至少删除 k个点才能使图不连通;而 r点连通扩充问题则对每个点对都 可以有不同的点连通度要求， 这无疑增加了解决问题的难度， 但同时也能够更好 地满足实际的需求。 因为有些情况下并不需要所有的点连通度要求都一致， 对于 某一些点对，要求其点连通度高一些，而对于其他点对，点连通度可以适当低一 些，这就使 得r点连通问题更具有实际的应用价 值。 山此可见，r点连通扩充问题更加符合实际的工程需要，比 k 点连通扩充 问题以 及边连通扩充问 题的难度都要大。 在后续章节中， 我们将具体介绍不加 权 无向图 r点连通扩充问题的解决。 天津大学硕士学位论文第二章 不加权无向图的r点连通扩充 第二章 不加权无 向图的 r 点连通扩充 本章主要介绍不加权无向图的 r点连通扩充问题及其解决算法。 在本章我们 提出了 一个多项式时间复杂度的算法。该算法可以获得极小 r点连通扩充图， 并且在一定条件下 ( 多数情况下)是最优的。关于算法的最优性将在下一章进行 证明 和闻述。 本章将在基本定义和定理的基础上， 阐述无向图 r点 连通扩充问 题与 有向图r边连通扩充问 题的关系， 并详细介绍如何通过解决特殊的有向图r 边连通扩充问 题，从而解决相 应无向图的 r点连通扩充问题。 最后给出算法描 述以及算法的复杂度分析。 2 . 1 引言 一个通信网络可由一个无 向图作为模型，网络中的设备节点抽象为图中的 点， 连接这些设备的 线路介质抽象为图中连接点的边。由 此， 抗毁性可由图的 边 连通度和点连通度来描述。网络在使用过程中，随着时间的推移，其可靠性己不 满足新的要求， 则需要改造， 提高它的可靠性。 如何在网络中 增加新的线路， 使 网络的可靠性满足新的要求， 并使总费用最小， 这就是网 络的 最小扩充问 题， 也 就是图论中的 “ 最小扩充问题气 定 义 2 - 1 ( 最 小 扩 充 问 题 ) : 对 无 向 图 民 一 ( v . , e o ) ， 和 单 增 性 质 c r “ 一 。 是 连 通 矩阵， 点 集v o t - 定 义 着 权f。 寻 求 一 个具 有 最小 权的 附 加 边 集刀， 刀二 e o ， 使得g a 十 厂二 ( v a , e q u e ) 具 有性 质c : 对 任 意两 点 ， 和j ， 均 有( 边或 点 ) 连 通 度c ( i , j ; g o 卜yj 将这一问题的给定条件加以适当约束便可得到它的一系列子问题。当 f u , v 二 1 时， 称为 无 权的 最小 扩充 或 简 称 最小 扩 充问 题。 当f ( u , v ) 不 恒 等于1 时 ， 称 最小 扩充问 题是 加 权的 ; 当 r j -= k 时， 称 为 是k 连通 最 小 扩 充问 题; 当 r . 不恒等于 1 时，称为 是 r连通最小扩充问 题;当所研究的图为有向 图时， 称为 是关于有向图最小扩充问题; 否则称为是关于无向图最小扩充问 题。 当c是某种 点连通特性时， 称为是关于点连通度的 最小扩充问 题: 当c是某种边连通特性时， 称为是关于边连通度的最小扩充问题。 人们的研究工作通常也是从这些子问题开 始的。 对于 边连 通 扩充 问 题， 首 先e s w a r n 和t a 巧 a n 16 】做了 两 方 面 开 拓 性的 工 作: 天津大学硕士学位论文第二章 不加权无向图的r点连通扩充 第二章 不加权无 向图的 r 点连通扩充 本章主要介绍不加权无向图的 r点连通扩充问题及其解决算法。 在本章我们 提出了 一个多项式时间复杂度的算法。该算法可以获得极小 r点连通扩充图， 并且在一定条件下 ( 多数情况下)是最优的。关于算法的最优性将在下一章进行 证明 和闻述。 本章将在基本定义和定理的基础上， 阐述无向图 r点 连通扩充问 题与 有向图r边连通扩充问 题的关系， 并详细介绍如何通过解决特殊的有向图r 边连通扩充问 题，从而解决相 应无向图的 r点连通扩充问题。 最后给出算法描 述以及算法的复杂度分析。 2 . 1 引言 一个通信网络可由一个无 向图作为模型，网络中的设备节点抽象为图中的 点， 连接这些设备的 线路介质抽象为图中连接点的边。由 此， 抗毁性可由图的 边 连通度和点连通度来描述。网络在使用过程中，随着时间的推移，其可靠性己不 满足新的要求， 则需要改造， 提高它的可靠性。 如何在网络中 增加新的线路， 使 网络的可靠性满足新的要求， 并使总费用最小， 这就是网 络的 最小扩充问 题， 也 就是图论中的 “ 最小扩充问题气 定 义 2 - 1 ( 最 小 扩 充 问 题 ) : 对 无 向 图 民 一 ( v . , e o ) ， 和 单 增 性 质 c r “ 一 。 是 连 通 矩阵， 点 集v o t - 定 义 着 权f。 寻 求 一 个具 有 最小 权的 附 加 边 集刀， 刀二 e o ， 使得g a 十 厂二 ( v a , e q u e ) 具 有性 质c : 对 任 意两 点 ， 和j ， 均 有( 边或 点 ) 连 通 度c ( i , j ; g o 卜yj 将这一问题的给定条件加以适当约束便可得到它的一系列子问题。当 f u , v 二 1 时， 称为 无 权的 最小 扩充 或 简 称 最小 扩 充问 题。 当f ( u , v ) 不 恒 等于1 时 ， 称 最小 扩充问 题是 加 权的 ; 当 r j -= k 时， 称 为 是k 连通 最 小 扩 充问 题; 当 r . 不恒等于 1 时，称为 是 r连通最小扩充问 题;当所研究的图为有向 图时， 称为 是关于有向图最小扩充问题; 否则称为是关于无向图最小扩充问 题。 当c是某种 点连通特性时， 称为是关于点连通度的 最小扩充问 题: 当c是某种边连通特性时， 称为是关于边连通度的最小扩充问题。 人们的研究工作通常也是从这些子问题开 始的。 对于 边连 通 扩充 问 题， 首 先e s w a r n 和t a 巧 a n 16 】做了 两 方 面 开 拓 性的 工 作: 夭津大学硕士学位论文第二章 不加权无向图的r点连通扩充 ( 1 ) 证明了“ 加权2 边连通扩充” 问 题属于n p 完全问 题。 根据n p 完全理论容 易证明: “ 加权 2遍扩充”问题的母问题“ 加权 r边扩充”问题和 “ 加权 k 边扩充”问题均属于 n p完全问题;( 2 )提出了最小扩充任意不加权无向图为2 边连通图的有效算法，从而证明了 “ 2 边连通扩充”问 题是p 类问题。 在此基础 上， 许多学者对扩充问题进行了研究， 取得了较大成果。 m. h a b i b 2 3 1 在 1 9 8 。 年 解决了“ 空图的k边连通扩充” ; k a j i t a n i 等 2 4 在 1 9 8 6 年解决了 “ 不加权树图的 k边扩充”问 题。 这些问 题都是 “ 任意无向不加权图的k边连通最小 扩充”问 题的子问 题。蔡国 瑞、孙雨耕2 s ! 在 1 9 8 9 年圆满地解决了该问 题， 提出了一个有 效算法， 证明 其为p类问 题。同时提出 的判断图的 k边连通最小 扩充的充要条 件， 这一具有突破性的研究成果立即成为了后续课题研究的重要理论基础并多次 为外国学者引用。在此基础上， 孙立山、孙雨耕1 2 1 1 2 0 1 等解决了 “ 任意无向 图的 最小 r边连通扩充”问题和 “ 任意有向图的最小 k边连通扩充”问题。以上所 述 研究成果之间的关系可以参考图2 - 1 ( a ) 所示。 至此， 除 有向图 的最小r边连通 扩充问 题仍未得到解决之外，不加权图的边连通扩充问题的求解己经比较完善。 与边连通扩充问 题相比， 点连通扩充问 题是公认难度更大的一 类问 题。 许多 学 者 研究 了 它 的 一 些 列子问 题， 取 得 了 丰 硕的 成果 。 e s w a r a n 和t a rj a n t16 1于1 9 7 6 年 提出 了 点 连通 扩 充问 题， 并 解决 了 ， 2 点 连 通 扩充” 问 题; t o s h im a s 和w a ta n a b e 2 9 解 决了“ 3点 连 通扩 充” 问 题; h a r a r y 2 2 解 决了“ 空图 的 点 连 通扩 充”问 题; ma s u z a w a 3 4 解决了 “ 根有向 树图的点连通扩充”问 题;孙雨耕、贺昌 科 2 8 】解决 了“ 无向 树图的最小k点连通扩充” 问题;曹 其国、 吴雪、 孙雨耕 1 8 ) 解决了“ 无 向 图 的k点 连 通扩 充” 问 题。 以 上 所述 研 究 成果 之 间 的 关 系可 参 考图2 - 1 (b ) 所示 。 在图2 - 1 ( b ) 中的问题可分为三个区: 加权问题均为n p完全问 题: 不加 权扩 充问题的几种简单情况属于 p 类问题;对于中间带开发区的 “ 不加权的r点连 通扩充”问 题， 还有待于研究，或证明 其为n p 完全问 题，或提出 解决的有效算 法。 不加权无向图的r点连通扩充问 题是图2 - 1 伪 ) 中 系列问 题的 母问 题， 解决该 问题具有相当的难度，主要体现在以下两个方面:最优判据的寻找， 即满足什么 条件的扩充才是最优的; 在满 足最优判据的条件下， 如何将扩充边集加入到已 有 网络中， 即在什么位置上添加扩充 边集。 与此同时，由 于该问题需要满足不同点 对间的不同点连通度要求， 因而在可靠通信网的分析和设计等问题上具有更实际 的应用价值。 本章 提出了一个多项式时间复杂度算法r u c a ， 并指出通过该 算法可以得到 一个极小的r点连通扩充图，在一定条件下，算法是最优的。 万飞月切窝邑揍雇律尸曰侧常 官丫2困 万毛侣工.芝 191恨耘刑“澎具 拟年图圳版洲名团星从澎具冷橱川城 它1c记奋沪5田 州润划黔书厚斜杖般以 万蒸咖职翁使渝 很格城目团革尽长 ul1, 因圳lh山n ，巴口沐闪二幼演 恨帐城园匆但仲理 团寒叔叮/困谊攘只才 因洲众聋长豁哭国困澎具冷疽眼 举日料持 1川、己f q一凶困 万匕已县 恨耘艇冈团俐. 团翎叔泞 .t识拓利窝澎具岭 川、 里恨耘领州澎具 狱iije 191恨林艇国澎口只 椒辐叫划艇闭9困谊眼澎具降橱11概 1你2。侣与目沐 恨帐艇护 乏 里写冬苗 祝j橇篇 n 川、卜己卜 911椒林项闪澎具 州双举外泪踏姗拭艇以 天津大学硕士学位论文第二章 不加权无向图的r 点连通扩充 算法 r u c a的总体设计思想是:首先利用 u t d变换将无向图转化为有 向图，再 把有向图经 s p l i t构造把点连通扩充问题转化为边连通扩充问题。 在对有向图 的边连通扩充中， 采用先扩充再检验的方法 ， 如果不满足要求， 再分解成一系列 子图 进行扩充， 最后在合并成一个总图。对总图进行可行删除，再 经 s p l i t和 u t d的逆变换便可得到所求无向图的 r点连通扩充图。 下面我们介绍一些相关的定义和定理，作为后续讨论的基础。 2 . 2基本定义和定理 对于 图g 二 ( v ( g ), e ( g ) ， 其中以 g ) 是图 g的 非 空顶 点 集合， 在 不会 引 起歧 义的 情况 下 可 简写 为v ; e ( g ) 是图 g 的 边 集， 简 写为e 。 文中 所 提 到的 无 向 图 不含 自环同时没有并联边，有向图同样不含有 自环，但可 以有并联边 。若 e ( g ) = 巾， 则g 称 为 空图。 以 下主 要 介绍 关 于无 向图 的 一 些 基本 定 义， 若 不 特 殊指明，所提到的图均为无向图。 定 义2 - 2 : ( x , y ) 。 表 示图 g中 连 接两 点x , y 的 直 接边 集， 简 写 为( x , 力。 定 义2 - 3 : v , ( e ) 表 示 边。 。 以 司的 顶 点 集 合 。 如 若 。 e ( x , 力 。 ， 则 v c ( e ) = i- , 对 。 记 灭 0 以的一 a 称 为a 的 补集 。 设a 二 。 佑 ) , b c - 以 g ) ， 且a n b = o ，则 有以 下定义。 定 义2 -4 : e ( a ,b ; g ) - j e : e e e ( g ) , 咋 ( e ) n a ， (d , 咋 ( e ) n b ， 叫， 表 示 一 端 点 在 点 集a 中 ， 另 一 端点 在点 集b 中 的 直 接 边 边集 ， 简 写为e ( a , 刃。 定 义2 - 5 : d ( a , b ; g ) 刽 e ( a ,b ; g ) , , 表 示 分 离 点 集 a 和 点 集“ 所 需 要 删 除 的 边 数 ， 简 写为 d ( a , b ) 。 定 义 2 - 6 : 以 句 “ 钊 a , 元 g ) ， 表 示 将 点 集 “ 从 图 g 中 分 离 的 边 集 ， 简 写 为e ( a ) 。 定 义2 - 7 : d ( a ; g ) 制 e ( a ; g 外表 示 将 点 集a 从 图 g 中 分 离 所 需 要 删 除 的 边 数， 简 写 为d ( 刃。 定 义2 - 8 : d ( x ; g ) 表 示点、 g v ( g ) 的 度， 即与 ; 点 关 联 的 边数 ， 简 写 为d ( x ) o 定 义 2 -9 : s (g ) - 珊价;吓 表 示 图 中 的 最 小 度 ， 简 写 为 8 a 定 义2 - 1 q : n ( x ; g ) 表 示点 ， 的 邻点 集。 n ( x ; g ) - y : y e v ( g ) 且 ( x , y ) a # (1) ， 简 写 为 n ( x ) 。 定 义2 - 1 1 : g 一 e - 少( g ) , e ( g ) 一 e ) ， 其 中 e 二 e ( g ) ; 若 e = e ， 则 记 g 一 e = g 一 e 。 定 义2 - 1 2 : g + e - ( v ( g ) , e ( g ) u e ) 】 其 中 e 是 定 义 在 v (g ) 上 的 边 集， 并 且e ” 二 e 佑 ) ， g + e ” 称为g 的 扩 充图 ; 若r= e ， 则记 g 十 e = g 十 。 。 定义 2 - 1 3 : g - a 是由图g中 删除了点集a以 及与a 相关联的边集后而得到 天津大学硕士学位论文第二章 不加权无向图的r 点连通扩充 算法 r u c a的总体设计思想是:首先利用 u t d变换将无向图转化为有 向图，再 把有向图经 s p l i t构造把点连通扩充问题转化为边连通扩充问题。 在对有向图 的边连通扩充中， 采用先扩充再检验的方法 ， 如果不满足要求， 再分解成一系列 子图 进行扩充， 最后在合并成一个总图。对总图进行可行删除，再 经 s p l i t和 u t d的逆变换便可得到所求无向图的 r点连通扩充图。 下面我们介绍一些相关的定义和定理，作为后续讨论的基础。 2 . 2基本定义和定理 对于 图g 二 ( v ( g ), e ( g ) ， 其中以 g ) 是图 g的 非 空顶 点