（运筹学与控制论专业论文）两类控制参数在特殊图类上的算法研究.pdf

2 0 0 5 年上海大学硕士学位论文 摘要 在过去的三十多年里，随着计算机科学的迅速发展，图论也得到了飞速发展， 而图论中发展最快的领域也许就是控制数理论的研究控制数理论能够快速发展 的主要原因是它在现实世界中，例如编码理论、计算机科学、通信网络、监视系统 和社会网络等理论与实践中有着广泛而深刻的应用背景 设图g = ( y ( g ) ，e ( g ) ) 为简单无向图，v ( o ) 和e ( c ) 分别为图g 的顶点 集和边集设d 矿( g ) ，若v ( g ) d 中的每一个点至少与d 的某一个顶点相邻 接，也目9n f d 】= v ( g ) ，则称d 为g 的控制集，1 9 9 8 年，h a y n e s 和s l a t e r 基 于某类应用背景提出了配对控制集的概念2 0 0 0 年，h e d e t n i e m i ，h e d e t n i e m i 和 r a l l 提出了图的无圈控制集问题集s v 称为g 的配对控制集( 无圈控制集) ， 如果s 是g 的控制集且导出子图( s ) 存在完美匹配( 不含有圈) 控制相关参数的算法复杂性问题作为控制数理论研究中的一个重要领域，受 到了越来越多的研究人员的关注不过，对于任意图，几乎所有的控制相关参数问 题均是n p 皖全的即使一个问题被证明是n p 完全的，人们仍然有可能得到此问 题的特定实例的多项式算法( 例如，对于任意图具有n p 一完全性的控制数问题已 经被证明在树、区间图、a t - f r e e 图上是多项式可解的) 本文主要研究了两类新 型控制参数( 配对控制数和无圈控制数) 在特殊图类的算法复杂性问题，主要工作 分为两个部分： 第一部分，由于任意图的配对控制集问题具有n p 一完全性，我们考虑了a t f r e e 图类在研究了a t f r e e 图类的结构性质的基础上，我们给出了配对控制集在 a t 1 一f r e e 图的b f s 一树上分布的结构性质利用这些性质，我们给出了求解a t - f r e e 图类最小配对控制集的多项式时间算法 第二部分，针对文f 4 1 1 中提出的一些公开问题，同时在注意到无匿控制集问 题对于二部图都是n p 一完全的这一事实基础上，我们研究了二部图的一个子类二 部置换图的无圈控制集问题当限定在二部置换图上时，我们证明了无圈控制数 等于其控制数( ( g ) = 7 ( g ) ) 利用此结论我们给出了二部置换图的无图控制集 问题的线性时间求解算法 关键词： 图；算法；控制集；配对控制集；无圈控制集 2 0 0 5 年上海大学硕士学位论文 i i a bs t r a c t ”? i t h i at h el a s tl n o r et h a nt h i r t yy e a r s jc o n c l l r i ? e n tw i t ht h eg r o w t ho fc o m p u t e is c i e n c e ，g r a p ht h e o r yh a ss e e ne x p l o s i v eg r o w t h ，p e r h a p st i l ef a s t e s tg r o w i n g a le aw i t h i ng ia p ht h e o r yi st h es t u d yo fd o n l i n a t i o ni ng r a p h s t h er a p i dg r o w t h o fd o a i i n a t i o ar e s e a r c hi sa t t r i b u t a b l em a i n l yt oi t ss om a n ya p p l i c a t i o n st or e a l w o l mi j r o b l e m s ) s l l c ha sc o d i n gt ll e o l mc o m p u t e rs c i e n c e ，c o m m u n i c a t i o nn e t w o r k s ， n l o l l i l o rs 3 7 s t c l r ia n ds o c i a ln e t w o r kt h e o r y l e tg = ( v ( g ) ，e ( g ) ) b eas i m p l eu n d i r e c t e dg r a p h ，a n dt i l ev e r t e xs e t a n de d g es e to fga r ed e n o t e db yv ( c ) a r i de ( g ) as u b s e td vi sc a l l e da d o m i n a t i i i gs e to fg i fe v e iyv e r t e xi nv si sa d j s c e n tt oa t1 e a s to n ev e r t e xi ns ie ，a r d 1 = v ( g ) i i l1 9 9 8 ，h a y n e sa n ds l a t e ri n t r o d u c e dt h ec o n c e p to fp a i r e d d o m i n a t i o ni n9 2a p h sw h i c hh a st o m es p e c i a lm o n i t o r i n ga p p l i c a t i o n si n2 0 0 0 ， h e d e t n i c m i ，f e d e t n i e r n ia n dr a l lf i r s ts t u d i e dt h ea c y c l i cd o m i n a t i o ni ng r a p h s a s l l b s e ld vi se m l e d8p a i r e df a c y c l i c ) d o m i n a t i n gs e to fgi fsi sad o m i n a t i n g s e tt t l l dt i l ei n d u c e ds u b g la p h ( s ) h a sap e r f e c tm a t c h ( c o n t a i n sn oc y c l e s ) a sa l li2 n p o r t a n tr e s e a r c hf i e l di nd o m i n a t i o nt h e o r y , t h ea l g o r i t h l n i cc o i n p l e x i t yo fd o m i n a t i o n r e l a t e dp m a m e t e r sh a sa t t r a c t e da t t e n t i o nf r o n im o r ea n d 1 22 0 1p1 e s e a r c i l e r s u n f o r t u n a t e l y ， k h u o s ta l lt h ed o m i n a t i o n r e l a t e dp a r a m e t e r sa r e n p c o n i p l e t cf o rt e n e t a lg t a p h sh o w e v e r ，e v e ni fap r o b l e mi sp r o v e dt ob en p c o m p l e t e ，i tm a yb ep o s s i b l et of i n dap o l y n o m i a la l g o li t h mf o rs o r n er e s t ii c t e d i n s t a l l c e so ft h i sp r o b l e m ( f o re x a m p l e ，d o m i n a t i o np r + o b l e mt h a ti sn p c o m p l e t e f e ng e l l e la lg r a p h sh a v ep r o v e dt ob ep o l y n o m i a ls o l v a b l ew h e nr e s t 2 l e t e dt ot le e s i n t e l v 1 lg r a p h sa t f i e eg r a p h s 1i nt h i sp a p e r 。w es t u d yt h ea l g o r i t h m i cc o r n - p l e x i t ，o tt w ok i n d so f12 e vd o m i n a t i o i 2 一r e l a t e dp a l la m e t e r s ( p a i r e dd o m i n a t i o na n d a c y c l i ed o m i n a t i o n ) i ns p e c i a lg r a p h s ) a n dt h ef o l l o w i n gt w op a r t sa l eo u rm a i n i e s2 1i t s 2 0 0 5 年上海大学硕十学位论文 i i i i nc h ef i is tp a r t ( c h a p t e r3 ) ，s i n c et h ep a i l 州d o m i n a t i o np 1 _ o l f l e m i sn p h c o m p l e t ef o rg e n e r a lg r a p h s w et u r n o l l ra t t e n t i o ut oa t 一5 、e eg r a p h s w eg i v et h e d i s t r i b u t e ds t r n c t u la lp r o p e r t yo ft h ep a he e l d o m i n a t i n gs e to nt i l eb f s c lc eo fa n a t f r e eg r a p h a p p l y i n gt h es t r u c t u r a lp r o p e r t y ，w ep t e s e n t8p o l y u o m i a lt i m e a l g o r i t t n nt oc o m p l t t eam i n i n m mc a r d i n a l i t yp a l le d d o m i n a t i n g s e to na i 、一f l e e g r a p h s i nt h es e c o n dp a r t ( c h a p t e r4 ) ，n o t i n gt h a tt h e r ea r es o n l eo p e np t o b l e n l sa n d t h ef a c tt i n t tt h ea c y c l i cd o m i n a t i o np r o b l e mi sn p c o m p l e t ec i 哟e ni e s t f i e t e d t ob i p a l t i l eg i a p i t s ，w ec o n s i d e rt h e s ep r o b l e m so i lb i p m t r ep c lr n u t t u , i o l tg r a p h s w h i c hi sas u b c l a s so fb i p a r t i t eg r a p h sw es h o wt h & tt h ea c y c l i cd o m h u t t i e nl l l l n l l 3 f 2 1 o fab i p a t t i r ep e r m u t a t i o ng r a p he q u a l st oi t sd o m i n a t i o nn u m b m ( ( g ) = 7 ( g ) ) ， u s i n gch i sr e s u l tw eg i v ea l i n e a rt i m ea l g o r i t h mt oc o m p u t ei t i i l i l t h n q i ac a r d i n a l i t y a c y e l i ed o m i n a t i n gs e to nb i p mt i t ep e r m u t a t i o ng r a p h s k e yw o r d s ：g r a p h ；a l g o l i t h m ；d o m i n a t i n gs e t ；p a i l e d i d o m i n a t l u g s e t a c y c l i cd o l n i n a t i n gs e t 原创性声明 本人声明：所呈交的论文是本人在导师的指导下进行的研究工作除了文中特 别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果， 参与同一工作的其他同志对本研究所做的任何贡献均已在论文中做了明确的说明 并表示了谢意 签名：许屯_ 红 日期：炒厂年，月纠日 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有权保留论 文及送交论文复印件；允许论文被查阅和借阅；学校可以公布论文的全部或部分 内容。 保密的论文在解密后应遵守此规定 签名：许境4 铃 导师酪铩7 ；i 兵 第一章引言 本章主要介绍图的控制数理论的产生背景，应用领域及其主要研究方向，最 后指出j 本文所做的主要i 作 1 1 图的控制数理论的产生背景 近几十年来，随着计算机技术和网络通讯技术的飞速发展，图论研究也呈现 出异常活跃的趋势由于在现实世界和理论研究中广泛而深刻的应用，图的控制 数理论已成为其中发展最快的研究领域之一 对图的控制数的研究最早可追溯到十九世纪中期当时有一种棋盘比赛，棋 赛的目的就是用某些棋子覆盖或者控制棋盘上的所有方格。人们注意到了在棋盘 上如何放髓最少几个皇后就可控制( 覆盖) 或占据所有的方格这样的问题，这就是 困的控制数问题的最初形式1 8 6 2 年d ej a e n i s c h 研究了控制( 覆盖) 整个棋盘 所需要的最少的皇后个数问题据1 8 9 2 年r o t t s eb a l i 在文章中总结可知，十九世 纪末期人们主要对棋盘上如下三类控制问题进行了研究：( 一) 覆盖问题为了覆 盖( 攻击或控制) 一个n ，z 棋盘的所有方格最少需要多少个给定类型的棋子? 这 是求晟小势控制集的一个例子，( 二1 独立覆盖问题为了控制nx ，t 棋盘的所有 方格最少需要多少个不构成互相攻击的给定类型的棋子? 这是求最小势独立控制 集的一个例子( 三) 独立性问题在一个n ，t 棋盘上最多可以放盈多少个不 构成互相攻击或控制的给定类型的棋子? 这是求最大势独立集的一个例子当给 定的棋子类型是皇后时，此问题就是有名的一皇后问题在1 9 6 4 年左右y a g l o m 和y a g l o m 兄弟两人详细研究了上述三种类型的问题 在1 9 6 0 年前后，人们开始对图的控制数进行数学理论方面的研究所公认的 圈的控制数理沦是在1 9 5 8 年由b e l g e 和1 9 0 2 年由o i e 共同建立的1 9 5 8 年 l 蚺g e 的图论专著中首次定义“控制数”这一概念( 虽然当时他用的是另外的名称) 2 0 0 5 年上海大学硕士学位论文 2 而到了1 9 6 2 年，o r e 的图论著作中，正式定义并使用目前一直沿用的控制数方面 的术语“d o m i m 、t i n gs e t ”和“d o m i n a t i o nn u l l l b e r ”1 9 7 7 年，c o c k a y n e 和 h c d c t r f i e m i 在一篇报告中综述了当时已知的有关图的控制数的结果，并且首次使 用符号7 ( c ) 表示图g 的控制数，此符号一直沿用至今此后的1 0 多年里，这一理 论开始引起人们的广泛关注并得到迅速发展，众多的研究者纷纷投入到控制数问 题的研究中来据1 9 9 0 年d i s c r e t em a t h e m a t i c s 出版的一期专辑( v o l8 6 ) 统计，截至当时累计的文献就达到了4 0 0 衙随后控制数理论成为图论中一个重 要的研究热点鉴于此理论的迅速发展，1 9 9 8 年，美国学者h a y n e s ，h e d e t n i e m i 和s i 。、t e ri 3 7 ，3 8 1 在对此领域进行系统总结后，首次出版了两本关于图的控制数 理论的专著d o m i n a t i o ni ng r a p h s a d v a n c e dt o p i c s 和p u n d a m e n t a l so f d o m i n a t i o ni ng r a p h s ，其中在f u n d m n e n t a i so fd o m i n a t i o nh ig r a p h s 中 引用了1 2 1 ) 0 多个文献2 0 0 0 年，以m s 为d o m i n a t i n 9s e f s ，i n d e p e n d e n ts e t s ， c i q u t i 5 在分类条目中专列了一项0 5 c 6 9 关于控制参数理论研究的全面进展可参 看 3 7 3 8 】 图的控制数理论不仅从图论本身研究角度来看具有重要意义，而且在相关学 科例如计货：机科学、通讯网络及编码理论等领域有重要的应用价值图的控制数 理论能够快速发展的原因是由于其内在的研究价值以及对相关学科研究的指导作 用共同决定的，归纳起来主要有以下三个方面的主要原因： ( 一) 它在现实世界和渚如“覆盖”、“监控”等数学模型研究中有着广泛而深 刻的指导意义在现实中的许多问题模型都可以归结为图的控制( d o m i n a t i o n ) 问 题 例如，用图g = ( v ，e ) 表示一个通信网络，点集v ( c ) 表示所有的网络节 点，边集e l g ) 表示连接两个网络节点的通信线路为了监控一个网络节点( 这些 节点放置有重要设备) 的运行状态，可以在比节点或其相邻节点上放置一种监控设 备，放置这样的监控设备往往费用相当昂贵基于费用最j 、化的考虑，在保证所有 2 0 0 5 年上海大学硕士学位论文 3 节点均被监控的条件下，应该选择尽可能少的网络节点来放置监控设备，满足条 件的被选择节点数目的最小值就是图g 的控制数7 ( g ) ( 二) 控制参数定义类型的多样性根据实际背景的不同。现已定义的控制参 数有几十种之多，而且随着研究的深入和应用背景的扩大，新的控制参数仍然继 续不断地涌现 ( 三) 图的控制参数判定问题的n p 完全性与其它组合优化中n p 一完全问题紧 密而自然的关系在特殊图类( 如树，区间图，弦图，置换图，a t - h e e 图等) 上 研究各类控制参数的计算复杂性问题已成为组合优化领域中一个引人入胜而富有 挑战一陛的研究方向 1 2 图的控制数理论的应用领域 椰众多的理论一样，图的控制数理论也来源产生于实践当中现实世界中深 刻两广泛的应用背景是这一理论能够得以快速深入发展的重要原困之一昌前， 图的控制数理论的应用领域主要有运筹学、计算机科学、通信技术、网络理论以及 社会学等等下面我们来看几个应用实例 广播站选址问题设想某一地区分布有若干个村庄，我们想要选择一些利庄建 设广播站，使得信息可以通过这些广播站广播到全部的村庄由于每个广播站只 有一个有限的信号覆盖范围，我 f j 必须要建设多个广播站，然而，建设广播站的费 用足昂贵的，在满足能够覆盖全部村庄的前提下我们希望所需要建设的广播站数 目达到最少假设每个广播站的信号覆盖半径为r ，点集v ( c ) 代表所有的村庄 如果任意两个村庄u 和w 之间的距离不超过r ，我们添加一条u 到w 的边，最后 就得到一个图g 于是，问题就变为如何求解图g 的一个最小控制集 电力网监控问题2 9 0 2 年，h a y n e s 等人在文【3 6 】中首先研究了这类问题由 2 ( 0 5 年上海大学硕士学位论文 4 1 二此类问题具有深刻的应用背景，人们对它的研究仍在不断深入之中电力公司为 了实现对整个电力网运行状况的监控，需要在电力网中放置一些监控设备( p m u ) 由于p m u 成本的昂贵性，在保证整个电力网被完全监控的前提下需要使得配置 的p m u 数量达到最小化设图g = ( ue ) 代表整个电力网，点集v ( c ) 代表所有 的电力网节点，边集f ( g ) 代表电力传输线根据电力网中特定的“监控”概念， h a y n e s 等人定义了电力控制集( p o w e rd o m i n a t i n gs e t ) 的概念，并发现它与图论 中经典的覆盖，控制集问题有着密切的联系 社会网络理论k e l l e h e r 等人1 4 9 1 研究了图的控制数理论在社会网络理论中应 用的有关问题社会网络理论中人们通常要研究存在于一个群体之间的某些关系 “e b t i o n s h i p s ) 群体中的人们一般被称为参与者( a c t o r s ) 关系通常用一个或多个 二元将征来定义，即，对两个参与者来说这一特征他们明确地或者具有或者不具 有给定一个特征，人们可以构造一个社会关系图，图中的点代表参与者，两点问 的边代表对应的两个参与者具有所述的特征一个社会网络团是指一些参与者的 集合，对于给定的特征，集合的任意两人或者同时具有或者同时不具有( 也即，代 表社会网络团的点集的导出子图为完全图或者独立集) 状态集( s t a t u s ) 指社会网 络图t l t 这样的点集s ，对任意的两个点u ，ues ，有( u ) 八v s = ( ) n v s ， 于是，状态集中的所有点控制着状态集外的同一个点集社会网络图中的两个点 “和v 称为结构等价的，如果有( u ) = n v ) 或m = i 。 成立集合s 称为 结构等价集如果s 中任意两个点都是结构等价的社会网络研究人员对于在 个社会网络图中寻找极大结构等价集和所有的状态集尤其感兴趣，并且也设计了 些求解此类川题的算法k e t l e h e r 和c o z z e n 的研究表明，图论中的控制数理 论可以应用到上述问题的研究中去他们得到了如下结论： 定l 里1 2 1 ( 5 0 1 ) 若阶n 2 的连通因g 的一个7 集s 同时也是一个状态集， 则s 是g 的势为2 的独立控制集 2 0 0 5 年上海大学硕士学位论文 5 推论1 2 1 ( 5 0 ) 若连通图g 的一个7 一集s 同时也是结构等价集，则s 包含两 个度为l 1 的独立点 随着图的控制数理论研究的继续深入，新的应用领域仍然不断涌现 1 3 主要研究方向 近几f 年来，图的控制数理论一直是图论研究中的一大热点，据统计，到目前 为止，这一领域的文献数目已达3 0 0 0 篇以上这其中的研究方向主要集中在以下 儿个方面： ( 1 ) 各种控制参数的界的确定及其相互之间的关系研究； ( ! ) 各种控制参数求解问题的计算复杂性及其算法方面的研究； ( 3 ) 雨数控制数及其相关问题的研究； ( 4 ) 控制数理论在相关学科中的应用研究等等， 随着对这一领域研究的不断深入，人们发现其他学科( 例如：通信技术，网络 理论等等) 中都可以利用图的控制数理论解决很多重要的问题例如，通信网络中 f f , j 数据信息的蹈由问题一直是网络技术的重要研究领域研究表明，运用图的控 制数理论能够有效地解决这些问题 1 4 本文的主要工作 串 实上，由于所有主要控制参数的判定问题在任意图上都是n p 一完全的，于 是，在特殊图类( 如树，区间图，弦图，罱换图，a t - f r e e 图等) 上研究各种控制 参数的计算复杂性问题成为一个引人入胜但同时具有很大挑战性的研究方向 率文所做的主要t 作是研究了两类较新型的控制数( 配对控制数和无圈控制 2 0 0 5 年上海大学硕士学位论文 5 推论1 2 1 ( 5 0 i ) 若连通图g 的一个7 一集s 同时也是结构等价集，则s 包含两 个度为 一1 的独立点， 随着图的控制数理沦研究的继续深入，新的应用领域仍然不断涌现 1 3 主要研究方向 近几十年来，图的控制数理论一直是图论研究中的一大热点据统计，到目前 为止，这一领域的文献数目已达3 0 0 0 篇以上这其中的研究方向主要集中在以下 儿个方面： ( 1 ) 各种控制参数的界的确定及其相互之间的关系研究； ( 2 ) 各种控制参数求解问题的计算复杂性及其算法方面的研究； ( 3 ) 隔数控制数及其相关问题的研究； 4 控制载理论在相关学科中的应用研究等等 随着l f 这一领域研究的小断深入，人们发现其他学科( 例如：通信技术网络 理论等等) 中都可以利用图的控制数理论解央很多重要的问题例如，通信网络中 的数据信息的路由问题一宣是网络搜术的重要研究领域研究表明，运用图的控 制数理沧能够有效地解决这些问题 1 4 本文的主要工作 事实上，由于所有主要控制参数的判定问题在任意图上都是n p 一完全的，于 是，在特殊蜀类( 如树，区间图，弦图，置换圈， a 丁f 1 e e 图等) 上研究各种控制 参数的汁货复杂性问题成为一个引人人胜但同时具有很大挑战性的研究方向 本文所做的主要j 作是研究了两类较新型的控制数( 配对控制数和无圈控制 本文所做的主要j 作是研究了两类较新型的控制数( 配对控制数和无圈控制 2 0 0 5 年上海大学顼十学位论文 6 数) 在特殊图类上的求解算法问题包括两部分第一，本文研究了配对控制集在 a t f l c e 图上分布的性质特征，利用这些性质特征，我们给出了n 丁k e e 图类的配 对控制集问题的多项式时间求解算法；第二，针对文f 4 1 1 中提出的若干问题，本 文研究了二部世换图的控制集和无圈控制集之问的联系，证明了二部趾换图的控 制数等于无圈控制数1 ，( g ) = 1 。( g ) 利用这一结果，我们同时给出了二部鬣换图 类的无圈控制集问题的线性时间求解算法 本文的主要结构是：第一章引言部分主要介绍了图的控制数理论的背景及应 用；第二章给出了图论中一些基本的概念和记号以及控制数问题的一些基本结论； 鲜；三章中我们研究了a t - 矗c e 图的配肘控制集问题；第四章主要讨论了二部f t 换 图的控制集和无图控制集的联系以及其无圈控制集问题的求解算法 第二章基本符号和结论 2 1 基本概念和记号 本文所讨论的图均是无孤立点、无环无多重边的有限简单图凡是文中未加 定义的术语和符号，可参看文献【4 ，3 7 】为了叙述方便，我们首先引入一些定义和 记号设g = ( 、，e ) 是简单图，v ( g ) ，s ( c ) 分别表示图g 的顶点集和边集，g 的点的数日= i v ( a ) f 称为图g 的阶数如果图h 满足条件v ( h ) v ( c ) 和 e ( 打) f ( g ) ：则称h 为图g 的一个子图对s y ( g ) ，用( s ) 表示由s 导出 的于闺 图c 中点z 的开邻域定义为n ( x ，g ) = ：( z ，) e ( g ) 1 ，z 的闭 邻域为g 】= n ( x ，g ) u z ) 更一般地，对任意的x y ( g ) ，我们定义 x ( x ，g r ) 二= 1 2 一c x n ( zg ) n i x ，g 】= n ( x ，g ) ux 在不引起混淆的情况下，上 述符号可分别简记为v ( z ) ，h ，( x ) 和 xj 设肖v ( g ) 且z x ，点 ”7 称为z 对应于x 的一个私邻点，如果f 是在x 中的唯一邻接点，也即 【” n x = 。) 我们定义集合p n ( z ，x ) = 【x z ) 为点z 的x 一私邻域， 简记为p n ( x ) 为方便起见，对任何tsd ，规定p n ( t ，d ) = 【t ( 【叭t 】u 丁) 显然，p a 7 ( 丁，d ) 1 7 d 且p n ( t ，d ) 中的每一个点仅与t 的点邻接，而不与 d 1 的任何点邻接我们称d ( 。) = l ( r ) 1 为点z 的度数，度数为1 和0 的点分 别被称为图的悬挂点和孤立点用( g ) 和c i ( g ) 分别表示图g 的最大度和最 小度 e ( g ) 称为g 的匹配或边独立集，若m 中任意两条边在g 中是不相 邻的- 如粜j ，的某条边与口关联，则称匹配m 饱和顶点u ，或者称u 是m 饱 和的，否贝j ，称u 是m 非饱和的m 中一条边的两个端点称为在m 下是配对的 设1 7 ( ) 表示匹配m 所饱和的点集，若满足v ( m ) = v ( g ) ，则称m 为g 的完 7 2 0 0 5 年上海大学硕士学位论文 8 美匹配若不存在匹配m 7 ，使得l m _ i m i ，则称m 是g 的最大匹配g 的最大 匹配的基数称为是g 的匹配数，记作“( g ) 与匹配相对应的是图的点独立集和独 立数的概念在图g 中，如果两个不同顶点在g 中是不邻接的，则称它们是独 立的如果点集d v ( c ) 中的所有点都是相互独立的，则称d 是g 的独立集 显然，e ( ( d ) ) = 0g 的所有独立集的最大势称为g 的独立数，记为岛( g ) 对于图g 来说，称其子图p = ( 场，e p ) 为一条长为的路，如果有硌= 似j ，口，u k ) 和e p = ( u i l ，v i ) e ：l i k ) 类似地，g 的子图 g = ( e c ) 称为条长为的圈( 或简称为一圈) ，如果有场= ( o ，uh 。讥一1 ) 和e c = ( q 一1 ，地) e ：1 i 一1 ) u ( 讥一l ，u o ) ) 由7 1 个顶点构成的路和圈 通常分别记为r 和g 。，相应的路长和圈长分别为，z 一1 和，。图g 中两点u 和口 的距离等于t 。和”之间最短路上的边的数目，记为d c ( u ，”) ( 或在不引起混淆的情 况下直接简记为d ( u ， ) ) 图g 的直径记为d i a m ( g ) = m n z d ( u ，“) ：“， v ) 所有顶点的度都等于k 的囹g 称为扛正则囤图g 称为完全图如果g 的任意 两个相异点之间都有边相连设s y ( g ) ，称s 为图g 的一个团，如果s 的 导出子图为完全图设x ，ycv ( g ) ，用g ，y 表示顶点集是xu 1 ，边集是 ( z ，) e ( c ) ：z ，y y ) 的二部图一个星形图是指7 7 。2 的完全二部 图，( r ”简单图g 和h 的笛卡尔积图是指具有顶点集v ( g ) xv ( h ) 的简单 图g ) ( 日，其中( 1 5 ，”) 与( u ，u7 ) 相邻当且仅当或者u = u 且( ”， ) e ( 圩) ，或者 w = 矿且( “，u 7 ) e ( g ) 根据不同的应用背景，人们定义了多种控制参数，下面我们给出几个基本类 型的控制参数的定义 定义2 1 1 设s 曼v ( g ) ，s 称为g 的控制集( d o m i n a t i n gs e ) ，如果对任意点 p 7 5 ，c ，至少邻接s 的一个点，即n s j m m b e 呻7 ( g ) 定义为g 的最小控制集的点数 p ( g ) 图g 的控制数f d o m i n a t i o n 即1 ( g ) = 7 t 2 l s l ：s 为g 的控 2 0 0 5 年上海大学硕士学位论文9 制集 基数恰为1 ( g ) 的控制集被称为g 的一个1 集如果s 是g 的控制集， 则称s 控制g 在数学上，研究集合满足某种特定性质的极小和极大性具有重要的意义图 论中的极小和极大性通常可以这样表述设g = ( ke ) 表示一个图，假定集合 s y ( g ) 且s 满足某种性质p ，若对每一个子集s cs ，s 7 都不具有性质尸，则 称s 是极小的；若对每一个scs 7 ，s 都不具有性质p ，则称s 是极大的对于 控制集来说，我们可以得到如下的极小控制集的概念 定义2 1 2 设s 为g 的一个控制集，如果对任意的z s ，都有s z ) 不再 是g 的控制集，则称s 为g 的一个极小控制集g 的所有极小控制集的最大基 数称为g 的上控制数，记为c ( c ) 根据专著【3 7 第6 章中提到的，一种类型的控制参数称为基本的，如果其满 足条件： i 每个连通的、非平凡的图都有一个这种类型的控制集； i i 这种类型的控制集s 可以用其导出子图( s ) 的某些“自然”的特征来定 义 下面没一s 为g 的一个控制集，如果对导出子图( s ) 施加一些限制，可以得到 其他类型的控制参数 ( 1 )全控制集：导出子图( s ) 的最小度至少为1 ； ( 2 )独立控制集：导出子图( s ) 中不含有边； ( 3 ) 连通控制集：导出子图( s ) 为一个连通图 图( ? 的全控制数( 独立控制数和连通控制数) 定义为g 的最小全控制集( 独 立控制集和连通控制集) 的点数，记为m ( g ) ( z ( g ) 和( g ) ) 显然，他们都是基 本类型的控制参数 2 0 0 5 年上海大学硕士学位论文 1 0 定义2 1 3 设s v ( g ) ，称s 为g 的无赘集，如果对每一个顶点 s ，有 n ( ns ) 设s 是g 的无赞集，如果对任意的“y ( g ) s ，都使得 “ u s 不再是g 的无赘集，则称s 为极大无赘集g 的所有极大无赘集的最小基数和 最大基数分别称为g 的( 下) 无赘数和上无赘数，分别记为州g ) 和，凡( g ) 对十图众多的控制相关参数之间的关系，1 9 7 8 年，c o c k a y n e 等人i l b 得出 下面重要的不等式此后，对于如下的不等式的研究文献已有i 0 0 多篇 i r ( c ) ，y ( g ) i ( g ) s 风( g ) c ( c ) ，咒( g )( 2 11 ) 2 2 控制数问题的n p 一完全性结果 根据专著【3 7 】的统计，到1 9 9 8 年已有超过2 0 0 多篇关于图的控制数及其相 关参数算法和复杂性方面的研究文献控制数问题的算法和复杂性方面的研究一 直以来郡是图的控制数理论中的重点研究方向之一下亟我们介绍这方面的一些 基本结果 我们首先介绍n p 一完全性理论中判定问题( d e c i s i o np r o b l e m ) 的概念一类问 题，如果它的每个实例都可以表述为可以用“是”或“否”来回答的形式的话，那 么称之为判定问题例如，图的控制数的判定问题的形式如下： 控制数问题 实例：给出图g = ( k e ) 和正整数k 问题：g 是否存在一个满足条件i s l 的控制集s ? d 8 v t ij o h m o j l1 8 1 1 首先证明了控制数问题是n p 垸全的这是关于图的控制 数理论的一个最基本的复杂性结果，它告诉人们要想找到求解任意图的控制数问题 的多项式时间算法是不可能的于是，人们通过对任意图的条件做一些限定，希望 2 0 0 5 年上海大学硕士学位沦文 找求解某些特殊图类的控制数问题的多项式时间算法当研究了众多的常见图类 后，人们发现求解大多数常见特殊图类的控制数问题仍然是n p 完全的，只有相对 较少的一些特殊图类的控制数问题是多项式可解的对于二部图，d e w d n e y 2 1 、 c h a n g 和n c m h a u s e r1 9 、b e r t o s s i1 2 1 以及另外其他一些研究者都各自独立地证 明了控制数问题在二部图上也是n p 一完全的对于弦图，b o o t h 和j o h n s o u l 5 】首 先证明了控制数问题在弦图上也是n p 一完全的这一结论 刘于一些具有良好的结构性质的特殊图类，人们还是给出过一些求解其控制 数问题的有效算法树就是一个很好的例子第一个关于控制数的算法就是在树 上给山的，并且是线性时间算法 1 4 】_ 还有其他一些重要的特殊图类，例如：区间 图，梯形图，置换图，强弦图，a ，1 一f z e e 图等，它们的控制数问题的都被证明是多 项式可解的 第三章a t f r e e 图类的配对控制集算法 本章我们首先介绍配对控制集的概念以及有关的基本结果，然后引入a t l r e e 图类并研究其相关的结构性质最后，我们给出7 求解a t f r e e 国类的配对控 制集问题的多项式时间算法， 3 1 配对控制集的概念和基本结果 在本节中我们假定所讨论的图为无孤立点的有限简单无向图1 9 9 8 年 h a y s 和s l a 【4 0 1 在全控制集概念的基础上首先提出图的配对控制集的概念 定义3 1 ，l 设p y ( g ) ，p 称为g 的配对控制集( p a i r e d - d o m i n a t i n gs b 吩， 如果p 控制g ，并且导出子图( p ) 含有完美匹配图g 的配对控制数( p a i r e d 一 ( 渤m 乩小8 7 0 协( g ) 定义为g 的最小配对控制集的点数，即( g ) = m 讯【1 p p 是g 的配对控制集) 基数为嘞( g ) 的配对控制集称为g 的一个 r 集 配对控制集的概念的提出是基于如下的应用背景，倘若我们把一个图g 看成 一个监视系统，在它的任意点上都可以放置监控器称图的某个点被监控当且仅 当或者在浚点放置了监控器或者该点通过一条边与相邻的监控器相连由于在每 个点配置监控器要花费一定的费用，要在整个系统( 即图g ) 被完全监控的基础上 使得所需要花费的费用最少的话，这就是通常的图的控制数问题的背景如果我 们进步要求每个监控器同时可以得到至少一个其它监控器的监控保护，这可归 结为圈的全控制数问题特别地，如果要求监控器之间两两可以配对进行协作监 控保护，这便引出了图的配对控制数问题 自t 9 9 8 年配对控制集的概念提出以来，已经有多篇文献研究了这一新型控制 参数，这些研究主要集中在配对控制数的界、配对控制数问题的复杂性以及算法 2 0 0 5 年上海大学硕士学位论文 等方面，下面我们给出相关的主要研究结果 关于对配对控制数界的研究方面，首先有文【4 0 中提到的一个简单结论： ( g ) s 仉( g ) 1 ，( g ) 其它结果有： 定理3 1 1 ( 1 4 0 ) 若图g 不合孤立点，则 t s ( g ) 7 。( g ) ，并且此界是可达的 定理3 1 2 ( 【4 0 】) 若图g 不舍孤立点，则m ，( g ) 曼2 7 ( g ) ，且若- y p ( c ) = 2 7 ( g ) 9 1 , 】g 的每个1 ( g ) 一集同时也是z ( g ) - 集 定理3 1 3 ( 1 4 0 ) 若g 为阶7 z 6 的连通g l ，且j ( g ) 22 ，则( g ) s2 n 3 其他有关配对控制数的界以及有关的板图刻画方面的研究可参见文献f 1 1 ，2 8 、3 9 关于配对控制数问题的复杂度方面，h a y n e s 和s l a t e r 得到如下定理： 定理31 4 ( f 4 0 ) 对于一个给定的图g 和一个正偶数ks i v ( c ) l ，判定( g ) 是否成立是尸一完全的 鉴j ：配对控制数问题的难计算性，人们尝试对于特定图类给出求解此问题的 有效算法到目前为止，有以下结果： 2 0 0 3 年，文 5 6 给出了求解树的配对控制数的线性时间算法； 2 0 0 4 年，文( 4 7 j 给出了求解膨胀树图的日d 对控制数的线性时间算法 下面一节我们介绍a p b e e 图类，最后我们给出求解其配对控制数问题的多 项式时间算法 3 2a t f r e e 图类 a t f r e e 图是一类重要的图类，具有很好的结构和算法特征，如区间图、置换 图、梯形图以及伴随相似图都属于a 2 二f l e e 图类 2 0 0 5 年上海大学硕士学位论文 自1 9 8 9 年以来，c o z n e i l 等人对a t 一胁1c 图类的结构和算法特征做了深入研 究，相关文献可参考1 8 1 由于a i - f l e e 图类的特殊结构，某些在任意图上具有n p 一 完全陆的控制参数问题已经被证明在a m - n 一图类