（运筹学与控制论专业论文）图的控制和连通控制.pdf

摘要 由于控制数理论的研究越来越引起人们的重视，人们对控制数有了更深的了 裤，提出了不同的控制数例如全控制数，小控制数，负控制数，连通控制数等 等这些类型的控制数的量的关系在图的结构中起着重要的作用而其相应的判 定问题是n p 完全问题或p 困难问题因此对于它们的界的估计是非常有必要 的 本篇论文主要研究的是图的控制数7 与连通控制数在某些图中的关系问 题，以及满足1 = 7 。的某些图类的性质问题 关于控制数，y 与连通控制数在某些图中的关系问题文f 3 j 给出了满足，y = 的树的条件，但实际上有很多树都不满足这个条件于是我们想对树中工值的界 作进一步的讨得到下面两个非常好的结论： ( 1 ) 对于树丁来说，； o ，； o ，那么f a + 而c k 证因为o b k ，c d k ，所以 譬 k 即得证 d + d 命题2 2 树t 的最小连通控制集是树的内点集 证因为最小连通控制集不会全是叶子，并且连接两个钩子的路上的点全是内 点即得证 s a r u m u g a m 等人在 3 中刻画了满足7 = 条件的树： 定理2 1 3 】对于一个树t 且l v ( r ) l 3 , v = 当且仅当树t 的每个内点 是钩子 但实际上有很多树都不满足这个条件于是我们想对树中上值的范围作进一 7 0 步的讨论 图g 的边e 被收缩是指把它删去，并使它的两端重合，这样得到的图记为g e 引理2 1 对于树t ，若s ( t ) 不为空集，有拶( t ) = 玎圩( 。) 一2 ( ( t ) x e j ( t ) 1 ) 证若4 j ( t ) = 0 ，设p = l 2 是树t 中的最长路，那么a 4 与因为 。2 5 时，则v 3 j ( t ) ，与# j ( t ) = 0 矛盾但是。= 1 ，2 ，3 时，s ( t ) 为空集， 这与假设矛盾故口= 4 ，这样树t 中只有两点u 2 ，地e s ( t ) ，故# s ( t ) = 2 因此 此时式子猡( t ) = m t ( 。) 一2 ( # j ( t ) 一1 ) 成立 ? ，( ” 若蛆( t ) = 1 ，令此点为”，于是 7 7 l t 一) = # y ( t ) 一4 上( t ) 一t t ，( t ) = # s ( t ) 若g j ( t ) 2 ，则j e i = x t y l ，。l ，y le j ( t ) ，于是我们把e 1 给收缩，得到新图t e 1 在图t e l 中重合点。l ( 1 ) j ( t e 1 ) ， i x ，( 丁) 一 z l ，y 1 ) ，仍有z j ( t e 1 ) ， 且s ( t ) = s ( t e 1 ) 这样就有 j j ( t 吼) = 4 ，( t ) 一l ； 4 硕士学位论文 m a s t e r st t i e s i s m t 。( z ) = 研( z ) 2 o j te l 】z ，( r ) 然后对于图t e l ，若有e 2 = x 2 y 2 ，x 2 ，驰j ( r b 1 ) ，对e 2 再收缩于是反复 按照此法进行，直到缩到某一个树丁，j ( r 7 ) 中只有一个点，令此点为”这样做是 可能的，因为若z ，j ( t ) ，那么连接x ，的路上不存在点属于l ( t ) 或者s ( t ) 并且每次收缩一边，4 l ，( 丁) 减少1 于是总共缩了：，( 丁) 一1 次得到下面的等式 即碍证 s ( t ) = s ( t 。) ”吁( z ) 一2 ( 1 j ( 丁) 一1 ) = m ，( ”) z 卅7 1 ) = 口y ( t ) 一i l ( t ) 一i j ( t 7 ) = j s ( 丁) = i s ( t ) 为了方便下面定理2 2 的讨论，我们记唧( u ) = m ( ) 定理2 1 证明基于如下 思想：设d 是树t 的最小控制集如果ue d 时，那么它所控制的内点( 如果它本身 是内息就包括它本身这个翩就有m ( ”) + 1 个当m ( ”) 2 时，磊等是_ 0 由引理2 1 可得 l = l 因为 即得 因为 # s ( t ) = m ) 一2 ( # j ( t ) x e j ( t ) 1 ) = ( m ( ) 一2 ) + 2 z j ( r ) s ( m ( 仉) 一2 ) =( m ( z ) 2 ) i = 1 z e j ( n n i l ，一s = # j 5 | ( t ) 2 ) ) = ( m ( z ) 一2 ) + 2 一( m ( z ) 一2 ) z j ( nz e i ( t ) n i l s ( 带 地) + ( m ( 饥) 一2 ) 1 ) + ( m ( z ) 一2 ) 1 + 2 i = 1x e i i i s ( ( m ( ) + 1 ) + ( m ( v d 一2 ) 2 ) + ( ( m 扛) 一2 ) 2 十4 i = 1x e i i i s ( 带 哦) + ( m ( v i ) 一2 ) 1 i = 1 s ( ( m ( ) + 1 ) + ( m ( 忧) 一2 ) 2 l = l ( m ( ) 一2 ) - l 堑! 型 ( m ( z ) 一2 ) 2 x e i l l 7 赢舢 一 7 一 硕士学位论文 m a s t e r st h e s i s 故有命题2 1 ，得二 妄即得证 0 此界是最好的对于任意一个数妄+ p ，我都可以找到路p ，令路p 的阶为 s ，那么器= 嵩只要k 为奸可3 + 4 戳就有器 扣 8 定理3 1 若阶不小于3 的树丁的任何一个最小控制集d 使得h ( t ) d 且满足下面两个条件： ( 1 ) 吖。( t ) = ( 盯吁扣) + 1 ) ； x 6 d ( 2 ) v x v ( t ) 一d l ( t ) ，有m t ( x ) = 2 那么树t 有唯一的最小控制集 证为了下面证明方便，我们记 吁( ) = m ( u ) ，( t ) = 7 ，( t ) = 首先我们 看两个断言： 断言一：若阶不小于3 的树了1 的任何一个最小控制集d 使得h ( t ) d 且 满足下面两个条件： ( 1 ) ( t ) = ( m - r ( z ) + 1 ) ； z 6 d ( 2 ) v x v ( t ) 一d l ( t ) ，有御( z ) = 2 那么树丁只有一个最小控制集含有日汀) 证明：设d t 是任意一个满足断言一条件的最小控制集由条件( 2 ) 和上节 的证明可知v x ，y d 1 ，都有( 。) n ( ) = 而由条件( 3 ) 可知v x v ( t ) 且m ( z ) 23 ，都有x d t 我们如果记以( ? ) = z v ( t ) ：m ( z ) 3 那么 j 3 ( t ) d 1 并且由已知得s 口) c 日口) cd a ) 若以( t ) = ，由社s ( r ) = ( 仇( z ) 一2 ) + 2 ，可得社s ( r ) = 2 匿为 r j f r ) 襻s ( t ) = 1 的情况不存在；而榉s ( t ) = 0 时t 是一个璧，结论显然，故不作讨 论从而可设s ( t ) = o l ，z 2 ) ，考虑连结。1 ，0 2 的路p ，设p = x l 1 也口m z 2 ， 其中r e ( v , ) = 2 ，i = 1 ，m 因为分别与uh ，y m 相连的叶子不在d l ，所以 l ，的某些点属于d l ，并且这些点将u l ，u 。控制，又因为，g d 1 有 n ( z ) r 、n ( y ) = 西，那么由于 1 ，u 。分别与d l 中的z 1 ，z 2 相连，故p 0 = u 2 一1 必须是一个阶三o ( m o d 3 ) 的路，这样p 0 中选入d l 中的点的选取方式唯一故 d l 的元素是唯一确定的 9 硕士学位论文 m a s r e r ls t l i e s i s b ) 若以( t ) 西，则v 。s ( t ) cd ，j 唯一的矗( t ) cd 1 ，使得 d ( z ，y ) = m i n d ( x ，z ) ：z j 3 ( t ) 记p = 。1 u l 。是连结。，y 的路，其 中m ( v i ) = 2 ，j = l ，2 ，m 因为分别与 一，相连的叶子不在d 1 ，所以 u l ，”2 ，口。的某些点 属于d 1 ，并且这些点控制口1 ，u 2 ，口。，又因为v x ，y d 1 都有n ( x ) n n ( y ) = 咖 那么由于口l ，u 。分别与d 1 中的z ，y 相连，故p 0 = t ；2 u 。一l 必须是一个阶三 o ( m o d 3 ) 的路这样p o 中选入d 1 中的点的选取方式唯一若：舻以( t ) = 1 ，则d l 唯 一若拱，3 ( t ) 2 ，考虑以( t ) 中的两个点z ，y ，在连结o ，y 的路p = z 口l 2 中都有r e ( v , ) = 2 ，i = 1 ，2 ，m 讨论方法类似，可以证明p o = y 2 v 3 。一l 必 须是一个阶三o ( m o d 3 ) 的路，这样r 中选人d l 中的点的选取方式唯一故d l 的元素是唯一确定的 综上所述，如果满足断言一的题设，那么树r 只存在一个包含h ( t ) 的最小 控制集 断言二：若阶不小于3 的树t 的任何一个最小控制集d 使得h ( t ) d 臣 满足下两个条件： ( 1 ) 仉( t ) = ( m t ( z ) 4 - 1 ) ； d ( 2 ) v x v ( t ) 一d l ( t ) ，有m r ( z ) = 2 那么树丁的任意最小控翩集都包含日( t ) 证明：设d 1 是满足断言二条件且包含h ( t ) 的最小控制集，由断言一，得d l 唯 一这样自然有s ( t ) d l 并且v z y ( t ) ，m ( z ) 3 ，都有。d i 设d 是任 意一个最小控制集 ( a ) 首先证明：v z s ( t ) ，都有z d 反证法假设3 x s ( t ) 且x g d ( d 是任给的一个最小控制集) ，那么与z 相 连的叶子必须在d 中 我们令 d l = ”l ，叶 ，其中 + ，嘶 = s ( t ) 则 口，地) 3 y v ( t ) ：m ( y ) 兰3 1 0 硕士学位论文 m a s t e r st h e s i $ 1 面甄i i _ i 忑面亍：瓦i j 毳瓦面孬磊i 瓦i _ 砾 s ( ，) ，z 。+ i f 一，q 一，d 于是存在与。一，如。相连的叶子y i j 一，y , n d 记 f o ：= y t 胁 ；e o ：= d 中除一，以外的叶子) i ：1 ：= z l ，- z m ；e 1 = 。d ：3 1 7es ( 丁) ) = z m + 1 ，一，z 1 一， f 2 ：= z d 1 ：m ( x ) = 2 ；易：= 。d ：m ( x ) = 2 f 3 ：= f z d l ：m ( x ) 23 ；晶：= z d ：，n ( z ) 3 ) 这样d ；局u e o u 尻u 易u 扇 为 d l = s ( t ) uf 2 u f 3 由于f o u 蜀只控制树t 的一个内点，而e 1u 疡u 玛控制的内点个数最多 e( r e ( x ) + 1 ) ，所以由d 是树t 的控制集和命题2 2 得 x e e t u 如u e 3 s 社( 岛u e o ) +( m ( z ) + 1 ) x e e i u e 2 u e a 显然由假设得f o 多并且通过观察，我们发现# f o = 弗f i ，辛f l + 带蜀= 带s ( r ) ，铂孝f 3 故可进一步得 s 带( f o u 玩) 十( m ( 。) 十1 ) z 风u e b u e 3 # e o + ( m 扛) + 1 ) + ( m ( z ) + 1 ) f 1 z 口lu e 2 u 岛 = # e o + ( 仇扛) + 1 ) + f m ( z ) + 1 ) z s ( t ) z e 2 u e a 硕士学位论文 m a s t e r st h e s i s 因为 徉d = # d i( 2 ) 社d = 社f o4 - 社e o4 - # e l + 挣易+ 拳e 3 ，# e t4 - 孝f o + 带s ( t ) 拳d t = 舞s ( t ) + 孝f 24 - 群凡 、 斧s ( t ) = 带s ( 丁)( 3 ) f 2 ) 式减去( 3 ) 式得j ( 岛u e 2 u e 3 ) = 社( f 2 uf 3 ) ( 带( 蜀u e 2 ) = 带( 易u ( f 3 岛) ) 实际上 # e o + ( m ( z ) + 1 ) s3 ( 带玩u e 。) o e 2 ( m ( z ) + 1 ) + ( m ( 。) + 1 ) 3 ( 带( f 3 e 3 ) u b ) z f 2 o n e 3 这样( 1 ) 式可为 、 # e o + e ( m 扛) + i ) 4 - 【m ( z ) + 1 ) + ( m ( 。) + i ) z e s ( t ) 。岛z 6 e 3 s e ( m ( z ) + 1 ) + ( m 仁) + 1 ) 十( m ( 。) + 1 ) + ( m 0 ) + 1 ) z s 汀) ；f 2。e 3 z f 3 、e 2 ( m ( 。) + 1 ) = z d 1 得到矛盾故假设错误所以树t 中的s ( t ) cd ( b ) 其次证明：对于比矿( ? ) ，如果m ( x ) 3 ，那么。d 首先记 翰：= z d ：d ( z ) = 1 ；f l ：= s ( t ) ； e l ：= s ( t ) ；f 2 ：= 。d i ：仇( 。) = 2 ) e 2 ：= z d ：r n ( z ) = 2 ：f 3 ：= z d i ：m 。) 3 】2 硕士学位论文 m a s t e r st 儿e s i s 屁：= z d ：m ( 。) 3 所以e 1 = f l ，并由( a ) 的证明可得s ( t ) c d 其次用反证法假设存在一个。矿旧) ，m ( z ) 3 且。芒d ，则带e 3 挣f 3 于是由( a ) 述说的原因可得 ，c # e o + ( m 扛) + 1 ) + ( m ( z ) + 1 ) + ( m ( z ) + 1 ) x 6 e tz e 2z e e a = ( m 扛) + 1 ) + # e o + ( m 0 ) + 1 ) + ( r n ( z ) + 1 ) $ 6 s ( t ) 。e 2z ( m ( z ) + 1 ) + ( m ( z ) + 1 ) +( m ( z ) + 1 ) + ( 竹1 扛) + 1 ) 2 6 s ( t ) z e e 3 z e f 3 e 3r e e f 2 = ( m ( 茹) + 1 ) = 0 d l 得到矛盾 故得v x z v ( t ) ：m ( z ) 芝3 ，则。d ( c ) 最后证树t 中的所有的叶子不在d 中 反证法假设存在个叶子在d 中，那么由( a ) ，( b ) 可得 社髓= 社f l ，# e 3 = # f 3 ，# e o u e 2 = # f 2 因为社e 0 0 ，从而# e 2 ；成立，那么其他两种情况： 1 c j 情况一：7 = 。，。时，由鼍 j 1 得万；矗 ；7c一，c 一 情况二： 7 = 1 ， 0 时，由a 7 = 1 , a , y 。= 0 时此推论成立，即 等 j 1 所以鑫 ； 1 4 这样都有 工：! = 竺，三 吖：一7 。 3 下面我们来证明7 = l ，仉= 0 这种情况： 对于图g 7 来说，设d 是g 7 的一个最小控制集且h ( g ) cd ，由定理2 2 的 证明过程可得 一， 一 t s ( 社 仇 + ( m ( 仉) 一2 ) 1 ) +( m ( z ) 一2 ) 1 十2 = l x 6 v g ) 一l ( g 、d s ( ( m ( 巩) + 1 ) + ( m ( 地) 一2 ) i = l 令( 4 ) 式右边为磊k 了+ 虿r t 再+ j 2 距矿( g ) 一二( g ，卜d 2 ) + ( ，h ( z ) 一2 ) 2 + 4 z e v ( g ) 一l ( g ) 一d s 其中k = ( 带 q ) 。( m ( 咣) 一2 ) l t = l 著( 1 ) 式取不等号时，由定理2 2 的证明，可得7 ：! 2 ! 能一3 + 2 n + 4 一l 工：! 竺 ! 2 ! 二! ! 镌 一3 七+ 2 n + 4 一l 一3 下面讨论( 1 ) 取等号的情况，即= ( r e ( z ) + 1 ) 蚝d 如果存在z v ( g ) 一l ( g 7 ) 一d ，m ( z ) 3 ，则由 ( m ( z ) 一2 ) - 2 2 ， x e v g ) 一l ( g ，) 一d 1 5 硕士学位论文 m a sf e r st 4 _ i ：s i s 雨f 一 - y 7十( n 一1 ) l + l4 - 2 倪 3 k4 - ( n 一1 ) 24 - 2 十2 最后得丧= 等奇1 下面讨论v x v ( a ) 一l ( g 7 ) 一d m ( z ) = 2 的情形即图g 的任意一个最小控 制d 且日( g ) c d 都有= ( m ( z ) 4 - 】) 且v x v ( c ) 一l ( a ) 一d ，m ( 。) = 2 z d 的情形 我们知道，对于任意一个图g ，若连一条边e = u ，有，y ( g + e ) = 7 ( g ) 一1 ， 则存在图g 的- - + i b 控制集d ，使得u ，u d ，且v ( 札) c ( 口) 但根据定理 3l ，g 只有一个最小控制集，不妨设为d 因为= ( m ( 。) + 1 ) ，有定理2 2 中的证明的注，我们知道v u ，u d 都有n ( u ) nn ( v ) = 西因此在图g 中连接 任意不相连的两点都不能使控制数减少1 故7 = y ，丢 篆； 这样如果图g 的任意个包含所有钩子的最小控制集d ，都有 = ( m ( z ) 4 - 1 ) x e d 且比v ( a ) 一l ( g ) 一d ，m ( z ) = 2 ，那么此推论仍成立 综上所述，在a t , = 1 ，= 0 情况下仍有推论成立即得证 1 6 对于满足7 = 的图，s a r u m u g a m 等人给出了几个图类并充分描述这些图 类的特征 定理4 1 3 j 设图g 含有唯一的圈c ，c = u i u 2 u n u l ，n 5 设x 是c 上的所有二度点集，那么7 = 当且仅当下面的条件成立： ( a ) v v v 一v 】，如d g ( 口) 2 ，则7 2 是一个钩子； ( b ) 僻) 是连通的且1 x 3 ； ( c ) 若p 】= u 1 是( x ) 的连通分支，则对于v 口n ( v 1 ) ，有 是钩子， 若p i = ”i 啦是伍) 的连通分支，则n ( 口l ，v 2 ) 中至少存在点v ，使得 f 吲u ) 2 且v 是钩子， 若p l = u ju 2 u 3 是( x ) 的连通分支，则对于v v n ( u ! ，有d g ( ) 2 且” 是钩子 定理4 2 3 】设g 是连通图且s 是图g 最小连通控制集如果7 = 那 么，( ( s ) ) 2 且 是钩子， 若p 1 = u 1 口2 口3 是( x ) 的连通分支，则对于v n ( u l 3 ) ，有d a ( v ) 2 且口 是钩子， 证设s 是图的任意一个最小的连通控制集，那么1 s = 7 ( g ) = ( g ) 先证必要性 假设( a ) 不成立，那么j v ( g ) 一v x l ，d a ( v ) 2 ，但 不是钩子由s 的 连通性得”s 并且u 的所有邻点都在s 中那么s v 是g 的一个控制集，得到 矛盾故( a ) 成立 下证( b ) 假设w ( ( x ) ) 3 ，那么有两个事实： ( 1 ) 对于( x ) 不存在这样的连通分支，使得此连通分支上的所有点都在s 中 否则设( x ) 的连通分支g 1 ，v ( g 1 ) s 那么v v v ( g 1 ) ，设( ) = z ，) ，则 正，g s 于是有s _ u 仍是控制集，得到矛盾， ( 2 ) 如果w ( ( x ) ) 3 ，那么由( 1 ) 得j “1 ，t t 2 ，u 3 v ( c lu q ) 且 l j 1 ，u 2 ，u 3 两两 不相连，使得1 ，u 2 ，u 3 e s ，因为( g u l u 2 - - 2 j 【3 ) 不连通耳( 回是( g t 1 一札2 一壮3 ) 的导出子图，所以( s ) 不连通，得到矛盾故w ( ( x ) ) 2 同时如果w “x ) ) = 2 时，设这两个连通分支是g 1 ，g 2 ，基于上面的事实( 1 ) 和 事实( 2 ) 可得矿( g 1 ) y ( c t ) ，v ( g 2 ) cy ( q ) 下证( x ) 的每一个连通分支的p p l 3 用反证法，假设p = u t 啦u t o 4 ) 那么有一个事实，s 中不含有p 上的相邻两点否则设含有“i 啦+ l 相邻两 点( i = 1 2 ，一1 ) 于是要么s 一 珥) 是控制集，要么s 一 u i + 1 ) 是连通控翩 1 8 。 硕士学位论文 m a s t e r lst i i e s i s 这样由s 的连通性，又有下面的事实： 如果“l ，l t 2 9 s ，那么s 一 u 。 是图g 的控制集 如果啦山t t t 毛s ，那么s 一 u ，) 是图g 的控制集，得到矛盾 如果u l ，t t i - + - 1 9 s ( i = 1 ，2 ，t 一1 ) 那么( s u h ，+ 1 ) ) u _ u 。) 是图g 的 控制集，得到矛盾故( b ) 成立 最后证明( c ) 如果p l = ”1 是( x ) 的一个连通分支，那么， l 醪假没存在埘( u t ) 不 是钩子，令) n x = ( l ，。 ，由s 的连通性，z s ，那么s 一 砌 是控制 集，得到矛盾所以v v ( ) 都是钩子 如果马= 1 ) t 1 2 2 是( x ) 的一个连通分支，m l ，w 2 分别和”l ，”2 相连，且都不 是钩子因 叫l ，t ，2 中每一点的度都大于3 ，由s 的连通性，得”l ， t 0 2 s 那 么( s f w l ，叫2 ) u 是控制集，得到矛盾w ，2 中至少有个是钩子 如果p = u 1 j 2 v 3 是( 鄹的一个连通分支，叫l ，w 2 分别和1 2 1 ，v 3 相连，假设w l 不是钩子因( 虮，2 ) 中每一点的度都大于3 ，由s 的连通性，得w ，w 2 s 那 么【s 一 1 2 1 ，u l ) u 。) 或者( s 一 伽z ，地 ) u v 2 是控制集，得到矛盾假设w 2 不是钩子，那么( s 一( 耽，地 ) u ”2j 或者( s 一 枷2 ，”- ) u ( 。 是控制集，得到矛 盾叫l ，训2 中都是钩子 必要性得证 下证充分性 因为由( a ) ，对任意z v 一】，工都是钩子，故必须选人最小控制集 如果( z ) 的某个连通分支是p l = l ，设二v ( 口1 ) = 删1 ，枷2 ，根据( c ) 得t 0 1 ，1 8 2 是 钩子，必须选入最小控制集 如果连通分支p 3 = 1 啦”3 ，设枷l 和”l 相连，2 和u 3 相连，根据( c ) 得叫l ， 2 是钩子，则，2 必须选入最小控制集于是只剩下u 2 没有被控制要想啦 被拄制，则必须选入， 2 ，地中的一个点为最小控制集所包含所以为了保证连 】9 硕士学位论文 m a 5 1 e r st h e s i s 如果连