（运筹学与控制论专业论文）关于图的三类控制参数的研究.pdf

硕士学位论文 m a s t e r s t t i e s f s 摘要 本文主要研究了三类图的控制参数：图的下完美邻域数、图的受限控制数 和图的。控制数，并分为三章分别进行了讨论。 对于图的下完美邻域数，本文给出了e ( c ) = 1 ( g ) 的充分必要条件，并讨 论了一些特殊图类的下完美邻域数的上界，特别对于树采用了对所有点分层 的方法进行了较细致的讨论，并给出了紧上界o ( t ) ； 主要结论有： 定理2 4 ：图g 中，o ( c ) = 7 ( c ) 当且仅当e ( c ) = i ( g ) 定理2 儿：若丁是阶为n 的树，扎3 ，则口( 丁) i 7 7 , 对于图的受限控制数，本文主要讨论了其以边数为参数的上下界。主要结 论有： 命题31 ：n 阶m 边无孤立点连通图g 中，* ( g ) 2 ( n m ) ，且等号成立当 且仅当g p 4 命题3 2 ：n 阶图g 中，若最大度为、则* ( g ) 忐 命题34 ：n 阶图g 中，若最小度6 2 ，则1 ，( g ) n 一格 定理36 ：g = ( ve ) 是一个挖点m 边，m 行，最小度6 2 的简单连通图且 不包含图j l ，以，如为子图，则1 ，( g ) 盟掣 最后对于图的n 控制数，本文主要研究了z r 0 ( g ) 与i r ( c ) 的关系，给出 了n o r d h a u s g a d d u m 型( g ) + ( g ) 的界，从而解决了 7 文后提出的两 个问题另外还讨论了( g ) + 1 l 一。( g ) 不随q 变化的图类，在一定程度上解 决了 7 文后提出的公开问题2 主要结论有： 定理4 1 3 ：对于g = ( ue ) 的任一个极大n 一无赘集厶，存在一个基数i l l 的极大无赘集 推论4 1 4 ：若g = ( k e ) ，则i r ( g ) i r 。( g ) 硕士学位论文 m a s t e r st h e s i s 定理4 1 5 ：若g 和舀无孤立点，则当0 ( ￥j 1 时，y 。( g ) + 。( 召) n ；当 ； o 1 时，( g ) + ( 虿) 2 n 一4 关键词：图的下完美邻域数，图的受限控制数，图的n 控制数 儿 a b s t r a c t t h i st h e s i sm a i n l ys t u d i e st h r e ek i n d so fd o m i n a t i n gp a r a m e t e r so fg r a p h s ： t h el o w e rp e r f e c tn e i g h b o r h o o dn u m b e ro fg r a p h s ，t h er e f r a i n e dd o m i n a t i o nn u n l b e to fg r a p h sa n dt h eq d o m i n a t i o nn u m b e ro fg r a p h s a n dd i s c u s s e st h e mw i t h t h r e er e s p e c t i v ec h a p t e r s o nt h el o w e rp e r f e c tn e i g h b o r h o o dn u m b e ro fg r a p h s ，t h i st h e s i sg i v e st h e s u f f i c i e n ta n dn e c e s s a r yc o n d i t i o n so fo ( a ) = 7 ( g ) ，a n dd i s c u s s e st h eu p p e rb o u n d o ft h el o w e rp e r f e c tn e i g h b o r h o o dn u m b e ro fs o m es p e c i a lg r a p h s e s p e c i a l l y ，t h i s t h e s i sd i s c u s s e si to nt r e ei nd e t a i l sa n dg i v e st h et i g h tu p p e rb o u n do ( t ) ；1 b yu s i n gt h em e t h o do fd i v i d i n gt h ev e r t e x e so ft r e ei n t ol e v e l s t h e s ea r et h e m a i nr e s u l t sb e l o w ： t h e o r e m2 4 ：i ng r a p hg ，o ( a ) = 7 ( g ) i fa n do n l yi fo ( a ) = i ( g ) t h e o r e m2 1 1 ：i fti sat r e ew i t h 竹v e r t i c e s ，n 3 ，t h e no ( t ) f ； o nt h er e f r a i n e dd o m i n a t i o nn u m b e ro fg r a p h s ，t h i st h e s i sm a i n l yd i s c u s s e s t h eb o u n do fi tb ye d g en u m b e r t h e s ea r et h em a i nr e s u l t sb e l o w ： p r o p o s i t i o n3 1 ：i nt h ec o n n e c t e dg r a p hg w h i c hh a snv e r t i c e s ，me d g e sa n d n oi s o l a t e s ，( g ) 2 ( n m ) ，a n dt h eb o u n di sa t t a i n e di fa n do n l yi fg = p 4 p r o p o s i t i o n3 2 ：i nt h eg r a p hg w i t hnv e r t i c e s i ft h em a x i m u m d e g r e ei s t h e n * ( g ) 五n 耵 p r o p o s i t i o n3 4 ：i nt h eg r a p hg w i t hnv e r t i c e s 、i ft h em i n i m u md e g r e e5 2 t h e n1 ，( g ) n 一持 t h e o r e m3 6 ：i fg = ( ve ) i sas i m p l ec o n n e c t e dg r a p hw i t h 扎v e r t i c e sa n dr n e d g e s ，m n ，w h i c hd o e s n tc o n t a i nj 1 ，如，j a a ss u b g r a p h s ，a n dt h em i n i m u m d e g r e ed 2 ，t h e n * ( g ) 下m + 4 f i n a l l yo nt h eq d o m i n a t i o nn u m b e r o f g r a p h s t h i st h e s i sm a i n l ys t u d i e st h e r e l a t i o n s h i pb e t w e e ni r n ( g ) a n di r ( g ) a n dg r e s t h en o r d h a u s g a d d u m t y p e b o u n do f1 n ( g ) + 1 a ( g ) ，w h i c hs o l v e st w oo p e np r o b l e m so f 7 】a d d i t i o n a l l y ， i ta l s od i s c u s s e st h eg r a p h si nw h i c h ( g ) + 7 1 - a ( g ) d o e s n tv a r yw i t hn t o s o m ee x t e n t ，i ts o l v e st h es e c o n do p e np r o b l e mo f 7 】t h e s ea r et h em a i nr e s u l t s l u 硕士学位论文 m a s 亚r st h e s i s i ) e o w ： t h e o r e m4 1 3 ：f o ra n ym a x i m a ln i r r e d u n d a n ts e t 厶o f g r a p hg = ( ve ) ， t h e r ee x i s t sam a x i m a li r r e d u n d a n ts e to fg o fc a r d i n a l i t yn om o r et h a ni k c o r o l l a r y4 1 4 ：i fg = ( ve ) ，t h e n2 r ( g ) 7 ( g ) t h e o r e m4 1 5 ：i fga n dgh a v en oi s o l a t e s ，t h e nw h e n0 o ；1 ，w eh a v e 1 。( g ) + 1 n ( 召) n ；a n dw h e n 互i o ) 边的剖分定义为：引入一个新点t i j ，将边u o 替换为 t c w 和w v 将星的所有边剖分得到的树称为蜘蛛，若最多剖分星的n 一1 条 边得到的树称为受伤的蜘蛛若zev ，d ( z ) = l ，则z 定义为悬挂点，悬挂 点的邻点定义为钩子若连通图g 中存在p 3 ，使得g p 3 仍然是连通的， 则此岛定义为悬挂的b 本章的其他图论基本概念请参照参考文献” 2 硕士学位论文 m a s t e r st h e s i s 2 2 已知结果 引理2 1 ( 【2 d ：图g = ( ke ) ，对g 的任一个极小控制集d ，存在一个基数为 f d l 的g 的完美邻域集 推论22 ( 2 j ) ：对于任意图g ，o ( a ) 7 ( g ) 且r ( c ) e ( a ) g i 理23 ( 3 j ) ：图g 中有：i r ( g ) 7 ( g ) i ( a ) 口( g ) r ( a ) r ( g ) 2 3 主要结果 定理2 4 ：图g 中，o ( a ) = 7 ( g ) 当且仅当o ( a ) = f ( g ) 证明：“充分性”由推论2 2 和引理2 3 ，显然 “必要性”设d 是g 的1 集，由引理2 1 知存在阶为l d l 的完美 邻域集令d l = f 中孤立点 ，d 2 = d d l ，若d z d ，则任 取其中一点z ，由于z d 2 ，记t = n x nd 2 ，有 t i 2 ，又v v d 2 ， p ( 口，d ) g ，记p ( ) 为v 的任一个私有邻点，记s l 一如( u ) ： d z 且 隹t ) ，令s = d 1 u s l u z ) ，( 注：s l 可能为空集) ，则v v d 有l n v n s l = l ， 故d 中点均为s - 完美点，又d 是控制集，故v d 中任一点至少与d 中某点相邻，即至少与一个s 一完美点相邻，故s 是一个完美邻域集，且 1 s 1 1 d i ，则o ( a ) 1 s l 5 时，记p 凡为 z l ，t 2 ，t 。1 当7 io ( m o d 5 ) 时，可构造s = t 3 ，j 8 ，x n2 ；当nj1 ，2 ，3 ( r o o d 5 ) 时，可构造s = z 3 ，z 8 ，z 3 + 5 l 学i ，。) ：当n ；4 ( r o o d 5 ) 时，可构造s = x 3 ，x 8 ，x 3 + 5 【譬j ，x n _ l ，易知s 是r 的最小完美邻域集，故口( r ) = 1 5 1 命题2 1 0 ：若t k + l 为二叉树，则口( 矗+ 1 ) 3 茆r l ，k 5 n = i 瓦+ l i ( 二叉树t k + 如图1 所示) 图21 汪明：n = 2 0 + 2 1 + 2 2 + + 2 k = 2 k + i l 由于每一层点的个数为2 ，故我们构造完美邻域集s 中点时可考虑从 下层开始，又下层点只与一个上层点相邻，故若取某一层点为完美邻域集 4 硕士学位论文 m a s ie 1 1 st h e s i s 中点，则下两层和上一层点或是完美邻域点或是和完美邻域点相邻故可 从第k 2 层开始，令第k 一2 层点s ，然后取第七一6 层s ，依次向上递 归地选取s 的点，若ki0 ，1 ，2 ( r o o d 4 ) ，分析可知，只需讨论ki2 ( r o o d 4 ) 情形： o ( r k + 1 ) 2 k - 2 + 2 。一6 + 2 4 + 2 0 = 锷；竺尘= 而1 6l 。k - 2 2 4 ) = 而1 6 2 k - 2 _ _ 点 雨1 8 2 k 一1 若k i 3 ( m o d 4 ) ，则 p ( 瓦+ 1 ) 2 k 一2 + 2 一6 + 2 5 + 2 1 = 坐二等三掣= 丽1 6 i z k - 2 23 ) = 两1 6 2 2 2 一是 辕- 2 “2 1 故幽裂盐2 k 些+ l - - i 焉筹= 未，故目( 疋+ ，) 未n 定理2 1 1 ：若t 是阶为n 的树，n 3 ，则口( 7 1 ) ； 基，i ，灸蠢； ” 图22 证明：对n 用归纳法证明 当n 一3 时，t 是k l 故p ( 丁) = 1 ； ，命题成立 假定命题对于小于n 情形成立，下证对n 亦成立 找出丁的某最大度点( 若有多个，则任取其一) ，将它作为根，即第 0 层，其余点向下依该点到点v o 的距离分层次排列，分析可知，下一层点 只与一个上一层点相邻，否则会形成圈，与7 1 是树矛盾 若某钩子u 至少有2 个悬挂点z ，y ，则对丁一 z ，由归纳假设有o ( r 一 r ) 掣1 ，下面考察口( t ) 一集与o ( t 一 z ) ) 一集的关系，记目( 丁) 一集为s t ， p ( t 一 z ) ) 一集为岛，共有以下两种情形：( 见图f l ) 若钩子v 不是岛一完美点，则1 n v 】n s 2 l 2 ，不妨设s ( v ) = m n 岛， 若 s ( ”) ，则令g = 一s ( v ) + v ，) 1 否则令s l = 岛一s ( v ) + ) ，可得$ 5 硕士学位论文 m a s t e r st h e s i s 是丁一 z 的完美邻域集且i 曼l 由归纳假设知0 ( 7 一( z ，”，z ， ) 宁1 = ；1 1 考察日( 丁) 一集与口口一 z ， ，x i ) ) 一集的关系可知，记o ( t 一 z ，u ，z 7 ) ) 一集为岛， ：苜以下三种情形： 若口蜀，则s 4 可为t 的完美邻域集，故o ( t ) o ( t 一 z ，u ，i t ， ) 一l i 若 隹且”7 是s 4 一完美点，则u z ) 可为丁的完美邻域集，故 o ( t ) e ( t 一 z ， ，x i ) ) + l i 若u 7 & 且v 7 不是& 一完美点，则岛u 口 为7 1 的完美邻域集，故 o ( t ) e ( t 一 z ， ，z ，) ) + l 吲 综上知：命题对于n 亦成立，故o ( t ) ； - 7 硕士学位论文 m a s t e r st h e s i s 第三章图的受限控制数 3 1 基本概念及应用 g = ( ve ) 是一个图，v 点”v ， 的开邻域( u ) 定义为n ( v ) 一 “ 7 ：u u e ) u 的闭邻域n u 】定义为= n ( v ) u u ) 若s g ，v 点 “v s ，| 点 s ，使得“ e ，则称s 是g 的一个控制集。g 的控制 数1 ( g ) 定义为：7 ( g ) = m i n l s i ：s 是g 的控制集 ；若s y ，v z v s ， ( z ) n s l 1 ，1 ( z ) n ( v s ) l l ，则s 定义为g 的受限控制集受限控制 数的概念是由t e l l e 5 1 作为点划分问题引入的，易知每个图都有一个受限控 制集，因为s = v 可以是受限控制集令* ( g ) = m i n i s t ：s 是g 的受限控 制集 若s g ，s 是g 的受限控制集，且i s i = * ( g ) ，则s 称为( g ) 一 集。受限控制集的一个应用是囚徒和守卫例如：受限控制集以外的每一点 对应一个囚徒的位置，受限控制集中的每一点对应一个守卫的位置易知 每个囚徒的位置可以被某个守卫的位置监视( 为了有效安全) ，而每个囚徒 的位置也可以被至少一个其他的囚徒看到( 为了保护囚徒的权利) 为了最 有效率，我们应该安排尽可能少的守卫，也就是要求最小受限控制集 本章的其他图论基本概念请参照参考文献1 1 命题31 ：n 阶m 边 且仪当g = p 4 证明：2 m = d i ， 3 2 主要结果 无孤立点连通图g 中，1 r ( g ) 2 ( n m ) ，且等号成立当 考察g 中* ( g ) 一集r 知：v v v r ，有d ( u ) 2 ，故 n 2 m = d l 2 ( n 一* ( g ) ) + 1 r ( g ) = 2 n 1 r ( g ) ，所以* ( g ) 2 一m ) t = 1 若等号成立，则v y r ，有d ( u ) = 2 ，v r ，d ( v ) = 1 ，又由( g ) 定义知：v u y r ，口与r 中某点相邻且与1 7 一月中某点相邻，所以 i y r i = 2 ，l r l = 2 立当且仅当g = 只 否则g 不连通故g = p 4 反之显然成立故等号成 8 硕士学位论文 m s t e r sf i l t e s i s 命题3 2 ：n 阶图g 中，若最大度为，则1 r ( g ) 南 证明：设r 是g 的受限控制集，且 r j = * ( g ) ，令 ，是r 与v r 之间 的边集，从r 到v r 计数，则l a ，j d e g ( v ) ，从v r 到r 计数， u 尺 0 m l j v r ，故a ( e ) l r j d e g ( z ，) l ，l | v 一r l = n i r l ，所以 v 6 r 1 r ( g ) 寿 一 推论3 3 ：k 正则图g ，k 2 ，则1 ，( ( ；) 毒i 命题3 4 ：n 阶图g 中，若最小度6 2 ，则y r ( g ) n 一播 证明：由命题3 2 的证明过程知： d e g ( v ) n 一_ ( g ) ，故d e g ( v ) + u r r d e y ( v ) n 一* ( g ) + d e g ( v ) ，故2 r n n 一1 ，( g ) + d ( n 一( g ) ) ，故 ，( g ) n 一器 一 推论35 ：k 正则图g ，k 2 ，则1 r ( g ) n 一惫 定理3 6 ：g = ( ue ) 是一个n 点m 边，盯n ，最小度6 2 的简单连通图 且不包含图j l ，也，以为子图，则1 ，( g ) 丁m + 4 ：瓯”照、耸一 图3 i 证明：若m = n 时，g = g 易知： 当n = m i o ( m o d 3 ) 时，* ( g ) = ；= 警； 当n = m e 1 ( r o o d 3 ) 时，* ( g ) = 丁n + 2 = 孚 当n = m 1 2 ( r o o d 3 ) 时，* ( g ) = 丁n + 4 = 孚 故综上知： * ( g ) 丁r n + 4 若m n ，对m 用数学归纳法证明 9 硕士学位论文 m a s i e r s r i t e s i s 1 1 ) 若存在边e ，g 一 e ，满足题设条件，则由归纳假设知：* ( g 一 e ) ! 半一4 易知( c - e ) ) 一集可为g 的一个受限控制集，故* ( g ) * ( c - e ) ) 7 1 二攀 m t + 4 ( 2 ) 若g 中存在路p ：u 1 1 3 2 一 ，3 一呲一t 5 ，其中d ( v 。) = 2 ，i = 2 ，3 ，4 、则 对g = g 一 ”2 ，地，地) + e ) ，e = 。，1u 5 ，用归纳假设知：7 r ( g ) ! ! 寻生令 ，( g ，) _ 集为r l 若 u 1 ，u 5 ) r 1 ，则令兄= 兄lup 2 ) ；若 l r l ，譬r l ，则 令r = rlu 弛 ；若u l 隹r 1 ，r l ，则令月= r lu u 2 ；若口l ，t ，5 譬r l ，则 令r = r l u u 3 ) ；易知r 是g 的受限控制集，故，( g ) i r i = 7 r ( g 7 ) + l 孚+ 1 = 孚 苦( 1 ) ( 2 ) 均不满足，令w x = g 中度不小于3 的点 ，i = g 中度 勾2 的点 ，则有以下结论： ( a ) v z w 1 ，贝0u ( x ) t l j ，否4j t ，9 i i ，r y e ( c ) ，贝l jz ，分属 f ? t 的两个连通分支( 根据( 1 ) 可知) ； ( b ) 若z ，w l 且z ，可之间存在路：t u 1 一u 2 一z ，。一，其中 r ，( u 。) = 2 ，i = 1 ，2 p ，则p 2 ( 根据( 2 ) 可知) 由于6 2 ，故g 中至少存在一个圈，由于圈2 一连通，故g 中至少存 窿一个2 一连通的子集任取2 一连通的子集c ，有以下几种情形： 存在z ，gnw l ，若z ，之间存在路p ：3 2 一 l u 2 一，d ( t ，。) = 2 ， ，= 1 ，2 ，由于g 2 - 连通，则g 一 口1 2 ) 满足题设条件，记* ( g 一 u 1 u 2 一集 白见，由归纳假设有：* ( g 一 u l ，l ，2 ) ) 里二二学= 旦若z ，r 则吼可 勾g 的一个受限控制集，故1 ，( g ) 1 r ( g 一 u l ，u 2 ) ) 掣 掣；若t 吼， r ，1 7 2 ，则r 2 u 1 ) 是g 的一个受限控制集，故7 r ( g ) 1 ，( g 一( v l ，u 2 ) ) 十l 冬 ! + l = 丁r n + 4 ，若z 簪r 2 ，r 2 ，则r 2u ) 2 是g 的一个受限控制集，故 、( g ) 1 ，( g 一 u 1 ，u 2 ) ) 十l 里 十1 = m i + 一4 ；若t ，隹r 2 ，则r 2u u 2 ) ( 或者 n ) 是g 的一个受限控制集，故7 ，( g ) 1 r ( g 一 u ，2 ) 十l 丁7 r 。+ 1 十l = m r + t v z ，可c nw 1 ，若z ，可之间存在路： z 一掣l 一 2 _ 一 p 一，其 中f ，( 巩) = 2 ，j l ，2 ，p ，则p = 1 若存在某点z i kne ，n ( x ) c 、 l 己。v ( z ) = u 1 ，u 2 ，仇 ，t 3 ，由( a ) 知( z ) 1 由于c 2 一连通，故 f ；一u x i 连通 若g u x 】满足题设条件，令1 r ( g a f h ) 一集为r 。，则i r 3 掣 苦n ( n ( z ) ) 尺3 ，则r 3u ”1 可为g 的一个受限控制集，故* ( g ) 1 0 硕士学位论文 m s t e r s i h e s l s f 凡l 十1 掣；若( ( 。) ) nr 3 = 妇，则r 3u z 可为g 的一个受限控制 集，故( g ) j r 3 i + 1 t m + 4 ；若n ( x ) 中有s 个点，不妨设为是前s 个点， f u l ， 2 ，u s 的邻点r 3 ，当s t s 时，则r 3 u 。+ 1 ，u 。+ 2 ，v 可为g 的 一一个受限控制集，故( g ) l 飓j + ( t s ) m 等型十( f s ) = r n + _ 4 + j 厂t - 一3 s 雩； 当s t s 时，则r 3u l ，现，z 可为g 的一个受限控制集，故 ，( g ) l r 3 + ( s 十1 ) m - - 2 _ t + 一4 + ( s + l ) = 卫兰生产r n r + 4 ( f 6 ) ，事实上， t = 3 ，4 ，5 时同样成立。 镌键 图3 2 否则v x w in c ，3 y g 一| 7 v 有d o , 一_ 陋j ( y ) = 1 ，令d a ( y ) = f + l ，若 f 3 ( 如图日所示) ，则令g l = g 一 v m + e 1 ) ，c l = z 2 ，则g i 满足题设 条件，由归纳假设有：* ( g 1 ) _ m2 1 r - 1 + 4 令* ( g 1 ) 一集为r 4 ，若3 2 ，z 风 则令r = r 4 u v ；若x r 4 ，zgr 4 ，则令r = r 4u u ；若x 譬r 4 ，2 r 4 ， 则令r = 风u ， ) ；若z ，z 岳r 4 ，则令r = r 4u 口 ；易知兄是g 的一 个受限控制集，故* ( g ) 7 ，( g z ) + 2 孚若，= 2 ，若d ( z ) = 3 ( 如图 足所示) ，则令g 2 = g 一k y + e 2 ) ，c 2 = ：，则g 2 满足题设条件， 由归纳假设知：* ( g 2 ) t m - - 7 + 4 ，令( g 2 ) 一集为飓，若 ，z r 5 、则令 r ：= 尺5u l ，7 3 2 ；若w r 5 ，z r 5 ，贝0 令r = r 5u u 7 ， ；若w 车r 5 ，z 月5 ， 则令兄= r 5 ux ， ) ；若w ，z 垡r 5 ，则令r = r 5u z ， ) ；易知r 是g 的一个 受限控制集，故1 ，( g ) m + f 4 若d ( x ) 4 ，则令g a = g n y l ，则g a 满足题 设条件，由归纳假设有：* ( g 3 ) 丁m - 6 + 4 令* ( g 3 ) 一集为风，若z ，z r 6 则令r = 风u ；若z 风，z 车r 6 ，则令r = r 6u u ：若x 车风，o r 6 则令r = r 6u ， ) ；若z ，z 车r 6 ，则令r = r 6u y ；易知兄是g 的一个受 限控制集，故( g ) r 【l 如 + 2 m r + 4 g 中存在一个3 一圈且3 - 圈只有一个点w t ，则有以下三种情形( 如 图3 3 所示) ： 硕士学位论文 m a s t e r st i i e s i s ，毡。；冷一。，冷州 图3 3 c a s e l g 一 1 ，u 2 ，u 3 满足题设条件，设，( ( ? 一 1 ，u 2 ， ) 一集为岛 则r = r ，u u 1 ) 为g 的受限控制集又由归纳假设知：l r 7 i = 1 ，( g 一 u i 、u 2 ，地 ) m z a 3 c a ，故* ( g ) l r = l r 7 i + 1 等+ 1 鼍# c a s e 2 g 一 1 ， 2 ， 3 ，z ) 满足题设条件，设1 ，( g 一 l ，u 2 ，f 3 ，t ) 一集为月8 若y r 8 ，则r = r 8u 口3 ) 为g 的受限控制集。若y 隹r 8 ，则r = r 8u u 2 ) 为g 的受限控制集又由归纳假设知：l r 8 i = ，( g 一 l ， 2 ，u 3 ，z m - - + 4 故* ( g ) l r l = i r 8 l + 1 掣+ 1 丁m + 1 c a s e 3 g 一( 饥， 2 ， 3 ，z ，) 满足题设条件，设h ( g 一 u 1 ，u 2 ，珊，x ， ) * 集为r 9 ，若z r 9 ，则r = r 9u u 2 ) 为g 的受限控制集若z 岳r 9 ，则 尺= r 9u z ，y 2 ) 为g 的受限控制集又由归纳假设知：l r 9 i = * ( g 一 t ，1 u 2 ，v 3 ，z ，可) ) m - 广6 + 4 ，故一y ，( g ) i r l i r 9 i 十2 学+ 2 = m 3 + a g 中存在一个4 一圈且4 一圈只有一个点v q ，由于不含禁止子图j - 故只有以下两种情形( 如图3 4 所示) ： 耳o ：轴 图34 c a s e 4 g 一 v 2 ， 3 ，”4 ，z 满足题设条件，设1 r ( g 一 u 1 ，u 3 ，? j 4 ，z ) ) 集为r l o ，若r 1 0 ，则r = r l ou t k ? 2 4 ) 为g 的受限控制集若p 隹r i o 则r = r 。ou 2 ，v 3 ) 为g 的受限控制集又由归纳假设知：l r l 0 1 = * ( g 一 “l ，u 2 ，u 3 ，u 4 ，z 卫型3，故* ( g ) i r i = j 尺l o i + 2 m - - r 6 + 4 + 2 = 里# c a s e 5 g 一和1 ，t 2 ，u 3 ，v 4 ，z ，可 满足题设条件，设仉( g 一 ， 2 ， 3 ，u 4 ，3 7 ， ) 集为r 1 l 若z r 则r = r 1 1u 如2 ， 0 3 ) 为g 的受限控制集若z 隹r 1 1 1 2 硕士学位论文 m a s t e r sf i i i e s i s 则r = r 1 1u 扛，v 4 为g 的受限控制集又由归纳假设知：f 兄l l f = * ( g 一 ? ，1 ，u 2 ， 3 ，u 4 ，x ，可华，故1 ，( g ) l r l = l r l 】l + 2 学+ 2 丁m + 4 g 中存在一个5 一圈且5 一圈只有一个点w 1 ，由于不含禁止子图 。，2 ，也，故只有以下一种情形( 如图3 4 所示) ： c a s e 6 g 一( ”1 ，u 2 ，v 3 ，蛳， 满足题设条件，设* ( g u l ，屯 3 ， 4 ，? ，5 ) ， 集为r 1 2 ) 若x r 1 2 ，则r = r 1 2u 4 ，地) 为g 的受限控制集。若z 岳r 1 2 则r = r ，2uf l ，7 2 3 ) 为g 的受限控制集。又由归纳假设知：i 尺- 2 i 一* ( g p l ，观， 3 ，蛳，y 5 ) ) 华，故啊( g ) i r i = i r l 2 i 十2 r n 丁- 6 + 4 + 2 = 丁m + 4 综上知：m n 3 ，最小度d 2 且不含禁止子图j 1 ，也，如时， 一 说明考察图j - ，也，如，我们发现以上情形所采用的去边加点的方法对这三 个图不适用，因此只有采用禁止子图条件将它去掉 1 3 硕士学主论文 m a s l e r s i i i e s i s 第四章图的q 控制数 4 1 研究背景及基本概念 n 控制数的背景：考虑s t 的棋盘，王图的每个点代表棋盘的一个 格点，连接图中两点当且仅当棋盘上的王在这两点间移动( 王可以水平、垂 直、对角移动) d a v i dw o o l b r i g h t 在9 1 中提出这样个问题：在6 6 的排 列格点上安排守卫或者囚徒，要求每个囚徒和守卫相邻的个数至少和和囚 徒相邻的个数一样多( 相邻可以是垂直、水平或者对角) 。m a r kl i a t t i 在1 0 1 中给出了这个问题的最小点集这个问题可以推广为：图g 的、, v o o b r i g h t 数是g 的某个点子集s 的阶数，s 满足：不在s 中的每个点在s 中的邻 点的个数至少和不在s 中的邻点个数一样多且s 尽量小。这个问题即转化 为求王图k 6 6 1 的w o o l b r i g h t 数。再将v b o l b r i g h t 数推广，我们引入了c t 控制数的概念若0 1 ，s v ，v 点u v s ，有 ( ) ns o f ( u 则定义s 是a 控制集若对于v x s ，j n l i 且譬s 一 z ) ，满足 i n ( ) n ( s 一 z ) ) l o i ( g ) ，则s 定义为n 一无赘集。 本章的其他图论基本概念请参照前面章节及参考文献1 4 2 已知结果 命题4 1 ( f 7 d ：如果r 是一条n 点路，则 1 n ( r ) = ； 1 。( r ) = l j j 命题4 2 ( ( 7 ) ：如果g 是一个n 点圈，则 1 。( c 。)