（运筹学与控制论专业论文）直线簇上区间图的两类控制参数的算法.pdf

2 0 0 5 年上海大学硕士学位论文 摘要 图的控制数理论是图论中一个重要的研究领域，它在计算机科学，通讯科学， 网络理论，电力系统，社会学，特别是在计算机网络和通讯系统研究中有着广泛应 用我们称点集s v 为圈g = ( 虬e ) 的控制集如果对任意的点u v s ，总存在 s 中的一个点与。邻接图g 的控制数7 ( g ) 是图g 的控制集的最小基数在图的 控制数理论研究中，算法复杂性研究是一个十分活跃的研究方向，其中一项重要工 作是在特殊图类上寻找控制数及其相关参数的有效算法区间图是一类著名的特殊 图类，它形成弦图和完美图的子类，它们在解决很多现实问题中有重要作用由于 区间圈具有良好的结构性质，因此许多n p 完全的控制数及其相关参数问题限制 在区间图上都是多项式时间可解的本文我们主要研究了两类控制参数在区间图上 的算法问题，分为两个部分 第一部分：研究了直线簇上区间图的最小独立控制集和最小连通控制集的求解 问题人们已经证明：许多控制相关参数如独立控制数，连通控制数，全控制数的 求解问题，当限制在一条直线上区间图时，基本上都有线性时间算法本文研究了 广义区间图的情况，即多条直线上( 直线簇) 的区间图的最小独立控制集和最小连通 控制集的求解问题对给定的直线簇上区间图的两个模型，我们分别给出了求解上 述两类问题的多项式时间算法 第二部分：研究了包含赋权点的区间图的最小独立控制集和晟小连通控制集的 求解问题对一条直线上的区间图，其上有n 个区间和t 个赋权点，要找此区间图 的最小独立控制集( 最小连通控制集) ，使得其覆盖的点权和最大利用动态规划方 法，我们给出了求解此区间图的最大权最小独立控制集和最大权最小连通控制集的 多项式时问算法 关键词： 图论，控制集，算法，区间图，独立控制集，连通控制集，动态规划 2 0 0 5 年上海大学硕士学位论文 i i a b s t r a c t t i l es t u d yo f d o m i n a t i o nm l dr e l a t e dp a r u n e t e r so fg r a p h si sa ni m p o r t m i tf i e l do f g is p t lt h e o z w h i c hh a sl n a n ya p p l i c a t i o n si oc o r n p u t e r8 c i e r l c e ，e o g i i n t l n i c a - t i o ns c i e n c e ， 1 e t v o li t s t h e e l me l e c t r i cp o w e rs y s t e mm l ds o c i o l o g y , e s p e c i a l l yi nc o m p u t e rn e t w o r k s a l l ( 1c o l l l n l l i l t i c a t i o l ls y s t e m sas e ts vo fv e r t i c e si nag r a p hg = ( ke ) i sc a l l e da d o n l l l l “t h l gs e t e v e r yv e r t e x v si sa d j a c e n tt oa ne l e m e i l to fs t h ed o m i n a t i o n n u l a b e l 7 ( c ) o fag r a p hg i st h el n i l l i n i l i nc a a - d i n a l i t yo fad o n l i n a t i n gs e ti ngt h es t u d y o f ，x l g ( ) li t h m sa n dc o m p l e x i t yi sm e m l i n g f u lm l da c t i v ei n t i l es t u d yo ft l l ed o m i n a t i o n i no b l e l n 。a li t sv k t r i a n t s 、o l l eo fw h i c hi st of i n dt h ee f f i c i e n ta l g o r i t h m so l rs p e c i a le a 。s s e s o fg r a p l l si n t e r v a lg r a p h si saw e l l k , i o w nc l a s so fg r a p h s ，w h i c hf o r m sas u b c l a s so f c 1 1 0 r d a tg r a p h sa n ds t r o n g l yc h o r d a lg r a p h st h e ya j - ev e r yu s e h df o rm o d e l l i n gr e a lw o r l d p i 。o b l e n i s s i n c ei n t e r v a lg r a p t l sh a sg o o dt s t , r o c t u r ep r o p e r t y , t h m lm a n yd o m i n a t i o n * r o d r e l a t e dp i o b l e m s 、w h i c ha r en p c o n l p l e t eo i la r b i t r m yg r a p h s ，a r ep o l y n o m i a ls o l v a b l e w h e i tr e s t + r i o t e dt oi n t e r v a lg r a p h s i nt h i sp a p e r w es t u d ya l g o r i t h m so ft w od o m i n a t i o n p a “nj ( t f f 、r so r li n t e r v a lg r a p h s w h i c hc o n s i s t so ft w op a r t s i nt h ef i r s tp a l t ，w es t u d yt h ep r o b l e mo fc o m p u t i n gm i n i n m mi n d e p e n d e n td o m i n a t - i n gs e ta n di n i n i m u mc o n n e c t e dd o m i n a t i n gs e to fi n t e r v a l so i ll i n e s i th a sb e e np r o v e d t h a tt i l ep r o b l e n mo fm o s td o m i n a t i o nr e l a t e dp a r t u n e t e r ss l l c ha si n d e p e n d m l td o t n i n a - t i o i l ，c o a l l e c t e dd o m i r l a t i o n ，t o t a ld o m i n * l l i o nh a v el i n e a rt i m ea l g o r i t h m sw h e l r e s t r i c t e d t 。i n t e r v s lg r a p h s ( i n t e r v a l so no n el i n e ) ，i nt h i sp a p e r w es t u d yt h ep r o b l e m so nt h eg e n - e r a l i z c di n t , e lv a lg r a p h s ( i n t e r v a l s0 1 1i l m l t i p l el i n e s ) ，t h a ti s ，t i l ep r o b l e m so fc o m p u t i n g 1 t l i a i n l t l l l ti n d e p e n d e n td o m i n a t i n gs e ta n dm i n i n n n nc o n n e c t e dd o m i n a t i i l gs e to fi n t e r v a l so nm u l t i p l el i n e s f o rt h et w og i v e ni n t e r v a lm o d e l s ，v ep r o p o s ep o l y n o m i a l t i m e a l g o r i t h m so fs o l v i n gt h ea b o v et w oi ) r o m e m sr e s p e c t i v e l y i nt l l es e c o r k lp a r t ，v es t u d yt h ep r o b l e m so fc o m p u t i n gm i n i m u l ? li n d e p e n d e n td o r a i n a t i i i gs e ta i i dm i n i n u mc o n r m c t e dd o n l i n a t i n gs e to fi n t e r v a lg r a p h sw h i c hc o n t a i n ss o m e w e i g h t e dp o i n t s f o rag i v e nl i n ew i t h i n t e r v a l sa n dtw e i g h t e dp o i n t s0 1 1i t ，w ew m r tt o f i r l dam i n i m u mi n d e p e n d e n td o m i n a t i n gs e t ( m i n i m u mc o n n e c t e dd o m i n a t i r l gs e t ) o ft h e i r l t e r v a lg r a p h sw h i c hm a x i m i z e st i l es l l g lo ft i l ew e i g h t so ft h ep o i n t sc o v e r e dw ep r o p o s e p o l y n o m i a l t i n l ea l g o r i t h m sf o rt h et w op r o b l e m sb yd y n a m i cp r o g r a m m i n ga l g o r i t h m s 2 0 0 5 年上海大学硕士学位论文 i i i k e yw o r d s ：g r a p ht h e o r y , d o m i n a t i n gs e te f l g o r i t h m s ，i n t e r v a ig r a p h s 、i n d e p e n d e n t d o m i u i l l i i l gs e t , ，i ! 0 1 1 f l t c t ( ! dd o m i n a t i l i gs ( 、t ，f l v n n h l l ( 1p r o g r a n n n h l g 原创性声明 本人声明，所呈交的论文是本人在导师的指导下进行的研究工作，除文了文中 特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果， 参与同一工作的其他同志对本研究所做的任何贡献均已在论文中做了明确的说明并 表示了谢意 虢障慨 日期：研年月尹日 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有权保留论 文及送交论文复印件；允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容 保密的论文在解密后应遵守此规定 魏脚移一名：扁勾买 日期：例年6 月留e l 第一章引言 1 1图的控制参数问题的来源 图论是现代数学的一个重要分支，它在数学学科方面( 如群论、矩阵论、数值 分析、概率论、拓扑学、点阵论和组合论等) 有着广泛的应用，而且由于它所具有 的用图表示的直观性，使得它在信息社会的一些学科领域，例如计算机、运筹学、 系统工程、电子学以及物理学、生物学、社会科学和经济问题等方面的模拟系统中 都发挥了很大的作用 图论中有许多著名问题如最小树问题，最短路问题，网络流问题，图的控制问 题，匹配问题，染色问题，旅行商问题，中国邮递员问题由于它们具有很大的理 论意义和极强的应用背景，因此受到了极大关注，许多专家学者都投入到其中的研 究，从而使图论成为了现代应用数学中一个快速发展的重要分支。 图的控制参数理论是图论中一个非常活跃的研究方向，其思想萌芽最早可以追 溯到四百多年前在印度的一种棋盘游戏，在国际象棋的比赛中，出现了控制集的概 念，棋赛的目的就是用某些棋子覆盖或者控制棋盘上的所有格子1 8 6 2 年d e d a e n i s c h 考虑了控制整个棋盘所需要的最少的皇后个数问题( 皇后能越过任何几个空格，沿 水平线，垂直线或者对角线移动所谓控制整个棋盘是指每个格子或者已由某个皇 后占领，或者可由某个皇后在一次移动后占领) ，这种皇后的最小个数是5 这就是 著名的五皇后问题 4 1 l 它可以看做是控制数的最早雏形如果两个皇后中的一个 皇后所在的格子能被另一个皇后经过一次移动到达，那么称这两个皇后是相互攻击 的，否则就是互不攻击的如果棋盘上的每个格子总能被某个皇后到达而且这些皇 后之问又是互不攻击的，那么满足这种情况的皇后的最小个数是7 事实上，这种 棋盘问题和图的控制集之间有着直接的联系将图的顶点集与棋盘上的似个格子 一一对应，且两个顶点在图中是邻接的当且仅当两个对应格子中的一个格子可以由 位于另一个格子中的皇后所控制，这样的图就称为皇后图，那么控制棋盘中全部格 子的皇后的最小个数就是图的控制数，控制棋盘中全部格子的互不攻击的皇后的最 小数目就是图的独立控制数，即独立控制集的最小基数随后人们对此进行了初步 的数学研究，最初只是集中研究”n 棋盘的各类控制数这些渗透于日常生活中 的数学理论大大地引起了人们对控制数概念的兴趣，1 9 0 1 年a h r e m s 的著作中对此 做了详尽的阐述 现代的图的控制参数理论大家公认的是1 9 5 8 年由b e r g e 和1 9 6 2 年由o ，e 共同 建立的1 9 5 8 年，b e r g e 在其图论专著中首次提出了“控制数”这一概念，而到了 2 0 0 5 年上海大学硕士学位论文 2 1 9 6 2 年，o r ，8 在其图论著作中，正式定义并使用目前一直沿用的控制数方面的术语 “d o l n i a z l t & l gs e t ”和“d o m i n a t i o nn t t m b e r ”1 9 7 5 年c o c k a y n e 和h e d e t n i e n i 概述了 图的控制理论结果( 在这篇综述报告中，他们首次开始使用符号n ( g ) 表示图g 的控 制数，而且一直沿用至今) 在1 9 9 0 年，d i s c r e t em a t h m n a t i c s ( v o l8 6 ) 专门刊出 了一期专辑，全面的介绍了控制参数理论方面的研究进展在1 9 9 8 年，h a y n e s 等人编 写了有关图的控制参数理论的两部专著f 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 ， d o m i m a t i o ni ng r a p h s ：a d v a n c e dt o p i c s ，对1 9 9 8 年以前的各种控制参数的研究 进行了综述。这两本经典专著的出版，为人们深入研究图的控制参数理论奠定了坚 实的撼础，同时也巩固了图的控制集理论在图论中的地位，使得图的控制集理论得 到了空前的发展在2 0 0 0 年a m s 分类目条中专列了一项0 5 c 6 9 为d o m i n a t i n gs e t s ， i n d e p e n d e n ts e t s ，c l i q u e s 这从一个侧面反映了它突飞猛进的发展速度 在过去的的三十年里，尤其是近1 0 年来，图的控制( d o m i n a t i o n ) 理论方面的 研究e ! 成为图论中发展最快的领域之一其快速的发展的原因主要是基于下列三个 因素： ( 1 它在现实世界和诸如“覆盖”、“监控”类数学模型中有着广泛而深刻的指导 意义例如，人们已发现，现实社会中的许多问题与图的控制数( d o m i n a t i o n n u ? ；l b e r ) 有关用图g 表示一个计算机网络，每个点表示一个处理器，每条边表示连接两 个处理器的通信线路现将一个资源集放置于阿络的节点上，使每个处理器可通过 至少一条线路与资源集相连，以获取来自于资源集的指令信息基于费用方面的考 虑，应该选择尽可能少的处理器来放置资源集，被选择处理器数目的最小值就是图 g 的控制数1 ( g ) ( 二) 控制参数的多样性根据实际背景的不同，现已被定义的控制参数也越来 越多，而且随着研究的深入和应用范围的扩大，新的控制参数如雨后春笋般的不断 涌现 ( 三) 图的控制参数判定问题的p 一完全性与组合优化中其它p 一完全问题 有着紧密而自然的关系在特殊图( 如树，弦图，单圈图，正则图，循环图等) 上， 研究各类控制参数的计算复杂性已成为组合优化领域中一个富有挑战性的工作 1 2图的控制参数理论的应用 图的控制参数理论是图论中的一个重要研究领域，不仅在图论方面有着广泛的 应用，而且在其它学科例如计算机网络及其拓扑结构、通讯、监控系统及交通运输 等领域都能看到控制数理论的影子 2 0 0 5 年上海大学硕士学位论文 3 网络监控问题：在一个由多个“节点”和“线”联合而成的复杂网络中，常常 需要设置几个监测点来监控整个网络的运行情况，这些监测点除了要发送自身“节 点”的运行情况外，还要监测它所联结的“节点”情况，这样整个网络的运行情况就 在这些监测点上表现了出来如果希望控制总成本，即要尽量减少监测点的个数， 那么这个应用就是图论中的控制数( d o m i n a t i o nn u m b e r ) 问题上述节点的集合就 是图的控制集如果进一步要求各个监测点之间也互相监测的话，那么就抽象为全 控制集和全控制数( t o t a ld o m i n a t i o nn u m b e r ) 的问题如果这样的大型网络是由几 个小的边互不相联的子网络组成的，各个子网络之间的通信互不干扰，网络中需要 设置一些信息发射点来保持网络的通信( 只要有一个子网络是处于激活状态整个网 络就是激活的) ，这种基于网络稳定性而设置的信息发射点的最少数目就是因子控制 数( 幽c t o rd o m i m l t i o nm l m b e r ) 【1 1 ，2 4 ，4 4 1 编码理论问题：在计算机领域中被广泛研究的编码理论中，我们通常要找其码 长为亿役盖半径为r 的二进制码的最小数k ( n ，r ) 事实上，最小数( 7 i t ) 就 是控制数理论中超立方图的r 一距离控制数( r d i s t a a m ed o m i n a t i o nn u m b e r ) 5 ，2 2 1 显 然，图论中的距离控制数更具有一般意义 保：卫罗马帝国问题：罗马帝国疆土辽阔，需要驻守罗马军团来保卫其城市( 顶点) 的安全如果一个城市没有罗马军团驻守，则认为该城市( 顶点) 是不安全的在紧急 情况下，不安全的城市可以从与其相邻的城市借调罗马军团来维护其安全但是，亚 历山大大帝规定，只有在保证原驻守城市安全的情况下，罗马军团才能调出，即是如 果在调出罗马军团后，原驻守城市变成不安全的，则不能从该城市调出罗马军团， 由于维持庞大的军队费用太高，于是就提出了这个问题，需要多少罗马军团，使得 既能够保证罗马帝国的安全，又能使军费开支最小? 这就是图的控制参数理论中的 罗马控制数( r o m a nd o m i n a t i o nn u m b e r ) 问题，详细内容参见文献【2 0 ，2 l ，3 7 ，3 8 ，5 6 1 等 其他的如广播网的传播数( g o s s i pn m n b e r ) 问题与图的连通控制数与有着密切 的关系【3 1 ，5 7 】- h a y n e s 提出的电力控制数( p o w e rd o m i n a t i o nn u m b e r ) 就是以电力监 视系统为背景来进行研究的【35 】对其中某一具体问题感兴趣的读者，可以追踪查 阅相关文献 1 , 3图的控制参数理论的的主要研究方向 图的控制参数研究有许多成果，概括起来主要涉及到以下四个方面的内容： 控制参数的模型及其相关理论：根据不同的实际背景，可以定义各种不同的 2 0 0 5 年上海大学硕士学位论文 4 控制参数。现已定义的控制参数有几十种之多，随着研究的深入和应用的发展，新的 参数不断涌现从经典的控制数，独立控制数( i n d e p e n d e n td i m i n a t i o nn t t n ，b e r ) ，连通 控制数( c o n n e c t e dd o m i n a t i o nn u n l | b e l ) ，全控制数( t o t a ld o m i n a t i o nn u u t b e r ) 等参数， 到现在广泛研究的有效控制数( e f f i c i e n td o m i n a t i o nl u l n l k r ) ，距离控制数( d i s t a n c e d o m i t i o l in u m b e r ) ，完美控制数( p e r f e c td ( ) m i n a t i o nn u m b e r ) ，限制控制数( r e s t r i c t e d d o m i n a t i o nn u i n b e r ) ，电力控制数( p o w e rd o m i n a t i o nn u m b e r ) 因子控制数( f a c t o rd o m i n a t i o nn l m l b e r ) 约束数( b o n d a g en u m b e r ) 等参数从函数的观点来考虑控制问题，以 便更好地利用数学工具，一些研究者提出了控制函数( d o m i n a t i n gf l m e t i o n ) 的概念， 于是又出现了负控制数( m i n u sd o m i n a t i o nm n n b e r ) ，符号控制数( s i g n e dd o m i n a t i o n k l t n b e r ) 多数控制数( m a j o r i t yd o m i n a t i o nn u n f l ) e r ) ，符号全控制数( s i g n e dt o t a ld o r a i n a t i o nn u m b e r ) ，符号2 一独立数( s i g n e d2 - i n d e p e n d e n c en u m b e r ) ，全负控制数( m i n u s t o t a ld o m i n a t i o nn u m b e r ) 等函数控制数 控制参数之间的相互关系：图的结构性质和参数的定义方式决定了各种控 制参数之间具有某种必然的关系，因此研究它们之间的相互关系是一个重要的方 向如在1 9 7 8 年由c o c k a y n e ，h e d e t n i e m i 和m i l l e r 【3 3 】等人提出的著名不等式链； ( g ) 1 ( g ) z ( g ) m ( g ) ( g ) 7 t p ( a ) - j p 一复杂性及算法研究：对某种控制参数，通常要考虑它的判定问题在任意 图上的n p 一完全性，即是否存在多项式时间算法如果某种控制参数的判定问题不 是n p 一完全的，则研究者希望找到最优算法事实上，几乎所有控制参数的判定问题 在一般图上都是n p _ 完全的因此，对) 一完全的控制参数问题，在具有特殊结构的 子类图上寻找多项式时间算法，或者在一般图上寻找近似算法和启发式算法是人们 的主要研究方向之一人们通常研究的图类有树( t r e e ) ，区间图( i n t e r v a lg l a p h s ) ，置换 图( p e l n m t a t i o ng r a p h s ) 。强弦图( s t r o n g l yc h o r d a lg r a p h s ) ，弦二部图( c h o r d 出一b i p a r t i t e g r a p h s ) ，对偶弦图( d u a l l yc h o r & dg r a p h s ) ，可分图( s p l i tg r a p h s ) ，块图( b l o c kg r a p h s ) ， 仙人掌图( c a c t a sg r a p h s ) 等 控制参数的界的估计及极值图类的刻划：对于n p 完全问题，寻找上下界是 一项重要工作，通过图的各种参数如顶点个数，边的个数，最大度，最小度，直径，半 径，围长对控制参数的界进行估计，对达到上下界的极值图进行刻画等都是非常有 意义的这方面的工作开始的最早，成果也是比较多的，如首先由j a e g e r 和p a y a n 4 0 1 提出著名的n o r d h a u s g a d d a m 型不等式，( g ) + 彳( g ) ，i + 1 ，1 ( g ) 可( g ) m 2 0 0 5 年上海大学硕士学位论文 5 1 4 本文的主要工作 医司图( i n t e r v a lg r a p h s l 是一种具有特殊结构性质的图类，许多n p 一完全的控 制参数问题在区间图上都有多项式时间算法本文的主要工作是研究了控制参数在 区间图上的算法问题，分为两个部分 第部分：研究了直线簇h 区间图的独立控制数和连通控制数的求解问题对 于一条直线l 区问图的控制数，独立控制数，连通控制数，全控制数，控制团的求 解问题，c 蛔n g 1 3 ，f a r b e r 【2 7 卜r a n l n l l i l g m r l 和r a t l g a n 5 1 1 ，b r a n d s t d t 和k r a i t s c h 1 0 】 等人证明了它们是在多项式时问内可解的本文讨论了两种推广的情况，即是考虑 了多条直线上( 直线簇) 的区间图的独立控制数和连通控制数的求解问题对给定 的直线簇上区间图的两个模型，我们分别给出了求解两类控制参数的多项式时间算 法 第部分：研究了包含赋权点的区间图的最小独立控制集和最小连通控制集的 求解问题对一条直线上的区间图，其 二有n 个区间和t 个赋权点，要找此区间图 的最小独立控制集( 最小连通控制集) ，使得其覆盖的点权和最大，即是寻找此区间 图的最大权最小独立控制集( 最大权最小连通控制集) 利用动态规曳方法，我们给 出了求解此区问图的最大权最小独立控制集和最大权最小连通控制集的多项式时问 算法 本文下面的内容是这样安排的，第二章讨沧了图的控制参数的基本概念和算法 研究进展情况，第三章和第四章分别讨论了直线簇上区间图的最小独立控制集和最 小连涵控制集的求解问题，第五章讨论了包含赋权点的区间图独立控制集和连通控 制集的求解司题 制集的求解司题 第二章图的控制参数的基本概念和算法研究进展 2 1图的控制参数的基本概念 为了叙述方便，首先我们引入一些定义和记号设图g = ( v ( g ) ，e ( g ) ) 是 无向的，简单有限图，其中v ( o ) = ，”。) 表示图g 的顶点集( v e l 。t e xs e t ) ， e ( c ) = - ，e 。 表示图g 的边集( e d g es e t ) 图g 的阶数n = 【v ( c ) 1 对图g 的 任意两个顶点，若它们有边相连，则称这两个顶点是邻接( a d j a c e n t ) 的反之，若它 们没有边相连，则称这两个顶点是独) - ( i n d e p e n d e n t ) 的我们称图g = ( v 1 ，e ) 是图g = ( k e ) 的子图，若g 。的所有顶点和边都属于g ，即u e 设 x 矿( g ) 我们称以x 为顶点集的g 的最大子图为x 在g 中的导出子图，记为 g x 也就是说，x 的两个顶点在a x 1 中邻接当且仅当它们在g 中邻接 图g 中点。的邻域定义为n ( x ，g ) = 妇：x y e ( g ) ) ，的闭邻域为n i x ，g 】= ( 。，g ) u 和) 更一般地，对任意的x v ( g ) ，我们定义( x ，g ) = u 。x u ( x ，g ) ， ，g = n ( x ，g ) ux 在不引起混淆的情况下，上述符号可分别简记为( 。) m n ( x ) 和n i x 顶点在g 中的度d ( x ，g ) = l n ( x ，g ) l ，简记为d ( z ) 度数为1 和0 的点分别被称为图的悬挂点和孤立点 如果图g = ( v ，e ) 的某些顶点与边可以排成一个非空有限交错序列p ( v o ，) = u o ，e l ，m ，其中饥k 岛= “啦) e ，ls i ，则称此序列为由v o 到讯 的一条迹( ”n 伽若和u 相等，别称此迹为闭的若序列中的任意两个顶点都 不相等，则称此序列为由”o 到毗的一条y $ ( p a t h ) ，v o ，分别为路的起点和终点 若一条路的起点和终点相等，则称此路为回路或者圈( c y d e ) 若图g 的任意两点之 间都有路相连，则称图g 是连通( c o n n e c t e d ) 的连通的无圈图称为树( t r e e ) 其它 未加定义的术语和记号可参看文献阶 在以下的叙述中，我们总假定s v ( a ) 设s 满足某种性质p ，若对每一个 s 。cs ，s 都不具有性质p ，则称s 是极小的若对每个s 7 ds ，s7 都不具有性质p ， 则称s 是极大的下面我们给出几类主要控制参数的定义 定义2 1 1 设s y ( g ) s 称为g 的控制集( d o m i n a t i n gs e t ) ，若v ( g ) s 中的 每一个点，至少与s 的一个点相邻接，也即n s 1 = v ( g ) 设s 为g 的控制集，如果 对任意的 s ，都使得s 扣 不再是g 的控制集，则称s 为g 的极小控制集图 g 的控制数( d o m i n a t i o nn u r r 。b e ? ) 定义为图g 的极小控制集的最小基数，记为 ( g ) 即- y ( g ) = m i n i s l ：s 为g 的极小控制集) 图的上控制数( u p p e rd o m i n a t i o nn ? t m b e r ) r ( c ) = ，a x i s l ：s 为g 的极小控制集l 2 0 0 5 年上海大学硕士学位论文 7 定义2 1 2 设s y ( g ) ，s 称为g 的一个独立集( i n d e p e n d e n ts e t ) 若s 中的任 意两个点都不邻接设s 是g 的独立集，如果对任意的u v ( c ) s 都使得s u u ) 不再是g 的独立集，则称s 为g 的极大独立集图g 的独立数( i n d e p e n d e n tn u m b e r ) 定义为图g 的极大独立集的最大基数r 扎j 定义2 1 3 设m e ( g ) ，m 称为g 的一个匹配( m a t c h i n g ) 若m 中的任意两 条边都t , 4 1 t 接设m 是g 的匹配，如果对任意的e e ( g ) m 都使得m u e 不 再是g 的匹配，则称m 为g 的极大匹配圈g 的匹配数( m a t c h i n g 、l b e r ) 定义 为图g 的极大匹配的最大基数r 势j 控制集的概念提出以后，许多专家学者对它显示出极大的兴趣，在研究控制数 的同时，根据不同的应用背景，人们又提出了各种不同的相关参数，下面我们给出 几种主要的控制参数的定义，为了叙述方便，我们用最小来表述，最小控制集指的 是极小控制集中基数最小的控制集，即是基数最小的控制集其它的概念如最小独 立控制集是基数最小的独立控制集，最小连通控制集是基数最小的连通控制集，等 等以致类推 定义2 1 4 若s 为g 的控制集，且为g 的独立集，则称s 为g 的独立控 制集( i n d e p e n d e n td o m i n a t i n gs e t ) ，最，1 、独立控制集的基数称为g 的独立控制数 ( i n d e p e n d s n td o m i n a t i o nn u m b e r ) 定义2 1 5 若s 为g 的控制集，且s 的导出子圈c s 1 是连通的，则称s 为g 的连通控制集( c o n n e c t e dd o m i n a t i n gs e t ) 最小连通控制集的基数称为g 的连通控 制数( c o l y r l , e c t c dd o m i n a t i o nn u m b e ，) 定义2 1 6 若s 为g 的控制集，且s 的导出子图c s 1 没有孤立点，则称s 为g 的全控制集( t o t a ld o m i n a t i n gs e t ) 最小全控制集的基数称为g 的全控制数 ( t o t a ld c r m i n a t i o nn u m b e r ) 定义2 1 7 若s 为g 的控制集，且s 的导出子图c s 含有完美匹配，则称s 为 g 的配对控制集( p a i r e dd o m i n a t i n gs e t ) ，最小配对控制集的基数称为g 的配对控 制数( p o i ，c dd o m i n a t i o nm 6 ) 目前，人们大约定义了7 5 种与控制相关的参数，随着研究的深入，各种新的参 数不断涌现，其它未加定义的参数，术语和记号可参看文献3 3 ，s 4 1 2 2控制数及其相关参数的算法复杂性 本节我们简要地介绍n p 一完全理论及关于控制数的一些p 一复杂性结论 有关p 复杂性的详细论述，请参阔 2 9 2 0 0 5 年上海大学硕士学位论文 8 2 2 1 算法复杂性 算法复杂性是对于每一个可能的输入规模吼解决此输入规模的最坏可能的实 例所需要的时间( 基本运算步数) 它是关于实例输入规模n 的函数，用来表示算法 的时间需求比如7 泸，2 ”，n l o g n 等 设巾。) ，9 ( n ) 是定义在正整数上的正实值函数若存在常数c 0 ，使得当n 足 够大时有l ，( n ) isc i g ( n ) l ，则称函数，( n ) 是以函数9 ( n ) 为界的，记为，( n ) = 0 ( 口( n ) ) 我们称一个算法是多项式时间的，若此算法复杂性是以多项式为界的，即是此算法 的复杂性随输入规模的增加而多项式地增长反之，我们则称此算法是指数时间的 一般来说，人们认为多项式时间算法是有效算法，而指数时间算法是无效的 一个组合问题如果已经找到了多项式时间算法，那么就称它是多项式时间可解 问题把所有这样的问题集合记为p ，就构成p 类问题如果一个问题没有找到多项 式时间y t ：法，只觉上感到它很难，但又无法证明其不存在多项式时间算法，此时把 归结为一个深奥的数学猜想：p 一完全理论这类n p 一完全问题具有下述十分有 趣的性质 1 任何p 一完全问题都不能用已知的多项式算法求解( 尽管许多有才华的研 究人员做了几十年坚持不懈的努力，情况仍然如此) 2 若任何一个n p - 完全问题有多项式算法，则一切n p 完全问题都有多项式 算法 根据这两个事实，很多人猜想任何n p 完全问题都没有多项式算法但是无人 能证叽事实上现在人们相信，如果不发展全新的科学技术就证明不了这个猜想 n p 完全问题概念的实际意义在于人们普遍相信，难计算是这样一些问题的固 有性质；因此它们不可能用有效的算法求解；所以可以正确地求解n p - 完全问题 的任何货法，在最坏的情况下也需要指数量级的时间，从而除规模很小的实例外， 是不实用的因此对一个新的组合最优化问题，在找不到解它的有效算法时，研究 人员可以选择证明它是n p 完全的这样做有两个明显的好处；首先可以避免研 究者本人和其它研究人员白花力气去找有效算法，此外，一旦知道问题是p 完全 的，人们可能会选择其它途径来研究此问题( 如找该问题的近似算法，启发式算法 或者对原问题的具有特殊性质的子问题寻找多项式算法) 2 2 2 控制数及其相关参数的n p 一复杂性 首先，我们考虑控制数问题的n p 一复杂性，其判定问题形式如下： 控制集问题：给定一个图g = ( u e ) 和个正整数，问是否存在图g = ( u e ) 2 0 0 5 年上海大学硕士学位论文 9 的一个控制集，其元素个数小于等于k ? d t “，。7 。，n 2 9 1 首次证明了控制集问题的p 一完全性 定理2 2 1 膨9 图的控制集问题是p 一完全的 接下来人们把目光转向了特殊图类，希望能在某些结构性质比较好的图类中找 到多项式时间算法d e w & l e y 2 5 ，c h m l g 和n c m h a u s c r 1 6 1 ，b e r t o s s i 2 】和其它一些学 者各自独立地讨论了限定在二部图( b i p a a - t i t eg l a p h s ) 上控制集问题，他们得出如下 结论 定理2 22 胆5 1 6 2 限制在二部图上，控制集问题仍然是p 一完全的 b c ) o t l l 和j o h n s o nf 7 1 首次讨论了限定在弦图( c h o r d a lg r a p e s ) 上控制集问题， 得到如下结论 定理2 2 3 俐限制在弦图上，控制集问题仍然是n p 一完全的 第一个控制集算法是在树上给出的，1 9 7 5 年，c o c k a y n e ，g o o d m a n 和h e d e t n i e l n i g 给出了一个计算不赋权树的最小控制集的线性时间算法随后，人们又陆续发现了 其它一些有多项式算法的图类，如区间图，块图，定向路图( d i r e c t e dp a t hg r a p h s ) ，梯 形图( t r a p e z o i dg r a p h s ) ，仙人掌图( c a c t u sg r a p h s ) ，共图( c o g r a p h s ) ，置换图，强弦图， 对偶弦图，a t f r e e 图等对于各种不同的特殊图类，其控制集问题是属于p 问题 或是属于n p 。问题，已经有很多研究成果，详细的结论可查阅c o r n e i l 和s t e w a r t 的论文【2 , 3 】和h a y n e s 等人编写的两部专著【3 2 ，a 4 1 其次，我们给出几类主要的控制相关参数的n p 复杂性结果 无赘( i r r c d u n d a n c e ) 集问题；给定一个图g = ( v - , e ) 和一个正整数，问是否存 在图g = ( ve ) 的一个极大无赘集，其元素个数小于等于k ? 定理2 2 4 心8 图的无赘集问题是n p 一完全的 独立控制集问题；给定一个图g = ( ue ) 和一个正接数k ，问是否存在图g = ( ke ) 的一个独立控制集，其元素个数小于等于? 定理2 2 5 偿9 图的独立控制集问题是n p 一完全的 独立集问题：给定一个图g = ( k e ) 和一个正整数，问是否存在图g = ( k e ) 的一个独立集，其元素个数小于等于? 定理2 2 6 偿目图的独立集问题是n p 一完全的 2 0 0 5 年上海大学硕士学位论文 l o 上控制集问题：给定一个图g = ( k e ) 和一个正整数k ，问是否存在图g = ( k e ) 的一个极小控制集，其元素个数小于等于 定理2 2 7 l 到图的上控制集问题是尸一完全的 上无赘( u p p e ri r r e d u n d e a l c e ) 集问题 问是否存在图g = ( ke ) 的一个无赘集， 给定一个图g = ( k e ) 和一个正整数 其元素个数小于等于a ? 定理2 2 8 胆8 图的上无赘集问题是p 一完全的 定理2 ，2 9 心州即使限制在线图伸1 eg r a p h s j 和线二部图( 1 i n e y t p h sf