（运筹学与控制论专业论文）图的控制数及其相关参数.pdf

摘要 在过去的的三十年里，圄论中发展最快的领域也许题图的“d o m i n a t i o n ”的研究这 一研究领域出现快速发展的西素主要青三个：( ) 它在现实落弊和诺如“覆盏“位置 确定”类数学问题中广泛而深刻的应用例如目前编码理论中正搬研究的码长为n 覆盖 半径为r 鹣二遗黼稻的爨，j 、数n ，r ) 蠢楚蚕静羧麓集璎论孛怒立方蚕熬r 一距蕊控裁 数，显然，图论中的距离控制数髓具有一般意义现在，人们已发现图的控制集理论可 广泛应震予缡玛褒论，嚣蒸祝释学，逶蘩遮终，黧撬系统鼗社会鹅络等毽沦与实筏中+ ( = ) 控制参数定义类型的多样性根据实际背景的不同，现已定义的控制参数有几十种 之多，瑟艇夔着戮突懿深入窝应援豹激发，毅戆参数如霹詹褰笋。不断濑现。( 三) 基的 控制参数确定问蹶的n p 。完全性与其它组合优化中只完全问题紧密而自然的荧系 农特殊墨( 鲤弦图，馨弧爨，区蝴图，a t - f r e e 图警) 上，寻找各类控制参数的多项式时 间算法已成为组含优化领域中一个引入入胜而富宥挑战性的研究方向 本文所做工佟主要包括以下艘个部分：( 1 ) 几类控制参数界的确寇及与相关图参 数的关系；( 2 ) 极图的结构性质；( 3 ) 函数掩稍数的莽的确定；( 4 ) 匿静中心霸 平衡点问题 t 在第二章，我们讨论了经舆控制数的界和极图的刻画问题，主要做了以下几个方 藤懿工露： 1 9 9 3 年，r e e d 7 0 1 剿爱“鼹覆盖”技术证骥了最小度至少为3 的阶图其控割数 叮( g ) 不趟过m 我们通过改进这一技术进一步谶化了上述结论，证明了最小度至少为 2 灼n 阶魍其控制数- y ( a ) 不超过! ! 专幽，这里是图中度数为2 的点的数目作为这 一结果的应用，证明了最小度至少为3 的n 阶鬻荚卜限制控毹数浮，哟s 鲰学堂( 有关结果已投d i s c r e t em a t h e m a t i c e s ) 对任意连遴图g ，控翩数、匹配数和覆盖数满足不等关系：7 ( g ) sf l ( a ) 墨。( g ) 。 我们首先证明了当- r ( a ) 一z ( g ) 时，g 的最小度一定不超过2 ，进一步对7 ( g ) = 卢( g ) 藏5 ( g ) 一2 的鹜给密了完全裁瑟( 有关络莱已被数学避震录嚣) 。其次，对最，l 、麦隽 1 的几类特殊图也给出了刻画 尽管已麓遂当匿鹣簸，j 、度，j 、予3 时，鎏魏金控餐数槐与嚣配数零不可毙较( 见文 8 0 ) ，但我们证明了下列麓要结论；对任意最小魔不小于4 的无爪图g ，有m ( g ) 曼卢( g ) 成立遴一步我髓猿溅对最小发为3 戆任意塑遮结论泼立。没意费事嶷声 g ) sl ! 譬盟， 因此上进结果部分证明- f 由f a v a r o n 提出的关于全控制数猜想；m ( g ) g 峪掣 第二章的最后，我们建立了k 一控制数的一个n o r d h a u s g a d d u m 型不等式，由此 解决了鑫h a r a r y 等( 觅文 2 9 ) 1 9 9 6 牮提出静一个关于双控制数的猜想( 有关结果发装 在d i s c r e t ea p p l i e dm a t h e m a t i c e s 1 3 6 ( 2 0 0 4 ) ) * 第三章讨论了瞬的配对控制数问题，达一概念由h a y n e s 和s l a t e r ( 见文 4 0 ) 在 1 9 9 8 年提出弗进行研究我嬲徽了以下三个方嚣教工露： 对最小度5 ( a ) 2 且 y ) i 6 的连通图g ，h a y n e s 矛玎s l a t e r 证明了其配对控制 数坳( g ) 不超过；m 我们给懑了却( g ) = ；n 的极蚕刻蕊 给出了众控制数与配对控制数相等的树的一类构造性刻画( 该结果已通过a u s t r a l a s i m lj o u r n a lo fc o m b i n a t o r i c s 兹一事) ， 讨论了配对控制数( g ) 和它朴图的色数x ( g 。) 之间的关系，证明了除几类图外 每一令连遭銎黪配怼控麓数不超过它敬毪数热1 t 第四章碾究了蹬的函数控制数，主要得到了以下结果 讨论了瞬的负控制数的下界荫先证明了1 9 9 9 年由d u n b a x 等e 1 8 j 提出的关于偶 潜受藏涮数静下界魏个猜想，瑟瑟 鼍意* 给耩匿g ，7 一( 回4 ( 西再“f 一1 ) 一m 其次， 我们也建立了偶图负撩制数的另外一个可达下界 7 叩) 陬一( 掣十而躲” 这墨黩一m i n d ( v ) l v x ，5 y m i n d ( v ) i v y 建立了任意n 阶图符号一控制数的一个下界 孙。一坚圃譬必 这一襞皋蕴会了在茂之羲褥到瓣蓬懿符号控翻数寒多数控裂数在正裂鍪上豹爨有下器 结果( 上述有关结果发表在t h e o r e t i c a lc o m p u t e rs c i e n c e 2 9 6 ( 2 0 0 3 ) ) 2 0 0 2 年，h e n n i n g 4 3 秘究了壶z e l i n k a 8 5 早先攫出的褥号2 一独立数概念，并建 立了它的几个上界谯这里我们又给出了它的另外几个新上界此外，利用分析方法建 立了n 阶多部凰的最好可能上界，证明了对任意n 阶r 一郝图g 积眺五3 f + n - ( 乌) _ 一五4 y f 有关结果发表在a r sc o m b i n a t o r i a 6 9 ( 2 0 0 3 ) ) l i * 第五鼙讨论了黼的中心和平衡赢蟊题 夫程飘注意龚这襻一个重要攀实t 投疆不冠测度椽准定义驰墨鲍“中心”概 念，多数情况下满足在树中由一个点溅两个邻接点所组成，而在任徽连通图必在同一个 挟中，也即这些中心点通卷聚集在一起+s l a t e r 7 4 1 黉证瞬樾的自一中心c ( t 、) 由个 点或两个邻接点所组成，我们试图诚明对任意连通圈它的扣中心必在同一个块中，但 遗憾的是我们仅证明了对含薅个块的连通圈这一结论是成立的( 这一结果发表在j s y s t e m ss c i e n c ea n di n f o r m a t i o n 1 ( 4 ) ( 2 0 0 3 ) ) 1 9 9 9 邻，r e i d 7 1 1 提出了一类树的“中心”概念，即树的平衡点他利用所谓的 “双定向技术”证髓了裙静平衡点由一个点竣两个锑接点繇缀成，我艇稻焉不等关系给 出上述结果的一个简化处理( 这一结果已被d i s c r e t em a t h e m a t i c e s 录用) 关键词；图；控制集；掇制函数；匹配；中心；平衡点 i i i a b s t r a c t w i t h i nt h el a s tt h i r t yy e a r s ，c o n c u r r e n tw i t ht h eg r o w t ho fc o m p u t e rs c i e n c e ，g r a p ht h e o r yh a s s e e ne x p l o s i v eg r c ) w t h ，p e r t l a p e st h ef a s t e s tg r o w i n ga r e aw i t h i ng r a p ht l l e o q ：i st h es t u d yo f d o m i n a t i o ni ng r a p h s t h er a p i dg r o w t hi nt h en u m b e ro fd o m i n a t i o np a p e r si sa t t r i b u t a b l e l a r g e l y t ot h r e ef a c t o r s ：1 ) d i v e r s i t yo f a p p l i c a t i o n st ob o t hr e a l - w o r l da n do t h e ri n h e & a t i c a l c o v e r i n g o r f a c i l i t yl o c a t i o n p r o b l e m s ，s u c ha sc o d i n gt h e o r y , c o m p u t e rc o m m u n i c a t i o n n e t w o r k s ，m o n i t o rs y s t e m ，l a n d i n gs u r v e y i n ga n ds o c i a ln e t w o r kt h e o r y ( 2 ) t h ew i d ev a r i e t y o fd o m i n a t i o np a r a m e t e r st h a tc a nb ed e f i n e d ，a b o u t4 0 4 0d i f f e r e n tt y p e so fd o m i n a t i o nh a v e b e e nd e f i n e d 3 ) t h en p c o m p l e t e n e s so ft h eb a s i cd o m i n a t i o np r o b l e m ，i t sc l o s ea n d n a t u r a l r e l a t i o n s h i p st oo t h e rn p - c o m p l e t ep r o b l e m s ，a n dt h es n b s e q u e n ti n t e r e s ti nf i n d i n gp o l y n o m i a l t i m es o l u t i o n st od o m i n a t i o np r o b l e m si ns p e c i a lc l a s s e so fg r a p h s i nt h i sp a p e r ，w ep a yo u ra t t e n t i o nm a h f l yo nt h ef o l l o w i n gf o u rp a r t so fd o m i n a t i o ni n g r a p h s ： d e t e r m i n i n gt h eb o u n d so ns e v e r a ld o m i n h t i o np a r a m e t m 等a n di m e s f i g a t i n gt h er e i n - t i o n s h i pb e t w e e nt h ed o m i n a t i o np a r a l ，l e t e r sa n do t h e rg r a p h i c a lp a r a m e t e r s c h a r a c t e r i z i n gt h e e x t e r n a lg r a p h sf o ri n e q u a l i t i e si n v o l v i n gi nd o m i n a t i o np a r a m e t e r s d e t e r m i n i n gt h eb o u n d so i ld o m i n a t i n gf u n c t i o n si ng r a p h s d i s c a s s i n gs o m ep r o b l e m so n c e n t r u ma n db a l a n c ev e r t i c e si ng r a p h s + nc h a p t e r2 ，w ei n v e s t i g a t et h eb o u n d so nc l a s s i c a ld o m i n a t i o na n dd m r a c t e r i z es o l n e e x t r e m a ig r a p h sf o ri n e q u a l i t i e si n v o l v i n gi nd o m i n a t i o np a r a m e t e r s i n1 9 9 3 ：r e e di n 【7 0 1p r o v e dt h a te v e r yg r a p ho fo r d e r w i t hm i n i m u m d e g r e ea t l e a s t t h r e eh a sad o m i n a t i n gs e to fa tm o s t 警v e r t i c e s i ns e c t i o n2 2 ，b ym o d i f y i n gr e e d s ；d i s j o i n t p a t hc o v e r i n g ”m e t h o d w ei m p r o v er e e d sr e s t f l t t o7 ( g ) 甄譬埘，w h e r e 场i st h ev e r t e xs e t o fd e g r e e2 ，i fgi sag r a p ho i lnv e r t i c e sw i t h5 f g 乏2 。a sa na p p l i c a t i o no fa b o v er e s u l t ， w eo b t a i na l lu p p e rb o u n d ( g ，y ) 曼挫学出o nk - r e s t r i c t e dd o m i n a t i o nn u m b e ro fag r a p hg w i t ho r d e r 魏a n dm i n i m u md e g r e ea tl e a s tt h n e e + 强i sw e l l - k n o w nt h a t7 f s s 芦g s 娃 g ； h o l d sf o ra n yc o n n e c t e dg r a p hg i ns e c t i o n2 , 3 w eg i v eac o m p l e t ec h a r a c t e r i z a t i o no ft h o s e g r a p h s0 f o rw h i c h7 ( g ) = 蹿g a n da ( c = 2 ，f u r t h e r m o r e ，w ei n v e s t i g a t es o n i cs p e c i a lt y p e s o fg r a p h s6 lf o rw h i c h7 ( g ) = 卢( g ) a l t l m u g hi 碉s h o w st h a tt h ep a r a m e t e r s 零a n d 愧n o tc o m p a r a b l ef o rg r a p h sw i t h m i n i m u m d e g r e ea tm o s t2 ，y e ti ti sl i k e l yt oe o l l l p a r e 辟w i t hm f o rg r a p h sw i t hl a r g em i n i m u m d e g r e e 。i ns e c t i o n2 , 4 ，w eo b t a i nt h a ti fg i sc l a w f r e eg r a p h a n d f g ) 4 ，t h e n 镄( g ) 参 s ) t h i si m p l i e st h a tf a v a r o n sc o n j e c t u r ei st r u ef o rc l a w f r e eg r a p h sw i t hd ( d ) 4 w eb e l i e v e t h a tt h er e s u l ti st r u ef o ra n yc l a w - f r e eg r a p hw i t hm i n i m u m d e g r e e3 ，a l t h o u g hw e v o t en o t a b l et os e t t l ei t i fi ti st r u e a ne x a m p l ei sg i v e nt oi l l u s t r a t e st h et i g h ti n e q u a l i t y , i nt h ee n d 艇c h a p t e r 2 ，w ee s t a b l i s ht h en o r d h a u s - g a d d u mi n e q u a l i t i e so n k - d o m i n a t i o n n u m b e ro fg r a p h s ，w h i c hs t r e n g t h e n st h ec o n j e c t u r eo nd o u b l ed o m i n a t i o nn u m b e ro fg r a p h s p r o p o s e db yh a r a x ya n dh a y n e s 2 9 li n1 9 9 6 i n c h a p t e r3 ，w e i n v e s t i g a t e t h e p a i r e d - d o m i n a t i o n n u m b e r i n g r a p h s ，w h i c h w a s i n t r o d u c e d b yh a y n e sa n ds l a t e ri n 4 0 】i n1 9 9 8 h a y n e sa n ds l a t e ri n 4 0 】s h o w e dt h a tt h ep r o b l e mo fd e t e r m i n i n gt h ep a i r e d - d o m i n a t i o n n u m b e r 固o f a na r b i t r a r y g r a p h i sn p - c o m p l e t e ，a n df o ra n yc o n n e c t e dg r a p hg w i t ho r d e r n 6a n dd ( g ) 2t h e yp r e s e n t e da nu p p e rb o u n d2 n 3o f7 p ( a ) i nt e r m so f o r d e ro fa g r a p h h o w e v e r ，t h ea u t h o r so n l yg i v ea ne x a m p l e 国t os e et h a tt h ea b o v eb o u n d i ss h a r p ，a n dg i v e af a m i l yo fg r a p h sf o rw h i c h7 p ( a ) a p p r o a c h2 n 3f o rl a r g en i ns e c t i o n3 1 ，w ew i l lg i v ea c o m p l e t ec h a r a c t e r i z a t i o no fg r a p h sf o rw h i c h g = 2 n 3 。 i ns e c t i o n3 2 ，w ep r o v i d eac o n s t r u c t i v ec h a r a c t e r i z a t i o no ft h o s et r e e sw i t he q u a lt o t a l d o m i n a t i o na n dp e l t e d - d o m i n a t i o nn u m b e r s ； t ns e c t i o n3 , 3 ，w e i n v e s t i g a t et h er e l a t i o n s h i pb e t w e e n t h ep a i r e d - d o m i n a t i o n n u m b e r 却( g ) o fag r a p ha n dt h ec o l o r i n gn u m b e ro fi t sc o m p l e m e n t w es h o wt h a i ；勘g ) 墨x ( a 。) + l 融 a n yc o n n e c t e dg r a p hg w h o s ec o m p l e m e n ti s 玛3 * f r e e ，e x c e p tf o rs e v e r a lf a x n i l i e so fg r a p h s i nc h a p t e r4 ，w ed i s c u s st h ed o m i n a t i o nf u n c t i o n si ng r a p h s ，a n do b t a i nt h ef o l l o w i n g r e s u l t s i n1 9 9 9 ，d u n b a re 末越。i l 筏i n t r o d u c e dt h ec o n c e p to fm l n r sd o m i n a t i o na n dp o s e d 垮e c t u r e dt h a tf o ra n yb i p a r t i t eg r a p hgw i t ho r d e r 他，t h em i n u sd o m i n a t i o nn u m b e r7 一( g ) 4 ( , h - - + - f 一1 ) n 。i ns e c t i o n4 2 p r o v ef l m tt h ec o n j e c t u r ei s t r u ea n de s t a b l i s h o t h e r a t t a i n e dl o w e rb o u n d7 - ( g ) 犯一( i 墨擎儿+ 一 艘。盟 、1 1 f o r ab i p a r r i t eg r a p hg 端( x ，y ) w i t ho r d e r w h e r e5 x 一? n i 蠢口) x ，西= m i n d ( v ) t v y ， t h ec o n c e p to fk - s u b d o m i n a t l o nn u m b e r 讥sw a si n t r o d u c e db yc o c k a y n ee ta 1 1 1 1 i nt h e s p e c i a lc a s e s = l v i ，溉$ i st h es i g n e d d o m i n a t i o nn u m b e r g ，c o c k a y n ee t 畦：e s t a b l i s h e d8 s h a r pl o w e rb o u n do n 佻s f o rt r e e s i ns e c t i o n4 3 w es h o wt h a tf o ra n yg r a p hg o fo r d e rna n d s i z ee ，佻s 一墼睦i 辫b ya b o v et h er e s u l t s ，w ei m m e d i a t e l yo b t a i nt h el o w e rb o u n d s v o i l 8f o rt - r e g u l a rg r a p h s i n2 0 0 2 ，h e n n i n g 4 3 】s t u d yt h ec o n c e p to fs i g n e d2 - i n d e p e n d e n tn u m b e rd ii n t r o d u c e db y z e l i n k af s s ，a n de s t a b l i s h e ds o m eg o o du p p e rb o u n d sf o ro i ( g ) i ns e c t i o n4 4 ，w eo b t a i n s o f t i e n e wu p p e rb o u n d sf o rn ；8 ) i nt e r m so fo r d e r ，s i z e ，n u m b e ro fo d dv e r t i c e s ，m a x i m u md e g r e e a n dm i n i m u md e g r e eo fag r a p h ，a n dw ee s t a b l i s has h a r pu p p e rb o u n dn s 2 ( g ) g 害与十礼一 f 簧+ 簧”o i l ；( g ) f o r a nr p a r t i t eg r a p hw i t ho r d e ”t i nc h a p t e r5 + w ed i s c u s st h ep r o b l e m so ne e n t r u ma n db a l a n c ev e r t i c e si ng r a p h s t h ek - c e n t r u mo fag r a p hw a si n t r o d u c e db ys l a t e r 7 4 3 8g e n e r a l i z a t i o n so ft h es t a n d a r d d e f i n i t i o n so ft h ee e n t r aa n dt h em e d i af o ra r b i t r a r yg r a p h sg ，a n ds a t e rp r o v e dt h a tf o ra n y t r e ef o f o r d e r ”= l v ( t ) 1 t h ek - c e u t r u mg ( t ；) c o n s i s t so f o d e v e r t e xo rt w oa d j a c e n tv e r t i c e s i ns e c t i o n5 2 tw ep r o v et h a tf o ra n yc o n n e c t e dg r a p hgw i t hb l o c kn u m b e r2 ，t h ek - c e n t r u m e f g ；1i sc o n t a i n e di no n eb l o c ko fg t h en o r i o no fb a l a n c e db i p a r t i t i o n so ft h ev e r t i c e si nat r e et i si n t r o d u c e da n ds t u d i e db y r e i df 7 1 1 ，a n dr e i dp r o v e dt h a tt h es e to fb a l a n c ev e r t i c e so f at r e etc o n s i s t so fas i n g l ev e r t e x o rt w oa d j a c e n tv e r t i c e s i ns e c t i o n5 3 ，w eg i v eas h o r tp r o o f t ot h er e s u l t + k e y w o r d s ：g r a p h ；d o m i n a t i n gs e t ：d o m i n a t i n gf u n c t i o n ；m a t c h i n g ；c e n t r a l v e r t e x ；b a l a n c ev e r t e x v 1 上海大学 厂 旦6 7 8 2 3 5 本论文经答辩委员会全体委员审查，确认符 合上海大学博士学位论文质量要求。 答辩委员会签名： 主任：c 工作单位、职称，蓐劣；n 孝吖彩荡膨f 儆 委员：邵莠褥囤海大肇怒火 眵峻j 1 蠡弘芒孝莎叹 导师 彳陋蓼 列莒挈 答辩日期 少临大莩数梗 多，铹形履按 原创性声明 本人声鹱；辑皇交黪谂文是李久在鬃黪窖奏导下送行蕊骥巍王箨。 隙了文中特别加以概涟和致谢的地方外，谂文中不包含其他人殴发表 或凝驽邀的研究戚采。参与间一工作的其德同志对本研究所做的任何 霎懿蚜鑫在谂文孛箨了臻臻辩滋臻并衰示了游意。 燮名：冈期 本论文使照授权说踺 本久瓷全了解主簿大学宥关豫辩、霞鬻学位论文翁规定，帮：学 接帮殴镰鏊途文及送交论文复印罄，龛诲谂文荣耋溪释鬟瓣；掌棱霹 以公毒论文的全粥或部分内容。 ( 谦辩的论文在解密后成遵守此舰定) 签鑫； 等然鏊墓；嚣豢； 单薅芳黝挺年上海大学媾圭学位论文 l 引言 王 在过去懿戆三卡年曼，涟藿嚣葬橇辩学戆发袋，瑟论爨褒毒潆律瞧发羧戆趋势。在 图论中，发展最快的领域也许是图的“d o m i n a t i o n ”的研究，以图的各种控制数为研究对 象鹃毽兹摭裁集理论毫或为垂论戆一令重要熬硬究领域。这一领域静快遽发曩宝簧基 于下列三个因素；( 一) 它在现实墩界和诸如“覆藏“位置确定”爽数学问题中广泛而深 刻的应薅。人蜘已发理，其他学科申研究的许多翘题与图熊控制数有关。铡如嚣越编码 理论中正在研究的码长为n 覆盖半径为r 的二进制码的最小数k ( n r ) 正怒图的投制集 理论中超立方体图的r 一距离控制数( 见文献【3 ，l3 1 ) ，显然，图论中的距离控制数更具有 一般意义+( 二) 羧籍参数定义类溅的多样往根据实际背景的不简，瑗既定义的控制 参数有几十种之多，而且随着研究的深入和应用的激发，新的参数如雨后漤笋，不断涌 瑷( 三) 疆静控截参数确定闻瑟懿n p - 宠全往与其它缀合优纯中n p 一凳全闻联紧密 而自然的关系在特殊图( 如树，豫图，圆弧图，区间图，a t f r e e 图等) 上，研究各类控 裁参数兹诗算复杂经已或凳组台键佬镶域申一令琴| 久入黢瑟富毒魏凌佳懿赣宠方爱。 据考_ i 难，图的控制数的研究历史可追溯到公元1 8 5 0 年，当时欧洲人注意到这样的问 瑟：一个鬻际象棋棋盘土，鼓步效麓尼个爨詹藏鼍控麓( 袭毒) 或占据瑟舂晦方格，速可 以着作图的控制数的最早雏形在1 9 6 0 年前后，人们开始对图的控制数进行数学研究， 起麓逐是祭孛予戮究nx “棋盘戆务类控裁1 9 5 8 年，b e r g e 懿毽论专著巾蓠次出瑷，控 制数”这一概念，尽管当时他用了妈外的名称1 9 6 2 年，o r e 的圈论著作中，正茈定义 并烧愿基麓一直辫露戆控剃数术渗 d o m i a n t i n gs e t ”纛 d o m i n a t i o nn u m b e r ”1 9 7 7 年， c o c k a y n e 和h e d e t n i e m i 在一篇短的综述报告中，开始用符号7 表示图的控制数，而且沿 用楚今i i i i 詹，这理论开始引起人们的广泛关波并褥到迅速发展，控制数研究的文献 频频出现禚各种数学期刊一t 嚣t 9 9 0 年，d i s c r e t em a t h e m a t i c e s 出版的图的控制集 专刊中引用了大约4 0 0 个文献1 9 9 8 年，荧国学者h a y n e s ，h e d e t n i e m i 和s l a t e r 蹦，酬】在 避行系统憨绪后，嚣次高簇了两本笑于图簸控销蒸灌论静专著d o m i n a t i o ni ng r a p l t s _ 一 一a d v a n c e dt o p i c s 和f u n d a m e n t a l so fd o m i n a t i o ni ng r a p h s ，其中在f u n d a m e n t a l s o fd o m i n a t i o ni ng r a p h s 申亏 罱了1 2 0 0 多个文献。这两本专著懿圭鎏蔽，菇久韶深入研 究这一理论奠定了坚实的基础，同时也巩固了图的控制集理论在图论中的地位关于 1 9 9 8 年翦控鞠集戮究静全嚣迸爱露参看【3 8 ，3 露舞1 9 9 8 年渡寒，懑嚣控翻集理论缮努 了前所未有的发展，以至于人们面对如此多的文献难于写出一个简明的综述报告有关 控疑数毂文裁，摄偿诗已越过3 0 0 0 薅。 设g 一( e e ) 裘示一个图，假定s v ( a ) 且s 满足菜种性质p ，若对每一个s 7 cs ， 2 围的控制数及其相关参数 s 都不其有往获p ：弱称s 是援，j 、的；慧对每一个s cs 者| ；不其有黻震p ，剥称s 燕 极大的在数学上，通常会考虑确定最小或最大的极小( 大) 集所含元的数目这正悬 凌静控爨数壤念薹予翡数学曹祭。事实上，人销一齐始褥究垂鹣整钢数裁注意戮它豹应 用价值和应用前景当时，人们研究它是基于下列应用模型：用图g 表示一个计算机 惩终，镣个点裘示一个处理器，每条逑裘承连接螽令楚理器弱遴痿线路褒将一个资源 集放置于网络中，使每个处理器可通过楚少一条线路与资源集相连，以获取来自于资源 集鲍掺令债息基于费熙的考虑，选择尽可能少鲍处理器放置资源集，被选择处理器数 目的最小值就怒图g 的控制数其次，在二十世纪八十年代中期，人们在编弼理论中 开始研究下列“覆盖码( c o v e r i n gc o d e ) ”问题；设n n ，k ，r o ，1 ，2 ，n ) 。且x 彤 ( f 2 = 伦l 是二元域) 一个二元码e 曼糙的覆盏半径c r ( e ) 定义为 c r ( e j = m a x d ( x ，0 ) x 聪 这里d ( x ，o ) = m i n d ( x ，y ) 1y o ) ，而d ( x ，y ) 为通常的h a m m i n g - 距离因此c r ( o ) 魁 最小的整数，馒褥霹懿每个点y 与o 麴距离d ( y ，e ) 不超过c r ( o ) 具有覆盖半径r 蛉 二元码0 被称为一个( n ，1 0 1 ) r 诵，特剐地，当0 是有2 0 个码字的线傲码时，( n ， e 1 ) r 码也称为b ，翻r 码。k ( n ，r ) 和t h r 】分别定义为 k ( n ，r ) = m i n mj 存在( m ) r 码) t i n ，r 】= m i n t l 存在【喁k i t 码 k ( n 、r ) 即为聪中长度为n ，覆攘半径为r 的码的最小数目；而t n r 为璎中长度为忆， 覆盖半经为r 懿线性弱瞧最，、数曩，一个( 强蜀( 强r ) 涉妫效黎为最捷码确定炎眩r j 蛉 值或者界是重要的人们在编码理论中开始研究这类问题时，并没有注意到图论中的控 制数概念，同樽，图论磺究者们也没有注意到编码理论巾的这些研究蠢于n 一缎超立方 体m c u b e ) 骗恰有2 n 的点且它的每个点均可塔用一个n 维0 - 1 向量表示，因此v ( q 。) 与玲的元完全榻同，耐图q 。中点之间的距离定义与编码理论中的汉明度量一致，这 棒，每个码c 瑶恰对应超立方体强q 。的某个子围的点集，溺此k ( n ，) 正麓图论中 研究的超立方体q 。的r 一距离控制数人们也涟意到掰的连通控制数与广播网的传播 数阕遂( g o s s i p n u m b e r p r o b l e m ) 有密餐关系( 觅文簌【3 3 1 ) ，魏井，壶霞酌控麓参数定义静 广义r a m s e y 理论已成为当今r a m s e y 理论中的一个重要研究领域( 见 4 6 4 7 】) 总之， 露戆控制数瑾论已广泛应曩于诗葵撬褥学，通臻辩学，瓣终理论，电力系统帮社会学戆 研究中 当懿，关予匿鲍控割囊熬 嚣突主要在默下足令方嚣展开；( 1 ) 控魁参数男装确定 及与相关图参数的关系；( 2 ) 控制参数计算复杂性的研究和算法设计研究；( 3 ) 函 数控制数及其相关课题爨究；( 4 ) 控制集的应用研究 单而芳2 0 0 4 年上海大学博士学位论文 2 图的控制数的上界 3 在研究一类给定子集问题时，通常找出这类子集的最小者或最大者是我们所关心 的，例如，找出控制集或覆盖集的最小基数，找出独立集或填装集( p a c k i n gs e t ) 的最大 者我们已知道任意图的控制数的确定问题是n p 一困难的，即使对最大度为3 或4 正 则的平面图，它的确定问题仍然是n p 困难的正因如此，使得确定图的控制数的界的 问题成为一件十分有意义的工作图的控制数的界可以按照图的点数或边数给出，也可 与图的其他参数进行比较关于这方面的研究综述可参看专著 3 8 】 本章主要包括以下几个方面的工作：首先给出最小度为3 的图的控制数和限制控制 数的一个新上界其次刻画了匹配数与控制数相等的极值图，并证明了最小度不小于4 的 无爪图其全控制数不超过它的匹配数最后，给出了一类k 一控制数的n o r d h a u s g a d d u m 不等式，作为推论，解决了h a r a r y 提出的一个猜想 2 1 基本概念和记号 本节所讨论的图均为无环无重边的简单图为了叙述方便，首先我1 1 1 弓1 入一些定义 和记号设g 是简单图，v ( a ) 和e ( a ) 分别表示图g 的点集和边集，n = l y ( g ) l 记作 图g 的阶数g 的补图百也是以v ( a ) 为点集的一个图，两个点在百中邻接当且仅当 它们在g 中不邻接 图g 中点z 的邻域定义为( z ，g ) = lx y e ( g ) ) ，z 的闭邻域为2 v x ，g 】= n ( x ，g ) u z ) 更一般地，对任意的x y ( g ) ，我们定义n ( x ，g ) = u 。x n ( x ，g ) ，n i x ，g ： n ( x ，g ) ux 在不引起混淆的情况下，上述符号可分别简记为( 。) ，n i x ，n ( x ) 和n i x 设x 垦v ( a ) 且。x ，y v 称为对应于x 的一个私邻域点，如果。是y 在x 中的唯 一邻接点，也即州胡n x = $ 我们定义集p r ( x ，x ) = m 陋一如) 】为点x 的x 私 邻域，简记为p r ( x ) 为方便起见，对任何t d ，规定p r 。( t ，d ) = 吲( 旧t ut ) 显然，p 广( t ，d ) v d ，且p p ( t ，d ) 中的每一个点仅与t 的点邻接，而不与d t 的 任何点邻接我们称d ( x ) = l ( 。) l 为点z 的度数，度数为1 和0 的点分别被称为图 的悬挂点和孤立点用( g ) 和d ( g ) 分别表示图g 的最大度和最小度用仇表示由 k 个点构成的圈对a y ( g ) ，用g 或( a ) 表示由a 导出的子图，对x v ，记 d a ( x ) = l a ：x y e ) i 设x ，y c y ( g ) ，用a z ，y 】表示具有二分集x 和y 的偶图， 它的边为g 的连接x 和y 之间的所有边记e ( x ，y ) = l e ( a x ，y 帅一个星形图是指 m 2 的完全偶图k 1 g 的一个子图日被称为g 的一个因子，如果v ( h ) = y ( g ) 设d y ( g ) ，若y ( g ) d 中的每一个点，至少与d 的一个点邻接，也即n d = v ( g ) ， 匿堕整劐墼丛基翅羞查熬 翊稼p 为g 的控籁集，簿记为d s ，g 豹控裁数，( o ) 定义为g 酶最小控穰集豹点数 若v ( c ) 中的每一个点，至少与d 的一个点邻接，也即( d ) = v ( g ) ，则称d 为g 的 全控麓褰，簿记为t d s g 戆金茬铡数饿( g ) 意义为g 豹最，j 、全控剿鬃翡点数显然， 任意图都存在d s ，而每个无孤立点的图都存在t d s ，因为d v 就是一个t d s ，一个熬 数埝为7 ( a ) 蛉d s 被豁为g 黪一个妒集麓棒，一个基数埝为蕊( 固懿t d s 被熬为 g 的一个仇一浆在图g 中，蒋z 和y 邻接，则称。控制y 鼎然，z 控制它邻域里的 所毒点进一步，设a 移丑为v ( a ) 鳓两个孑集，若n ( a ) b ，则髂a 控测b 菪一 个点