（运筹学与控制论专业论文）关于图的全无赘数的讨论.pdf

硕士学位论文 m a s t e r st h e s i s 摘要 由于控制数理论的研究越来越引起人们的重视，人们对控制数有了更深入的 了解，提出了不同的控制数，例如全控制数、小控制数、负控制数、连通控制数 等这些类型的控制数的量的关系在图的结构中起着重要的作用 在长期的研究中，一些研究者们发现研究图的无赘数可以使人更深入的了解 图的控制数理论到目前为止，对于图的无赘数的研究已经越来越深入，研究者 们也已经得到了图的无赘集的大量的性质c o c k a y n e 和m y n h a r d t 更是认为对 全无赘数的讨论有利于我们更好的了解全控制数事实上，h e d e t n i e m ie ta l ，在 文【8 j 中给出了图的全无赘数的概念，并讨论了一些特殊图的全无赘数，而o d i l e f a v a x o ne ta 1 在文【9 l 中进一步得到了图g 满足机( g ) = o 的充分必要条件和 满足机( 丁) = 1 的树t 的结构 本文主要讨论的是满足讥伶) = 1 的图g 的某些结构特征及满足i r ( g ) = 讥( g ) = 1 的图g 的构成得到的主要结果如下： ( 1 ) 图g = ( k e ) 是经克隆一收缩后得到的图， o v ，以蛳为第0 层将 图g 中的点分层，若层数七4 ，则有机( g ) 2 ； ( 2 ) 图g 为连通图，咖g ，满足n v o 】= y ( g ) ，若g l ，g 2 ，g 为g 一o 的所有的连通分支，则j o 1 ，2 ，) ，使得i r t ( g h ) = 1 ，讥( g ) = 0 ，i = 1 ，2 ，一，k o 一1 ，k o4 - 1 ，一，k 其中对i r ( g ) = i r t ( a ) = 1 的图g 的结构的讨论部分的回答了文【9 】9 中的开 放同题( 2 ) 关键词：控制数，无赘数。全无赘集，全无赘数，结构特征 硕士学位论文 m a s t e r st h e s i s a b s t r a c t b e c a u s et h es e a r c ho nt h ed o m i n a t i o nn u m b e r si sm o r ea n dm o r ea t t a c h e d i m p o r t a n c et op e o p l eg e tm o r ed e e p l ya w a r e o fi ta n dp u tf o r w a r dm a n yd o m i n a - t i o np a r a m e t e r s ，8 u c ha s ：t o t a ld o m i n a t i o nn u m b e r ，m i n u sd o m i n a t i o nn u m b e r ， n e g a t i v ed o m i n a t i o n n u m b e r ，a n ds oo n ，t h o s et y p eo fd o m i n a t i o nn u m b e rp l a y a ni m p o r t a n tr o l ei ns t r u c t u r eo fg r a p h s i nt h el o n g - t e r ms t u d y i n gi ti sf e l tb ys o m er e s e a r c h e r st h a ta d e e p e ru n d e r - s t a n d i n g o ft h ec o n c e p to fd o m i n a t i o ni ng r a p h sc a nb e s tb eo b t a i n e db ys t u d y i n g t h em o r e g e n e r a lc o n c e p to fi r r e d u n d a n c ei ng r a p h s t od a t e ，t h er e s a e r c ba b o u t t h ei r r e d u n d a n c ei ng r a p h si sm o r ea n dm o r ed e e p e r r e s a e r c h e r sh a v eg o tal o t o fp r o p e r t i e sa b o u tt h ei r r e d u n d a n ts e ti ng r a p h s c o c k a y n ea n dm y n h a r d ti s m o t i v a t e db yt h eb e l i e ft h a tt h es t u d yo ft o t a li r r e d u n d a n c ew i l ls h e dl i g h to n t h ec o n c e p to ft o t 矗ld o m i n a t i o n i nf a c t ，h e d e t n i e m ie ta 1 i n 【8 】h a v eg i v e nt h e d e f i n i t i o no ft h et o t a li r r e d u n d a n ts e to fag r a p h ，a n dd i s c u s s e dt h ei r r e d u n d a n c e n u m b e ro fs o m e s p e c i a lg r a p b s o d i l ef a v a r o n e ta 1 i n 【9 】h a v eg o t t e nt h es u f f i c i e n t a n de s s e n c i a lc o n d i t i o no ft h eg r a p hg s a t i s f y i n gi r t ( g ) = 0a n dt h es t r u c t u r eo f at r e et s a t i s f y i n gi r t ( t 1 = 1 t h i sp a p e rm a i n l yd i s c u s s e ss o m es t r u c t u r ec h a r a c t e r i z a t i o no ft h eg r a p hg s a t i s f y i n gi r t ( g ) = 1a n dt h ec o n d t i t u t i o no ft h eg r a p hgs a t i s f y i n gi r ( g ) = i r t ( g ) = 1 t h em a i n l yr e s u l t sa r e ： ( 1 ) t h eg r a p hg = ( ke ) i sg o t t e nb y t h ec l o n ec o n t r a c t i o n ，v 0 v ，c o n s i d e r v oi st h ez e r ol a y e r ，d i v i d et h ev e r t i c e so f g i n t ok l a y e r s ，i f 七4 ，t h e ni r t ( g ) 兰2 ； ( 2 ) t h eg r a p hg i sac o n n e c t e dg r a p h ，v 0 y ( g ) ，s a t i s f y i n gn v o 】= v ( c ) i fg l g 2 ，一，g ka r ea l lt h ec o n n e c t e d c o m p o n e n to fg v 0 ，t h e nt h e r ee x i s tk o i n 1 ，2 ，七) ，b t i r t ( g k o ) = 1 ，i r t ( g t ) = 0 ，i = 1 ，2 ，o 一1 ，k o + 1 ，女 t h e d i s c u s s i n go ft h es t r u c t u r eo ft h eg r a p hgs a t i s f y i n gi r ( g ) = i r , ( g ) = 1 h a sp a r t l ya n s w e r e dt h eo p e np r o b l e m ( 2 ) i n 【9 】 k e yw o r d s ：d o m i n a t i o nn u m b e r ，i r r e d u n d a n c en u m b e r ，t o t a li r r e d u n d a n t s e t ，t o t a li r r e d u n d a n c en u m b e r ，c o n s t r u c t i o nc h a r a c t e r a t i o n i l 硕士学位论文 m a s t e r st h e s i s 第一节引言 一、历史和研究现状 在四百多年前印度的一种棋盘游戏中，人们发现了棋盘的某些方格能控制其 它的方格，于是产生了最早的控制思想，最早给出控制数正式定义的是b e r g e 和 o r e 由于图的控制理论在实际应用越来越广泛，控制理论得到空前发展到目前 为止，关于图的控制数的文章已经有约1 5 0 0 多篇关于图的控制数问题在h a y n e s e ta 1 的两本书6 ，7 1 中有详尽的叙述 由于控制数理论的研究越来越引起人们的重视，人们对控制数有了更深入的 了解，提出了不同的控制数，例如全控制数、小控制数、负控制数、连通控制数 等这些类型的控制数的量的关系在图的结构中起着重要的作用 一些研究者们认为研究图的无赘数可以使人更深入的了解图的控制数理论 这个想法来源于c o c k a y n ee ta 1 子1 9 7 8 年在f 4 l 中得到的结论，点集s 为图 的极小控制集当且仅当它既是无赘集又是控制集随后b o l l o b d s 和c o c k a y n e 在 【2 】中得到图g 的极小控制集族包含在图g 的极大无赘集的外围集中事实上， 在| 5 j 中c o c k a y n e 和m y n h a r d t 认为了解无赘集更利于研究控制集的性质，特殊 的，全无赘数的研究必然会推进全控制数的研究 h e d e t n i e m ie ta 1 在f 8 】中给出了全无赘集、全无赘数的定义，o d i l ef a v a r o n e ta 1 在【9 】中进一步得到图g 满足i r t ( g ) = 0 的充分必要条件和满足i r e ( t ) = 1 的树t 的结构 本文在他们的基础上对得到满足机( g ) = 1 及i r ( g ) = i r t ( g ) = 1 的图g 的结构上做了一定的工作 二、符号说明 本文讨论无向简单且连通有限图，没有说明的符号及术语其含义与文1 中 一致常用符号说明 n ( v ) = u l u v e ( g ) ) l v v 】= u u v e ( g ) ，u m = n ( v ) u ) n ( s ) = un ( v ) 旧= un ( v ) u s = n ( s ) u s 1 硕士学位论文 m a s t e r st h e s i s p 扣，s 】= 【”1 一【s ) d i s t g ( u ， )图g 中连接u 与v 的最短路长 g 珈)去掉点u o 及所有与点v o 相关联的边而得到的图 三、预备知识 定义1 1 ：若对v v s y ( g ) ，p n v ，s 】0 ，则称集合s 为图g 的一个 无赘集 定义1 2 ：称i r ( g ) = m m i s i i s 为图g 的极大无赘集) 为图g 的无赘数 定义1 3 ：s v ( g ) ，若对v v y ( g ) ，p n v ，s 】口，则称集合s 为图g 的一个全无赘集 定义1 4 ：称i r t ( g ) = m i n j sj s 为图g 的极大全无赘集) 为图g 的全无 赘数 定义1 5 ：对y u ，。v ，若n l u = 州 】，则称u 和v 为克隆；若n u 】c n l v ， 则称点、，优超于点u 或点u 屈服于点v 四、巳知结果 o d i l ef & v a r o ne t a 1 在文( 9 j 中通过了1 3 页纸的讨论得到了图g 满足 i r , ( g ) = 0 的充分必要条件及满足饥p ) = 1 的树t 的结构具体结论如下。 定理1 6 ：若图g 为某图的克隆一膨胀，则吮( g ) = 0 定理1 7 ：图g 满足饥( g ) = 0 当且仅当矿( g ) ，图g 中存在异于点 v 的点u ，使得点v 与点u 克隆或点vi ss u p e r i o rt o 点u 定理1 8 ：非平凡树t 满足i r , ( t ) = 1 当且仅当它由星k 1 。经如下三种变 形而得t ( a ) 对m 1 时剖分星的条边， ( b ) 对m 3 时剖分星的m 一1 条边，或 ( c ) 对m 2 时耐分星的所有边 在文【9 】末尾。o d i l ef a v a r o ne ta 1 提出了6 个有待解决的开放性问题。其 中问题( 2 ) 为描述满足i r ( g ) = i r t ( g ) = 1 的图g 的结构 本文正是在文【9 】的基础上。进一步讨论了满足i r t ( g ) = 1 的含圈图g 的结 构，及满足i r ( g ) = i r , ( g ) = 1 的图g 的构成 2 第二节满足讥( g ) = 1 的图g 定理1 8 即为满足机( g ) = 1 的无圈图g 的结构，所以下面我们仅就图g 中含圈的情况来讨论 将图g 中的点以“克隆”关系进行分类，点u 与点v 属于同一个集合当且仅当 点u 与点v 克隆从而得到一些克隆一集合：z l l l ， ) 1 2 ，”l j i ) ，v 2 1 ，u 2 2 ，也j 2 ) ， ， 他l ，2 ，明 ，及一些单点l m + 1 ，u r n + 2 ， 。，其中m = f l + 1 2 + + k 记g 1 = g l t ，1 1 ， 1 2 ，- ，口l f l ) 】，g 2 = g f 也l ， 2 2 ，- 一，现b 】，g k = g 【 1 ，2 ，。) 】 克隆- 收缩图g ：以点q 代替g ，去掉边 e = u h 口g ，i = 1 ，2 ，) ， 而边e = 伽0 g “u + 1 ，+ 2 ， ，i = 1 ，2 ，k ) 用边e = 仇 ( 。 卅l ，+ 2 ，) ，i = 1 ，2 ，) 来代替，边e = ( 口g i ，口7 q ，i j ，t ，j = l ，2 ，q 用边e = v | i v j ( i j ，i ，= 1 ，2 ，k ) 来代替，其余的点和边 均不变。得到的图记为百 对图g = ( k e ) ，口o v ，定义 o ( 咖) = 咖 1v o ) = n ( v o ) g = g i n o ) j g 毛= g i n l ( 咖) 】 。( v o ) = 1 由引理3 1 则v 1 s ，故s 中存在点 ，使得 v ( g ) u 1 ) n v _ i i i tg 中存在一点，设为u ”，使得l ”】c 州 】或】= 】 于是对 ” g h ”】一g 【s 一 ”) 】n v v ”】一n o v = d 所以 g 【 ”】一g s 一 ”) 】= 口 与“s 为图g 的全无赘集”矛盾，故纨( g ) = 1 所以 帆( g ) = 1 铮i r c ( g ( 1 ) ) = 0 c a s e 2 旦：g o ) 恰有两个孤立点设为v l ，u 2 若g 珈) = ( v t ，u 2 ) ，即g = 乃，此时i r t ( p 3 ) = j r ( p 3 ) = 1 若g 蜘) 有2 个以上的连通分支，且恰有2 个连通分支为孤立点i 1 ，v 2 ，显然 s = 仃i ，啦 为图g 的一个全无赘集，所以i r t ( c ) 2 ，不满足i r ( a ) = i r t ( g ) = 1 c a s e 2 ，：g 。o ) 有2 个以上的孤立点 显然此时i r c ( g ) 2 ，亦不满足i r ( g ) = i r t ( g ) = 1 c a s e 2 # ：g 珈 无孤立点 定理3 3 设g ”o ) 的连通分支为g 1 ，g 2 ，g ，若i r t ( 6 ) = 1 ，则3 k o l ，2 ，七) ，使得i r t ( ) = 1 ，i r t ( g ) = 0 ，i = 1 ，2 ，一1 ，岛+ 1 ，k 证明。因为机( g ) = 1 ，设s 为图g 的一个极大全无赘集，且i s l = l ，显 然v o 岳s ，否则 o s 则对v v y ( g ) o ，有 故 ”】一n s 一 ”) 】 ” 一n v o 】= o 一n s 一 ) l _ o 1 3 硕士学位论文 m a s t e r st h e s i s 集 与“s 是全无赘集”矛盾，所以s 中的点必在某个g 。中( 1 i ) 设s = ) ，且 女。v ( g k 。) ，k o 1 ，2 ，) 下证： s = v k o 也是g 女。的一个极大全无赘集 对咖v ( g k 。) n a 。【”】一 b b i s 一 秽) = ( v 舀p t b ) ) 一( n 4 s 一 ) 】 珈) ) = 矗【”】一g s 一( ) 】 所以s 是g 女。的一个全无赘集 假设3 s 为伉。的一个全无赘集，且scs ，则也是图g 的一个全无赘 事实上，因为v v y ( g ) y ( g ) ，有 g 【u y ( g ) y ( g 知) 且 v 0 【s 一 ”) l = g 【s 】cv ( a b ) u v o ) 而v o b m ，g 珈) 无孤立点 所以 g h 】一g 【s 口) = g p 一 咖) o 对v v v ( g k o ) n o ”】一舀 s 7 一 ”) j = ( 舀b 扣】u ) ) 一( g b i s 一 ”) 】u = n o 如p i 一g 。i s 一 口) j o 则对矿( g ) ，都有 m n 4 s 一如) j 口 所以s 也是图g 的一个全无赘集。与s 的极大性矛盾 所以s 是g b 的一个极大全无赘集，故讥( g 。) = 1 假设在 1 ，2 ，一l ，+ 1 ， 中还存在碥，使得打t ( g 矗) 1 1 4 硕士学位论文 m a s t e r st h e s i s 设为g i ：的一个极大全无赘集，且 = 钒( q ：) 下证：s + = s u 也是图g 的一个全无赘集 对v v v ( g ) ( 1 ( g b ) u v ( a 女：) ) 因为 g 【1 j y ( g ) ( v ( g b ) uv ( c 女：) ) g 【s + 一 】( y ( g t 。) uy ( g 吐) ) u 咖) 而 o k f 1 ，所以 g 卜】一a 【s + 一 ”) 】= n c , v 】一 v o ) o 对v v y ( g i 。) g 扣j 一f s + 一 u ) j = ( n o b p l u ”o ) ) 一( g b s 一 ”) j u f f 0 ) = n o h i v _ g 。i s 一 ” 0 对v v v ( a ) g 【小一g f 一 ”) 】= ( 。一u 珈) ) 一( g 。一( ”。) 】) = g 。川一n a 。一洲o 员对v v y ( g ) ，都有 g 【”】一g 【s + 一 ” 0 所以s = s u s ? 也是图g 的一个全无赘集，故讥( g ) 2 ，与“讥( g ) = 1 ” 矛盾，故不存在这样的碥 即对v i 1 ，2 ，女。一1 ，k o + 1 ，) ，都有i r ( o i ) = 0 定理3 4 ：若j 2 一连通图g l ，g 2 ，g 女，使得i r ( g i ) = 1 ，讥( g i ) = 0 ，2s i k ，且g l ，g 2 ，g 女都不是单点集，再增加一个点，且将增加的这个点与所 有g i ( 1s i s ) 中的所有点连边，这样构成图g ，那么i r c ( g ) = i r ( g ) = 1 特 别当= 1 时也成立 证明；由定理3 3 直接可得 由定理3 3 可知，要想找出满足i r ( g ) = i r ( g ) = 1 的图g 的结构，只需找 出i r t ( g ) = i 的2 一连通图g 的结构即可 1 5 参考文献 j a ，b o n d ya n du s r m n r t y g r a p ht h e o r yw i t ha p p l i c a t i o n s m n e wy o r k ：t h e m a c m i l l a np r e s sl t d ，1 9 7 6 1 2 】2b b o l l o b d s ，e j c o c k a y n e ，g r a p ht h e o r e t i cp a r a m e t e r sc o n c e r n i n gd o m i n a t i o n ，i n d e p e n d a n c ea n dr r e d u n d a n c e ，j g r a p ht h e o r y3 ( 1 9 7 9 ) 2 4 1 2 5 0 【3 jf h a r a x y , g r a p ht h e o r y , a d d i s o n w e s l e y , r e a d i n g ，m a ，1 9 7 2 1 4 le 。j c o c k a y n e ，s t h e d e t n i e m i ，d j m i l l e r ，p r o p e r t i e s o f h e r e d i t a r yh y p e r g r a p h s a n dm i d d l eg r a p h s ，c a n a d m a t h b u l l 2 1 ( 1 9 7 8 ) 4 6 1 4 6 8 【5 】e j c o c k a y n e ，c m m y n h a r d t ，i r r e d u n d a n c e i ng r a p h 文p e r s o n a lc o m m u n i c a t i o n 2 0 0 0 【6 j 6t w ，h a y n e s ，s t h e d e t n i e m i ，p j s l a t e r ，f u n d a m e n t a l so fd o m i n