碩士學(xué)位論文 ma s t e r s t i i h s i s i v ( d j i 53的 分支; 部分二為 價(jià) d d i_ 4 的 分支。 若m = v d - l中 不 存在與部分 二中 至少兩個(gè)分支關(guān)聯(lián)或與兩部分中的分支同時(shí)關(guān)聯(lián)的點(diǎn)，則兒= 。 同時(shí)這篇文章用另外一種更簡(jiǎn)單，更直觀的方法重新證明了 2 1 中的一個(gè) 定理:對(duì)所有階為 n的樹 t ,若 t s h , 則 y , -( n + 2 ) 1 3。這個(gè)證明方法主 要應(yīng)用了下面這個(gè)定理，這也是本文的一個(gè)主要結(jié)論: 定理4 . 3 :設(shè)d是樹t 的余控制集， d 有p 個(gè)連通分支: d i , d 2 ,馬 m是t 關(guān)于d的中介點(diǎn)集， 則m可劃分為s個(gè)中介點(diǎn)組: m , , m 1 , 、 一， m s 且 s 5 u 一 1 , 訓(xùn) ,u + s 一 t o 另外作為這篇文章最重要的 一部分， 我們證明了o d i 1 e f a v a r o n 的一個(gè)猜 想，也既是在樹中小控制數(shù)與全控制數(shù)的比值上界問題: 定理4 . 4 樹t 的階為n 夕， 則y r.閉石3 y r 口 沖 - 1 關(guān)鍵詞:全控制集，小控制集，中 介點(diǎn)，中 介點(diǎn)組， 控制數(shù) a b s t r a c t w i t h i n t h e l a s t m o r e t h a n t w e n t y y e a r s , c o n c u r r e n t w i t h t h e g r o w t h o f c o m p u t e r s c i e n c e , g r a p h t h e o r y h a s s e e n e x p l o s i v e g r o w t h . p e r h a p s t h e f a s t e s t g r o w i n g a r e a w i t h i n g r a p h t h e o r y i s t h e s t u d y o f d o m i n a t i o n i n g r a p h . c o c k a y n e a n d h e d e t n i e m i s s u r v e y o n d o m i n a t i o n a p p e a r e d i n 1 9 9 7 a n d c o n t a i n e d 2 0 r e f e r e n c e s . t h i s s u r v e y p a p e r s e e m s t o h a v e s e t i n m o t i o n t h e m o d e r n s t u d y o f d o m i n a t i n g s e t s i n g r a p h s . i n 1 9 9 0 , t h e n u m b e r o f r e f e r e n c e s o f t h i s k i n d h a s i n c r e a s e d q u i c k l y f r o m 2 0 t o 4 0 0 . s e v e n y e a r s l a t e r m o r e t h a n 1 0 0 0 r e s e a r c h p a p e r s h a d b e e n p u b l i s h e d o n d o m i n a t i n g s e t s a n d r e l a t e d s e t s i n g r a p h s ， a n d t h e f i e l d i s s t e a d i l y g r o wi n g . i nt h i s p a p e r，w e d i s c u s s t h e r e l a t i o n s h i p b e t w e e n t h e t o t a l d o m i n a t i o n n u m b e r a n d t h e l e a s t d o m i n a t i o n n u m b e r. t h e t o t a l d o m i n a t i o n n u m b e r o f a g r a p h i s t h e m i n i m u m c a r d i n a l i t y o f a d o m i n a t i n g s e t o f g s u c h t h a t e v e r y v e r t e x i n v h a s a t l e a s t o n e n e i g h b o r i n d . t h e l e a s t d o m i n a t i o n n u m b e r o f 口i s t h e m i n i m u m c a r d i n a l i t y o f a d o m i n a t i n g s e t o fw h o s e d o m i n a t i o n n u m b e r i s t h e m i n i m u m . i n 4 , e . s a m p a t h k u m a r d i s c u s s e d t h e r e l a t i o n s h i p a m o n g t h e l e a s t d o m i n a t i o n n u m b e r， t h e t o t a l d o m i n a t i o n n u m b e r a n d o t h e r p a r a m e t e r s i n a g r a p h . i n ( 2 j , o d i l e f a v a r o n p o i n t e d o u t a m i s t a k e i n ( 4 j a n d g i v e a n u p p e r - b o u n d o f y , / y , . b u t h e a l s o p o i n t o u t t h i s b o u n d p e r h a p s i s n o t t h e b e s t . i n t h i s p a p e r，w e f i r s t g i v e s o m e s u f f i c i e n t c o n d i t i o n s f o r y = y , i n a t r e e t : t h e o r e m 4 . 1 : l e t d b e a y r s e t o f t , i f t h e v e r ti c e s o f d a r e a l l h o o k s a n d e a c h m id d l e v e r t e x o f t r e l a t i v e t o d h a s o n l y o n e n e i g h b o r i n d , t h e n y l = y , t h e o r e m 4 . 2 : l e t d b e a y , - s e t o f t , i f t h e c o n n e c t e d c o m p o n e n t s o f d : d 1 , d 2 , y l=y ,。 d , v e rt i c e s o f d a r e a l l h o o k s a n d t h e s a t i s f i e s i v ( d , ) 1_ 3 ( 1 5 1 0 , t h e n c o r o l l a r y 4 . 2 . 1 : l e t d b e a y , - s e t o f t w h e r e t jb p 1 , p 2 ， a n d d 1 , d 2 , ， 馬t h e c o n n e c t e d c o m p o n e n t s o f勿 7 . i f t h e v e r t i c e s o f d a r e a l l h o o k s , d e v i d e d 1 , d 2 ,，一馬 i n t o t w o p a r t s : p a r t o n e s a t i s f y i n g i v ( d d i_ 3 ; p a r t t w o s a t i s f y i n g / v ( d ,) / 夕 4 . i f t h e s e t m = v -d -l h a s n o v e r t e x t h a t i s a d j a c e n t t o a t l e a s t t w o c o m p o n e n t s o f p a r t t w o o r o n e c o m p o n e n t b o t h i n p a r t o n e a n d p a r t t w o , t h e n y c = y ,。 a n d w e a l s o r e p r o v e o n e o f t h e t h e o r e m t h a t:f o r e v e r y t r e e t o f i t w i t h o r d e r n w e h a v e y , 異 ( n+ 2 )/3 b y t h e f o l l o w i n g t h e o r e m : t h e o r e m 4 . 3 : l e t d b e a t o t a l d o m i n a t i n g s e t o f t , :d 1 , d 2 , 、 馬 t h e c o n n e c t e d c o m p o n e n t s o f ( d 了 . m i s t h e m i d d l e v e r t i c e s s e t o f t r e l a t i v e t o d , t h e n m c a n b e d i v i d e d i n t o s v e r t i c e s g r o u p s : m1 , m2 二， 麟 a n d s 5 u 一 1 , 訓(xùn) 1 2 +s 一 t o i n f a v a r o n t h e o r e m 4 . a d d i t i o n , a s t h e m o s t i m p o r t a n t p a r t , w e p r o v e o n e o f o d i l e s c o n j e c t u r e s : 4 f o r e v e r yt r e e t , w e h a v e y l 田百 3 ) ， r 刀 ! 2 - 1 k e y w o r d s : m i d d l e v e r t e x t o t a ls et a g r o u p d o m i n a t i n g o f m i d d l e l e a s t d o m i n a t i n g s e t , v e r t i c e sd o m i n a t i o n n u m b e r . 碩士學(xué)位論文 ma s t e r s t v i r s i s 1引言 在過去的二十幾年中， 隨著計(jì)算科學(xué)的迅速發(fā)展， 圖論得到了前所未有的 巨 大發(fā)展， 而其中發(fā)展最快的也許就是關(guān)于圖的控制數(shù)的研究 。 其發(fā)展速度之 快從關(guān)于此方面的論文數(shù)量可窺見一斑: 最早關(guān)于控制的綜述文章發(fā)表于1 9 7 7 年， 其中包括了二十篇參考文獻(xiàn).這類文獻(xiàn)的數(shù)目 發(fā)展到 1 9 9 0 年， 己 經(jīng)超過了 4 0 0 篇， 而到1 9 9 7 年 ， 更是 達(dá)到了1 0 0 。 余 篇的 驚人數(shù)目 ， 并且仍然 保持 著一定的 速度不斷的發(fā)展。 眾所周知， 科學(xué)源于實(shí)踐， 控制數(shù)的研究之所以得到如此突飛猛進(jìn)的發(fā)展， 與它深刻而廣泛的應(yīng)用背景是息息相關(guān)的。 各種控制集的研究從最初的最小控 制集到獨(dú)立控制集， 無贅控制集， 全控制集， 小控制集， 連通控制集， 距離控制 集， 強(qiáng)控制集， 弱控制集等等， 都有其獨(dú)特的應(yīng)用背景。 以本文的小控制集為例， 假設(shè)有一個(gè)內(nèi)部連通的通訊網(wǎng)絡(luò)， 把它看作一個(gè)圖， 用 n 個(gè)點(diǎn)表示刀 個(gè)通訊站， 兩點(diǎn)相連表示兩個(gè)通訊站可以直接互傳信息。現(xiàn)在假設(shè)要設(shè)置一些發(fā)送站 i , 如果要求信息從發(fā)送站經(jīng)過一次發(fā)送后， 到達(dá)所有的通訊站， 求發(fā)送站的最小 個(gè)數(shù)就是求圖的最小控制集; 如果放寬要求， 要求經(jīng)過兩次發(fā)送后， 所有的通訊 站收到信息。首先信息從發(fā)送站 i發(fā)出后， 在第一時(shí)間內(nèi)到達(dá)的通訊站叫做中 轉(zhuǎn)站， 記為z o 要想第二時(shí)間內(nèi)， 信息到達(dá)所有的通訊站， ( i u z ) 必須是圖的控 制集， 而且要想使發(fā)送站的個(gè)數(shù)達(dá)到極小， i 又是z 的最小控制集。 這樣， 要使發(fā) 送站的個(gè)數(shù)達(dá)到最小， 就要求圖的一個(gè)控制集， 使得這個(gè)控制集的最小控制數(shù) 最小。這其實(shí)就是圖的小控制集的概念。 本文著重研究了 樹中全控制數(shù)與小控制數(shù)的關(guān)系， 給出了它們?cè)跇渲邢嗟?的一些充分條件， 并給出小控制數(shù)與全控制數(shù)比值的一個(gè)上界。 碩士學(xué)位論文 ma s t e r s t i i e s i s 2主要定義的簡(jiǎn)單介紹 對(duì)簡(jiǎn)單圖g ( v , e ): ( 1 ) 控制集: 設(shè)a c_ v ,若對(duì)任意的:。v - a ，有n ( v ) n a -; 6 0 ，則稱a 是 的一個(gè)控制集， 記 y ( g ) = m i n 加/ a 是 的控制集 ; ( 2 ) 全控制集: 設(shè)d c_ v ,若對(duì)任意的 。 v , 有n ( v ) n dz - 0 ，則稱d 是 的一個(gè)全控制集，記 y , ( g = m i n 加/ d 是 的全控制集 ; ( 3 ) y一 集合: 若d 是 的 全控制集，且滿足 加八 y ; ， 則 稱d 是 的一個(gè) y 一 集合 ; wk - 覆蓋: 設(shè) c c _ v , 若對(duì)任意的v e v ，都存在c中的某點(diǎn)使得 v 到其距離 不超過k ，則稱c是g的 一個(gè)k - m蓋; 記c k ( g ) 二 。 i n ic l i c是g的k - 覆蓋 ; ( 5 ) c 1, 一 集合: 若c 是g的k - 覆蓋， 且滿足ic i= c k ， 則稱c是g的一個(gè)c k 一 集合; ( 6 ) 小控制集: 設(shè)x cv ， 若x是g的一個(gè)控制集， 且 對(duì)于g的 其它任意一個(gè)控制 集x , ， 均有y ( x l ) s y ( i x i1 ) ， 則稱x是g的小控制 集; 記y c ( g ) = m i n ( ja i x是g的小控制集 ， 此處(xi 表示g的點(diǎn)集x的生成子 圖; ( 7 ) y l 一 集合: 若x是g的小 控 制集， 且滿足ix i- y c ，則 稱x是g的一個(gè)a 一 集合; 顯 然i x 的最小控制集就是圖的c z 集合。以 下圖為 例: u i v / wi u 2 v 1 w? u 3 v 3 w3 u 4 v 4 w4 u k v k wk g助2 注: i v ( g ) i= 5 k , ， :( g =3 k，r : ( )=2 k + 2，其中 x = f u , v l, w l, u v y , w 2 , . u k , v k, w k 就是一個(gè) y l 一 集合;c = v i, v 2, 一 、 v k / 是 x 1 的 最小 控制集， 也 即是圖 的c 1 噢 合; 而f u l, w k , w l, u l r w y u s .， w k - l, u k / 是一個(gè) y i 集 合。 對(duì)樹t ( v e ) : ( 8 ) 葉 子: 在 樹中 ， 把 度為1 的 點(diǎn) 稱為葉 子 ， 記l = ( x i x e v 且x 是t 的 葉 子 ; ( 9 ) 鉤 子 : 把 與 某 個(gè) 葉 子 相 鄰的 點(diǎn) 稱 為 鉤 子 ， 記h = (y l y e v 且y 是t 的 鉤 子; ( 1 0 ) 中 介點(diǎn) 集: 若d是 樹t 的 一個(gè)全控制 集， 我們稱v d l 是t 關(guān)于d的 中介點(diǎn)集，記為m;稱每個(gè)點(diǎn)x e m為 t 關(guān)于d的一個(gè)中介點(diǎn); ( 1 1 ) 中介點(diǎn)組: 設(shè)m, c m， 若 mil是 ml的連通子圖， 且對(duì)任意的點(diǎn) x e m - m l ， 有 m u ( x 刀 是不 連通的， 則 稱m i 是t 關(guān)于d的一 個(gè)或一組中 介 點(diǎn)。 另 外， 以d , d z , . . 環(huán)表示 d 的 各 連 通 分 支， 若n ( m ,) n d r # 0 ( 1 :5 ) , 稱分支d ， 是m , 的關(guān)聯(lián)分支. 其中n ( m i) 表示與m, 中某點(diǎn)相鄰的 所有頂點(diǎn)。 其他未說明的符號(hào)及術(shù)語， 我們依照c s i 3 已知的主要結(jié)論 對(duì)于圖g = ( v e ) ， 己 知 1j = n ; 我們有如下結(jié)論: 命題3 . 1 : y ( g ) y t ( g, y ( g ) 5 y ,( g ) ; 命題3 . 2 : y t ( g ) s n - d其中d 表示圖中點(diǎn)的最大次; 命題3 .3 : y r ( g ) n 一 x ( g ) ，其中x ( g表示圖g的 連通度; 定理3 . 1 : 若g是樹， 則有y , ? ( n + 2 ) ! 3 ; 定理3 . 2 : 若g是樹， 則有y t :5 3 ( 3 y , 一 2 ) / 5 ; 定理3 . 3 : 若g連通， 則有y t 5 3 n / 5 ; 對(duì)樹 不 有如下結(jié)論: 命題3 . 4 :樹 t的每個(gè)全控制集必包含所有鉤子; 命題3 . 5 :除了 星蜀， 。 _ ， 外， 每個(gè)樹t 都有一個(gè)不含葉子的y r- 集合 命題3 .6 :除了p i , p 2 外， 每個(gè)樹t 有一個(gè)含所有鉤子且不含葉子的， t 一 集合; 命 題3 . 7 : 記 h一 廠i t 是 樹 且具 有性 質(zhì): t 的 每 個(gè) 鉤 子 上 有 且 只有一 個(gè)葉子 ， 若 t o h 可通過在 t中去掉最小數(shù)目的葉子得到 t e h ， 此時(shí)稱 t 為 t 在 h 中的相關(guān)樹，且有y l ( t ) = y t m，y r ( t ) = y , ( t ) 碩士學(xué)位論文 ma s i l r s t i i c s i s 4主要結(jié)果 4 . 1 樹中y 二， 。 的一些充分條件 o d i l e f a v a r o n 在 2 中 給出了 樹的小控制數(shù)與全控制數(shù)比 值的一個(gè)上界 y i/ y , 5 9 / 5 , 但可以 看到即 使在樹中， y t 與y : 的 大小關(guān)系也是不確定的， 如圖2 的三圖a , b , c 所示， 分別滿足y l ” v v 2 v 2 v 2 v 4 v j v 6 v 7 v y v 9 x , y i x 2 為x 3為 w v w, w 2 w 3 1 v 4 1 v 3 w 6 1 v 7 嘰 w 9 u , u 2 u 2 u 4 “ j“ u, r y y i p y 7 = 1 0 y c = y , 6 y 2 = 1 2 y , = 1 0 圖 2 注 :對(duì)于圖a , x l = ( v o , v 2 , v 3 , v 4 , v 5 , v 6 , v 7, v 9) 是 其y l 一 集合，c i = ( v o , v 3 , v 6 , v 9) 是其c 2 一 集 合;d i = ( v 0 , v i , v 2 , v 3 , v 4 , v 5 , v 6 . v 7 . v 8 . v 9 ) 是 其y : 一 集合; 對(duì)于圖b , x 2 = d 2 = ( x i, y i ,x 2 ,y 2 ,x 3 ,y 3 ) 是其 y l 一 集合和 y 一 集合;d 一 (x i ,x 2 ,x 3) 是其 c 2 一 集合; 對(duì)于圖 x 3 一 ( w o , w i, u i , w 3 , u 3 , u 4 , u s , u 6 , w 6 , u 8 , w 8 , w 9) 是 其y l - 集 合 ，c 3 = ( w l, u 3 , u 6 w 8 , 是c 2 一 集 合; d 3 = ( w o , w i , w 2 , w 3 , w 4 , w 5 , w 6 , w 7 , w 8 , w 9 ) 是其y ， 一 集合 下面就樹t 中y l = y ， 的條件做了 一些積極的探討， 目 前尚 無此方面更進(jìn)一 步的結(jié)果。 引理4 . 1 :設(shè)d是樹t 的y r 集合，若周2 是t 的連通子圖，則y t 勻 碩士學(xué)位論文 m a s t g r s t i i e s i s 證明:顯然t = p i 時(shí)結(jié)論成立;若t = p 2， 有y l = 1 , y , = 2顯然有y l _ 1。 若in (x ) n d i ? 2 ， 因?yàn)? d 是連通的， 必然得到t中含圈， 矛 盾。故n ( x ) n d i 一 。 假設(shè)存在x e v - l ) 而x o l , ff /j d 7 f x ) ? 2， 則必 有 一 點(diǎn)x , e v - 1 ) 使 得， x , e e。設(shè)n (x ) n d = ( v ) , n (x l) n d = v , ， 因 為 d 是連通的， 所以v 和v ， 之間在z p 1 中存在一條路， 故x x i v , . . . . . . v x 是一個(gè)圈， 矛盾。由xn l =0, v d c l， 可得 x c d。所以y l 今 得證。 定理 4 . 1 介點(diǎn)都只 : 設(shè)d是樹t 的y r 集合， 若d中每點(diǎn)都是鉤子， 且t 關(guān)于d的每個(gè)中 與 d 的一個(gè)連通分支相關(guān)聯(lián)，則兒 一 y , 證明: 設(shè)x是樹t 的一個(gè)包含所有鉤子且不含葉子的y l 一 集合，并設(shè)a是 2 方 7 的 控制集且a i = y ( x i )。 首先， 顯然有d c_ x ; 假設(shè)d ;k x ， 即d c x , 不妨設(shè)x = d u m i ， 這里m c m 。若存在y。m , ，由 條件y 只與 d 的 一個(gè)連通分支相關(guān)聯(lián)， 不妨設(shè)n (y ) n d = ( v ) , n (y ) n m , = ( y i ,y a . . . . . . y d k ? l : 若 y % a ，則令 x = x - ( y ) , a 一a ;顯然 x 是樹 t的控制集，且 y ( x ) :s y ( l x ) ，這與x 是y c 一 集合矛盾 ; 若y s a ， 則令x = x一 ( y )一 f ( n (y ) n m d一a a = a -( y ) u ( v ) , 顯然x 也是樹t 的控制集， 且 y ( ! x 1 ) s y ( ! x 1 ) ， 矛盾。 故ml = o ，即 a=ja i ，! d i = y , ， 命題得證。 定理4 .2 :設(shè)d是樹t 的y r 集合， 若d中每點(diǎn)都是鉤子， 且 d 的各連通分支 d i , d a , ，d滿足:i v ( d ; ) i_ u + 1 ;若i 7 0 , 令e ( d ;, a n m ) 表示 點(diǎn) 集d ， 與a n m間 所連的 邊數(shù)， e ( g )表示圖g的 邊數(shù)， 則對(duì)任何i e i都有e ( d i, a r m ) _ id , i e 因此， e ( ( ( u i c, , d ) u (a n m ) ) _藝 ( e ( d j ) + e ( d ;, a n m ) ) ? ii i十藝 i d i l 另一方面，因?yàn)閠是樹，所以 e ( f ( u , e , d ) u( an m ) ) 5藝 i d il+ a n m i 由此我們得到 】 a n m i 酬i i + i，進(jìn)而 i a i ? i a n g +藝 i a n d i i ? ( ii i + 1 ) + (1 u 一 14 ) 一 u + 1 。 由上分析知， 不管哪種情況， 均有 y ( i x i ) ? k 。故 )權(quán) 少 y ( i d ) 得證。 所以， d是 樹t 的 一個(gè)小控制集， 那么 d i ? y c . 又由已 知， 樹t 存在 一個(gè)包含所有 鉤子的y : 一 集合， 所以r l ? 1d 1 7 碩士學(xué)位論文 ma s t r s t i i g s i s 綜上可知a= y r 。 推 論4 . 2 . 1 :設(shè)d是 樹t 的y r 集合， t f乃 p 2， 且d中 每點(diǎn) 都是鉤子， d r . d 2 , ， 馬 是 d 的 各連通 分 支， 把d , d 2 、 馬 分為 兩 部分: 部 分一為 i v ( d j 1 :5 3 的分支; 部分二為 v ( d d j_ 4 的分支。 若“= v z 一 藝中不存在與部分 二中 至少兩個(gè)分支關(guān)聯(lián)或與兩部分中的分支同時(shí)關(guān)聯(lián)的點(diǎn)，則y l = y e 。 證明:設(shè)x是 t 的包含所有鉤子且不含葉子的小控制集，即有x n l = (p 。 由 定理4 . 1 可知， 只與2 勿的一個(gè)分支相關(guān)聯(lián)的中介點(diǎn)不在x中 。 那么由 此和 己 知條件知， x中的中介點(diǎn)只與部分一中 ! d i 的分支相關(guān)聯(lián)， 又由 定理4 . 2的 證明， 我們知道只與部分一中 分 支相關(guān)聯(lián)的中 介點(diǎn)一定不 在 ( x 1 的最小控制集 中， 從而也必不在x中 。 所以， x n m二 0 ; 又x包含所有鉤子， 所以 ja i = id i ， 即 a=y r 妙. 2定理3 . 1 的另一個(gè)證明 下面從另外一個(gè)角度重新證明了 2 1 中的一個(gè)定理，并根據(jù)證明的過程構(gòu) 造出達(dá)此下界的圖例，從而說明此下界是最好可能的。 定 理4 . 3 : 設(shè)d是樹t 的 全 控制 集， 2 切有k 個(gè)連通分 支: 切 d 2. . . . . . 馬 m是t 關(guān)于d的中介點(diǎn)集， 則m可劃分為:個(gè)中介點(diǎn)組: 場(chǎng)， m 2 一 ， 從且 s _ 2 ( 1 :h is s)，由 此我 們 得到2 s _ ( n + 2 ) / 3， 得證。 否則， 設(shè)d是樹t 的 不含葉子的y +一 集合，以d i , 場(chǎng)， ， 壞記 z p 了 的 各連通 分支。首先，由 于d是t 的全控制集，即 2 勿中 沒有孤立點(diǎn)，所以n 印/ 2， 其次，因?yàn)閐包含所有鉤子 ，并且t e h， 所以 l i a y r 。最后，由引理 知:im匡k + s 一 1 y 一= .im il + y - . i ( im il + l ) 一 9 + s -t 因此 19 ,u + t - i 定理4 . 4 樹t 的階為n = 2 ，則a m - 3 y , ( t ) / 2 - 1 證明: 若t = p 2 或k i ,n - i ，定理顯然成立。 現(xiàn)在假設(shè)t # p 2 , k i, . - i ; 分別設(shè) d和 x為 樹t 的包含所有鉤子且不含葉子的y ， 一 集合和y l 一 集合， m 是t 關(guān)于d的中介點(diǎn)集:記f = d - h = v : v e d但v 不是鉤子 ;設(shè)a是(xi 的一個(gè)最小控制集。 一:顯然x nl = 9 2 x nh = h;所以 y l = 川二 x n 閨u a 刀卜jx n 圳+ 陣n ( f u m)卜川+ jx n ( f u m) 二:下面只須考慮集合 x n ( f u m ) , 設(shè)! m )有 :個(gè)連通分支: m i l 麟. . . ., m , ， 在這些連通分支中 恰有 t 個(gè)連通 分支m i , m 2 , ， m , ( o l t s y 滿足m , 中的每個(gè)點(diǎn)在d 中都只有一個(gè)鄰點(diǎn)，而 其余的分支中至少包含一個(gè)中介點(diǎn)與刀 中兩個(gè)或兩個(gè)以上的點(diǎn)相鄰。 對(duì) 1 _ i _ t , 因?yàn)閙n l = (p , 所以每個(gè) m ;) 都是階不小于2 的樹， 因此至少有一個(gè)懸掛點(diǎn)設(shè) 為 x ; ， 則它在t中的度為2 . 設(shè)n ( x d n m ; = ( y ; , n (x d n d = ( w d , n (y d n d = ( v ) o 斷言1若m; c_ x ( 1 _ i 9) ，則w , v x或者v ; o x 。 碩士學(xué)位論文 ma s t e r s 7 7 j g s i s 證明:否則， 假設(shè)加。 v 少 c x; 首先設(shè)y ; o a ， 令x = x - (y d , a = a ; 顯然x 是t 的 控制集且y ( ! x 7 ) s y ( ( x 1 ) ; 這 與x是y : 一 集合矛 盾。 其次 若x ; o a ， 令x = x - (y ) , a = a ， 同 樣導(dǎo)出 矛 盾。 故必 有( x ;, y ;) _ a o 但這樣又可令x = x -( x ;) , a = (a -( x d ) u ( w ;) ， 這同 樣與x是y : 一 集合矛盾。 故必有w ; o x或者v , o x。 斷 言2 若有k 個(gè)中 介點(diǎn) 組滿足m ;( 1 _ i _ k ) 中 每個(gè)點(diǎn) 在d中 都只有一個(gè)鄰點(diǎn) ， 且均包含在x 中 ， 記凡 一 ( x i , y 1 ,x 2 ,y 2 , . . . . . .x k , y k ) ， 其中x ;, ” 如前 所設(shè); 則n ( r d nd中至少有 k 個(gè)不同的點(diǎn)不在x中。 證明: 對(duì)k 用數(shù)學(xué)歸納法。 k = 0 時(shí)濕然成立. 現(xiàn)在假設(shè)結(jié)論對(duì) k - 成立， 我們考慮n 刀 的k 個(gè)連通分支: m , , 噸 ，m k ; 收 縮各個(gè)分支為點(diǎn)m i, m 2 . . . . . . . m k . 并設(shè)n (x ) n d = ( w ) , n (y ) n d = ( v ;) e 構(gòu)造圖g . v ( g ) = v i u v 2 , v i = m i , m 2 , . . . . . .， m k , v 2 = w i , v i , i+ 2 , v 2 , ， w k .v k ) e ( g ) = ( m l w t , m i v i , m 2 w 2 , m 2 v 2 , . . . m k w k , m k v d . 顯然 是樹， 并且對(duì)所有的m , 有 d g ( 2 ) = 2. 因此 v 2 中 至少有一個(gè)懸掛點(diǎn). 不 妨 假設(shè)這個(gè)點(diǎn)屬于集合/ v k, w k ) ， 記此懸掛點(diǎn)為 t k ， 而( v k, w k 中另外一點(diǎn)為 t k a 考慮前k - 1 個(gè)分支 m , , m 2 . . . . . . m k _ i ，由歸納假設(shè)知n ( r k - d n d包含一個(gè) 由k - 1 個(gè)不在x 中的點(diǎn)組成的集合 q.根據(jù)斷言1 ， t k , t k 至少有一點(diǎn)不在 x 中 注意到 t k 0 q，如果d o ( t k ) = 1 ， 則wo q . 因此如果 t k o x或者t kex而 且d o ( tk ) = 1 ， 則集合 q u ( t d或 q u ( t k ) 106 是滿足要求的集合. 現(xiàn) 在 假 設(shè)d o (tk ) 刃w o x 而 且tk e x ， 則 tk 被 寫 如果 t k - v k ，t k ,- w k, 貝 x k 在( x ) 中的度為1 ， 因此點(diǎn) mi 中的一點(diǎn)所控制. x k 和 y k 不都在 勿的最 小控制集 a中。 如果 t k = w k a = a , ，t k 所以 ， 當(dāng)y k 0 a時(shí)， 令 x = x - ( y d , a = a: 當(dāng) x k o a時(shí)， 令 這都與x是t 的a一 集合的 假設(shè)相矛盾。 = v k ， 當(dāng)y k o a時(shí) ， 令 x = x -( y d , a = a當(dāng) x k o a時(shí)， 令 碩士學(xué)位論文 ma s t e r s t i i e s i s x = x - ( x ,) , a = a; 當(dāng)( x k ,y k) c_ a時(shí) ， 令x = x -( x d , a 一 (a -( x k) u ( v k); 這都與x 是t 的y : 一 集合的假設(shè)相矛盾。 因此斷言 2 成立。 現(xiàn)在把m i , m 2 , . . . . . m , 分成兩部分: 不妨假設(shè)m b m 2 , . . . . . m k 滿足m ; c x ( 1 i y c) ， 由斷言2 ， 對(duì)腸, m 2 , . . . . . 城 可以 假設(shè)有k 個(gè)d中不同的點(diǎn)不在x中， 設(shè)為 w l , w 2 , . . . . . . w k ;其余的滿足至少有一個(gè)點(diǎn)不在 x 中，不妨設(shè)這些點(diǎn)為 z k r l , z k f 2 . . . . . . . z i 那 么 x n ( f u m ) = x n ( f v ( u m i) -) ( i v l m i) v= 1 = k t汽 v i m i) )= t 9( f - - 1 , w 2 , . . . 二 w k ) ) u( m ( z k 十 ; z k + 2 , . . . . . z r! ) =( f u m) 一( w / , w 2 , . . . . . w k z k + l , z k 十 2 , . . . 習(xí) 所以ix n ( f u m ) is if i + imi- i 從引理3 我們知道:19 5 產(chǎn) 十 卜1 ， 所以ix n ( f u m ) is 1f i + , k 一 ， 那么y l 二 x i = ix n ( d u m ) i 二 ix n h i十 lx n ( f u m) i ih i + if i + ,u 一 =7 : + y一 1 既然d是一 個(gè)全控制集， 所以產(chǎn) 勻 刀 ; 因 此我們得到: y l 陰石3 y ,( t ) / 2 - 1 證畢。 而圖1 中的例子說明這個(gè)比值的上界是最好可能的. 碩士學(xué)位論文 ma s t e r s 7 l 1 e s i s 5小結(jié) 在 圖的全控制集與小控制集 的研 究 中，還有許 多未 知 的領(lǐng) 域. j . p f a f f , r . l a s k a r a n d s . t . h e d e t n i e m i 在1 9 8 3 年證明t 確定一個(gè)圖的全 控制數(shù)和小控制數(shù)是 n p 一 完備的. 本文給出了樹中小控制數(shù)與全控制數(shù)比值的 一個(gè)上界， 己知對(duì)于任意圖， 這個(gè)比值可以任意大， 如下圖4 : _ v . 1 磚 圖 4 注: 這個(gè)圖的y c 一 集合是 v 2 , v 3 , v 4 , v 6 . .y ,y a . . ， . ，刀， 所以y : 二 k + 4; 其y r 一 集合是 ! v 2 . v 3 . v 4 , v 5 , v 6 ,y d， 所以y t 6 . 令k 可任意大， 則此圖的小控制數(shù)與全控制數(shù)的比 值可任意大。 但我們可以討論對(duì)于其他特殊的圖類， 這個(gè)比值的界是怎樣的. 另 外， 本文只給出了 在樹中y c = y , 的一些充分條件， 當(dāng) 然想到去求一些必要條件， 目前尚無進(jìn)一步的結(jié)果. 碩士學(xué)位論文 ma s t e r s t i i e s i s 參考文獻(xiàn) 1 j .a .b o n d y a n d u s r .mu r ty , g r a p h t h e o r y w i t h a p p l i c a t i o n， ma c m i l l a n , n e w y o r k , 1 9 7 6 2 o d i l e f a v a r o n， l e a s t d o m i n a t i o n i n a g r a p h , d i s c r e t e ma t h 1 5 0 ( 1 9 9 6 ) 1 1 5 - 1 2 2 3 e .j . c o c k a y n e , r .m. d a w e s a n d s .t .h e d e t n i e m i , t o t a l d o m i n a t i o n i n g r a p h s， n e t w o r k s 1 0 ( 1 9 8 0 ) 2 1 1 - 2 1 9 4 e . s a m p a t h k u m a r , t h e l e a s t p o i n t c o v e r i n g a n d d o m i n a t i o n n u m b e r s o f a g r a p h， d i s c r e t ma t h 8 6 ( 1 9 9 0 ) 1 3 7 - 1 4 2 5 e .j . c o c k a y n e ,o .f a v a r o n , c . p a y a n a n d a . g .t h o m a s o n , c o n t r i b u t i o n s t o t h e t h e o r y o f d o m i n a t i o n , i n d e p e n d e n c e a n d i r r e d u n d a n c e i n g r a p h s ,d i s c r e t e m a t h . 3 3 ( 1 9 8 1 ) 2 4 9 - 2 5 8 6 r .b .a l l a n a n d r .l a s k a r ,o n d o m i n a t i o n a n d s o m e r e l a t e d t o p i c s i n g r a p h t h e o r y , p r o c . o f n i n t h s . e . c o n f e r e n c e o n c o m b i n a t o r i c s , g r a p h t h e o r y a n d c o m p u t i n g , u t i l i t a s ma t h .( 1 9 7 9 ) 4 3 - 5 6 7 j .p f a f , r .c . l a s k a r a n d s .t .h e d e t n ie m i ,n p - c o