（運(yùn)籌學(xué)與控制論專業(yè)論文）圖的弱羅馬控制.pdf

煎壹盔堂塑主堂垡迨塞 l 摘要 基于i a ns t e w a r t 1 l 】發(fā)表的一篇論文( d e f e n dt h er o m a ne m p i r e ! ，s c i e n t i f i ca m e r - i c a n ，d e c 1 9 9 9 ，p p 1 3 6 - 1 3 8 ) 的意圖，m a h e r m i n g 和s t h e d e t n i e m i 【l 】1 提出了防御羅 馬帝國的新策珞使最高統(tǒng)治者既節(jié)約了給養(yǎng)軍團(tuán)的基本花費(fèi)又能防御羅馬帝國用 圖論的術(shù)語，設(shè)g = ( v ，e ) 是個圖，：y 一 o ，1 ，2 ，是一個定義在圖g 的頂點(diǎn) 集y 上的函數(shù)對，來說一個，( “) = 0 的頂點(diǎn)u 被稱為未防御點(diǎn)，如果它不與任 何帶有正權(quán)的頂點(diǎn)相鄰函數(shù)，被稱為弱羅馬控制丞數(shù)( 簡稱w a d f ) ，如果對每一 個，( “) = 0 的頂點(diǎn)u ，都與一個( v ) 0 的頂點(diǎn)口相鄰，并且函數(shù)，：y 一 o ，1 ，2 h 使得，7 ( “) = 1 ，7 ( 。) = ，( 口) 一1 且，7 ) = ( w ) ，v 伽v 一 _ ) ，沒有未防御點(diǎn) 函數(shù)，的權(quán)記為叫( ，) = * y ，扣) 圖g 的弱羅馬控制函數(shù)的最小權(quán)稱為弱羅馬控 制數(shù)，記為* ( g ) ，在本文中，研究了圖的不同控制數(shù)的一些理論性質(zhì)，并且刻畫 了樹t 滿足竹口) = 7 ( r ) 的特征和圖g 滿足鏞( g ) = 1 ( g ) + 1 的特征，以及滿足 * ( g ) = 2 7 ( g ) 的圖g 的一些性質(zhì) 關(guān)鍵詞；控制數(shù)，樹，弱羅馬控制數(shù) 河宣大學(xué)碩士學(xué)位論文 a b s t r a c t m o t i v a t e db ya l la r t l e l eb yi a ns t e w a r t 【1 1 j ( d e f e n dt h er o m a ne m p i r e ! ，s c i e l l t i f i c a m e r i c a n ，d e e 1 9 9 9 ，p p 1 3 6 - 1 3 8 ) ，m a i - i e n n i n ga n ds t t t e d e t n i e m i1 1 】1e x p l o r ean e w s t r a t e g yo fd e f e n d i n gt h er o m a ne m p i r et h a th a st h ep o t e n t i a lo fs a v i n gt h ee m p e r o r c o n s t a n t i n et h eg r e a ts u b s t a n t i a lc o s t so fm a i n t a i n i n gl e g i o n s ，w h i l es t i l ld e f e n d i n gt h e r o m a ne m p i r e i ng r a p ht h e o r e t i ct e r m i n o l o g y ，l e tg = ( k e ) b eag r a p ha n dl e t ， b ef u n c t i o n ，：vh 0 ，1 ，2 ) av e r t e x w i t h ，0 ) = 0i ss a i dt ob eu n d e f e n d e dw i t h r e s p e c tt o ，i fi t | 埠n o ta d j a c e n tt oav e r t e xw i t hp o s i t i v ew e i g h t t h ef u n c t i o n ，i sa w e a kr o m a nd o m i n a t i n gf u n c t i o n ( w t l i ? f ) i fe a c hv e r t e x “w i t h ，( ) = 0i sa d j a c e n tt o a v e r t e x 寸w i t h ，p ) 08 u c h t h a t t h e f u n c t i o n ：v h ( o ，1 ，2 ，d e f i n e db y ，7 ( = i ， ，( 口) = f ( v ) 一1a n d ，( ) = ( w ) i f v t ) ，h a sn ou n d e f e n d e dv e r t e x t h e w e i g h to f ，i 8 ( ，) = * v ，( u ) t h ew e a kr o m a nd o m i n a t i o nn u m b e r ，d e n o t e d * ( g ) ， i st h em i n i m u m w e i g h to faw r d f i ng i nt h i sp a p e r is t u d yt h eg r a p ht h e o r e t i cp r o p - e r t i e so ft h l sv a r i a n to ft h ed o m i n a t i o nn u m b e ro fag r a p h a n dic h a r a c t e r i z et r e e stf o r w h i c h 竹( q = ，y ( ? ) a n dg r a p h s g ?！眞 h i c h 竹( g ) = 一r ( q + 1 ，a n d ig i v e t h eg r a p h g s o m ep r o p e r t i e sw i t h 竹( g ) = 2 1 ( g ) k e y w o r d s ：d o m i n a t i o nn u m b e r ，t r e e s ，w e a kr o m a nd o m i n a t i o nn u m b e r 關(guān)于學(xué)位論文獨(dú)立完成和內(nèi)容創(chuàng)新的聲明 本人向河南大學(xué)提出碩士學(xué)住串請。本人鄭重聲明：所呈交的學(xué)柱論又是 表人在導(dǎo)師的指導(dǎo)下獨(dú)立完成的，對所研究的課題有新的見解。據(jù)我所知，除 文中特刷加科說明、標(biāo)注和致謝的地方外，論文中不包括其他人已經(jīng)發(fā)表或撰 寫過的研究成果也不包括其他人為獲得任何教育、科研機(jī)構(gòu)的學(xué)位或證書而 使用過酌材料。與我一同工作酌同事對本研究所儆酌任何貢獻(xiàn)均已在論衛(wèi)中作 了明確的說明并表示了謝毒。 學(xué)位中請八( 學(xué)位論作者) 鍪名： 煮茲劊 2 0 叼年歲月幻。 關(guān)于學(xué)位論文著作權(quán)使甩授權(quán)書 本人經(jīng)河南太嚳審核批準(zhǔn)授予碩士學(xué)位。作為學(xué)位論夏酌作者本人完全 了解并同意河南大學(xué)有關(guān)保留、使用學(xué)位論文的要求，即河南大學(xué)有權(quán)南國家 圖書館、科研信息機(jī)構(gòu)、數(shù)據(jù)收集機(jī)構(gòu)和本校圖書館等提供學(xué)位論文( 紙質(zhì)文 本和屯子咒本) 雌供公眾檢索、查閱。本人授權(quán)河南大學(xué)出于宣揚(yáng)、展覽學(xué)校 學(xué)術(shù)點(diǎn)展和進(jìn)行學(xué)拳交流等目的，可以采取幫即、縮印、掃描和拷貝等復(fù)制手 段保存、匯編學(xué)位論文( 紙質(zhì)文本和電子立本) 。 ( 涉度保密內(nèi)容的學(xué)位論文在解密后適用本授權(quán)書) 擘位獲得者( 學(xué)住論z 作者) 器名 壅之壘j 。o 0 7 年?duì)I月弘。 學(xué)住論文指導(dǎo)教師簽名寶窒墅 翌童盔蘭夔圭堂垡堡塞 l 第一章引言 e j c o c k a y n e 等在 3 】中給出了在一個圖g = e ) 上的羅馬控制函數(shù)( 簡 稱r d f ) 的定義：定義在礦上的一個函數(shù)f ：y 一 o ，1 ，2 ) 稱為圖g = ( v , e ) 的一個羅馬控制函數(shù)如果它滿足：每一個使f ( u ) = 0 的頂點(diǎn)u 至少連接一個頂點(diǎn) _ 使，( 口) = 2 實(shí)值函數(shù)f ：v r 的權(quán)記為( ，) = * y fc v ) ，并且我們定義 f ( s ) ；e 。s ，0 ) ，vs v ，因此”( ，) = ，( y ) 圖g 的羅馬控制函數(shù)的最小權(quán)稱為羅 馬控制數(shù)，記為1 r c a ) ，也即7 r ( a ) = r a i n w ( f ) f 是g 的一個r d f 一個權(quán)為他( g ) 的r d f 我們叫做個他( g 卜一函數(shù)圖的羅馬控制的一些理論性質(zhì)在 3 ，4 ，6 ，1 0 j 中 已經(jīng)被研究過 定義羅馬控制函數(shù)的意圖來源于i a ns t e w a r t 1 1 1 在美國科學(xué)雜志上發(fā)表的一 篇題為“防御羅馬帝國! ”的文章在我們所研究的圖中的每一頂點(diǎn)代表羅馬帝國 的一個地區(qū)一個地區(qū)( 頂點(diǎn)”) 被認(rèn)為是不安全的，如果沒有軍團(tuán)駐扎在那里( 即 ，如) = o ) ，否則被認(rèn)為是安全的( 即，( u ) e 1 ，2 ) ) 一個不安全的地區(qū)( 頂點(diǎn) ) 能夠 被安全防御如果能夠從相鄰的地區(qū)0 的一個鄰點(diǎn)u ) 派個軍團(tuán)到達(dá)該地區(qū)但是 在公元四世紀(jì)最高統(tǒng)治者頒布法令：個軍團(tuán)不能從一個安全地區(qū)派遣到一個不安 全的地區(qū)如果派遣后使得該地區(qū)不安全因此，在派出其中一個軍團(tuán)到相鄰地區(qū)之 前必須在該地區(qū)駐扎兩個軍團(tuán)( ，( ”) = 2 ) 最高統(tǒng)治者利用這種方式能夠防御羅馬 帝國因?yàn)樵趥€地區(qū)給養(yǎng)個軍團(tuán)是很昂貴的，所以統(tǒng)治者想用盡可能少的軍團(tuán) 防御羅馬帝國一個權(quán)為他( g ) 的羅馬控制函數(shù)對應(yīng)著個最優(yōu)分派軍團(tuán)駐扎的方 案 為探究節(jié)約統(tǒng)治者基本的給養(yǎng)軍團(tuán)的花費(fèi)，同時仍然能夠防御羅馬帝國的潛 力，m a h e n n i n g 【1 】1 等提出了新的策略令g = ( v , e ) 是個圖，是個函數(shù) ，：v 一 o ，l ，2 ) 設(shè)，m ，塢分別代表在，作用下取值分別為0 , 1 ，2 的頂點(diǎn)集注 意到在函數(shù)，：y 一 o ，1 ，2 ) 和頂點(diǎn)。的劃分( ，u ，) 之間存在一一對應(yīng)關(guān)系 因此我們記，= ( v o ，h ，) 在，對應(yīng)下個頂點(diǎn) v o 是未被防御點(diǎn)，如果它不與或中的頂點(diǎn)相 鄰m a n e n n i n g 1 】等提出了弱羅馬控制函數(shù)( 簡稱w r d f ) 的概念：稱函數(shù)， 2 塑墮盔堂塑主堂垡堡塞 是一個w r d f ，如果對于每一個頂點(diǎn)，都鄰接一個頂點(diǎn)”n u ，使得函數(shù) ，：v 一 o ，1 ，2 ) 沒有未防御點(diǎn)，其中，7 ) = 1 ，銣) = ，( 口) 一1 并且，( ) = ，( t j ) ， v v 一 ，u 我們定義，的權(quán)”( ，) 為i 碓f + 2 f f ，圖g 的一個w r d f 的最小權(quán)稱為弱羅馬 控制數(shù)，記為竹( g ) ，即竹( g ) = m i n w ( f ) l f 是圖g 的一個w r d f ) , 一個權(quán)為* ( g ) 的w r d f 稱為竹( g ) 一函數(shù)為了方便，對y 的每一頂點(diǎn)”，我們記f ( n v 1 ) = ， 給出w r d f 定義的意圖是基于下面的考慮仍然采用先前的記號，我們定義 一個地區(qū)是未防御的，如果這個地區(qū)與與之相鄰的地區(qū)都是不安全的( 即沒有軍團(tuán) 駐扎在那里) 因?yàn)閭€未防御地區(qū)是易受攻擊的，所以我們要求每一個不安全地 區(qū)必須與個安全地區(qū)相鄰，并且使得從這個安全地區(qū)派遣軍團(tuán)到不安全地區(qū)不會 產(chǎn)生未防御地區(qū)因此每一個不安全地區(qū)能夠被防御而不會產(chǎn)生未防御地區(qū)利用 這種方式最高統(tǒng)治者仍然能夠防御羅馬帝國而這一種分派軍團(tuán)的方案對應(yīng)著個 w r d f 且軍團(tuán)數(shù)目的最小值對應(yīng)著w r d f 的最小權(quán)因?yàn)檫@種方案既能節(jié)約統(tǒng)治 者給養(yǎng)軍團(tuán)的花費(fèi)又能防御羅馬帝國，所以弱羅馬控制引起了統(tǒng)治者的高度重視 注意到在w r d f 中每一個在中的點(diǎn)都被h u 砼中的某一點(diǎn)所控制，而在 r d f 中的每一在k 中的點(diǎn)至少被中的一點(diǎn)所控制( 這個顯得很昂貴) 再者，在 w r d f 中每一個在中的點(diǎn)都能夠被防御而不會產(chǎn)生新的未防御點(diǎn)。因此，研究 圖的弱羅馬控制更具有現(xiàn)實(shí)意義 本文主要圍繞圖的弱羅馬控制展開討論，研究了圖的不同控制數(shù)之間的一些理 論陛質(zhì)在本文的前半部分，主要給出了弱羅馬控制數(shù)的一些特殊值以及它的上下 界；在文章的后半部分，主要刻畫了樹t 滿足竹( t ) = 7 ( t ) 的特征和圖g 滿足 * ( g ) = 7 ( 回+ 1 的特征，以及滿足竹( g ) = 2 ，y ( g ) 的圖g 的一些性質(zhì)。 塑宣盔堂塑主堂焦堡塞 3 第二章記號 我們一般采用文獻(xiàn) 8 1 中的圖論術(shù)語和記號特別地，讓g = ( v , e ) 是一個 頂點(diǎn)集為礦，邊集為e 且階數(shù)為n 的圖，。是y 的任意個頂點(diǎn)，頂點(diǎn)”的度記為 d ( 頂點(diǎn)u 的開鄰域記為( 。) = 。v l u v e 且閉鄰域記為m = 。 u ( 。) 對個集合s v ，它的開鄰域記為( 研= u 。e s n ( v ) - s 且它的閉鄰域記為舊= s u n ( s ) 個頂點(diǎn)u 被稱為”關(guān)于s 的私有鄰點(diǎn)，或簡單的說是”的個s 一肌，如 果 叫n s = u 頂點(diǎn)”的所有s 一的集合肼( 釓s = m n s - 口h 被稱為 口關(guān)于s 的私有鄰集我們定義 關(guān)于f 的外私有鄰集為e 即( 口，s ) = m ( ”，s ) 一 w ) 因此集合e p a ( v ，s ) v s 集合s 被稱為是不多余的如果m ( 口，回0 ，vu s 設(shè)g = f ) 是一個圖，s v 我們說集合s 控制集合u ，記著s 卜u ，如 果u s 中的每一個頂點(diǎn)至少鄰接f 中的一頂點(diǎn)如果s - v s 或者等價地， = y ，則s 被叫做g 的一個控制集圈g 的最小控制集的基數(shù)稱為最小控制 數(shù)，記著7 ( g ) 一個基數(shù)為7 ( g ) 的控制集稱為，y ( g ) 一集我們注意到每個最小 控制集是一個最大不多余集，但反之不一定成立例如，長度為5 的圈島的每兩 個相鄰的頂點(diǎn)構(gòu)成一個最大不多余集，但它卻不是控制集圖的控制集吲以及它 的變化形式目前已經(jīng)有了很好的研究特別地，t w h a y n e s 8 ，9 】等給出了有關(guān)這一 主題的深入調(diào)查和研究 我們稱圖g 是羅馬圖，如果忱( g ) = 研( g ) 個頂點(diǎn)集合占被稱為獨(dú)立的，如果s 中的任意兩個頂點(diǎn)均不相鄰圖g 的 獨(dú)立控制集( 或者等價地，圖g 的最大獨(dú)立集) 的最小基數(shù)稱為獨(dú)立控制數(shù)，記著 t ( g ) 一個頂點(diǎn)集合s 被稱為2 分離的，如果m n m = 死v u ，u s 圖g 的 最大2 一分離集的基數(shù)稱為2 一分離數(shù)，記著耽( g ) 個頂點(diǎn)集合s 被稱為點(diǎn)覆蓋集，如果v w e ，要么t s 要么 s 為了易于表達(dá)，我們?？紤]帶有根源的樹對于( 有根源的) 樹t 中任意一頂點(diǎn)弘 我們用c ( v ) 和d ( v ) 分別代表。的孩子和后代的集合，并且定義口m = d 扣) u ” 4 塑壹盔堂堡主堂焦絲塞 在頂點(diǎn) 處的極大子樹是由d m 導(dǎo)出的子樹，記著馬一個度為1 的頂點(diǎn)稱為樹 t 的一個葉子( 又稱為懸掛點(diǎn)) ，同時與葉子相鄰的頂點(diǎn)稱為樹t 的支撐點(diǎn)，與至 少兩片葉子相鄰的頂點(diǎn)稱為強(qiáng)支撐點(diǎn)在本文中。我們記所有支撐點(diǎn)集合為s ( ? ) ， 所有強(qiáng)支撐點(diǎn)的集合為8 s ( t ) ，所有盱子集合為工( t ) 對于任給的正整數(shù)t ，完全二部圖甄t 稱為星，并且稱度為t ( t 2 ) 的頂點(diǎn)為中 心點(diǎn)，度為1 的頂點(diǎn)為外點(diǎn)，而情形p 2 中，我們稱兩個頂點(diǎn)都為中心點(diǎn)一個病 態(tài)的蜘蛛樹是指一個星致 至多剖分它的t 一1 條邊類似地，對于任給整數(shù)t22 ， 一個健康的蜘蛛樹是指一個星確。剖分它的所有邊在一個病態(tài)的蜘蛛樹中，一個 度為t 的頂點(diǎn)將被稱為頭點(diǎn)，并且與頭點(diǎn)的距離為2 的頂點(diǎn)稱為腳點(diǎn)頭點(diǎn)和腳點(diǎn) 是確定的除非當(dāng)病態(tài)的蜘蛛樹是兩個或四個頂點(diǎn)的路對于p 2 ，我們將規(guī)定兩個頊 點(diǎn)都為頭點(diǎn)，而情形p 4 中，我們將規(guī)定兩端的頂點(diǎn)都為腳點(diǎn)，并且兩個中間點(diǎn)都 為頭點(diǎn)， 在本文中，所考慮的圖均為有限的非平凡簡單圖 翌塑盔竺塑望垡絲塞 5 第三章相關(guān)的已知結(jié)果 關(guān)于圖的羅馬控制和弱羅馬控制已經(jīng)有了很多的結(jié)論，本章主要是把與本文 有關(guān)的結(jié)論列出來，以便后面使麒其中第一節(jié)主要介紹有關(guān)圖的羅馬控制的一些 結(jié)果，第二節(jié)主要介紹有關(guān)圖的弱羅馬控制的一些結(jié)果 3 1 圖的羅馬控制 有關(guān)圖的羅馬控制的一些已知結(jié)果 命題3 1 1 3 對任何階數(shù)為”的圖g ，y ( g ) = 他( g ) 當(dāng)且僅當(dāng)g = ，不 命題3 2 1 3 設(shè)= ( ，玨) 是任何他一函數(shù)，則 ( a ) 由導(dǎo)出的子圖c v 1 的最大度為l ； ( b m 和班之間沒有邊相連； ( c ) v o 中的每一個頂點(diǎn)至多與h 中的兩個頂點(diǎn)相鄰； ( d ) v 2 是g v o u 】的一個卜集； ( e ) 設(shè)h = g v o u 吲，則的每個頂點(diǎn)。至少有兩個一肌( 即圖日中 關(guān)于k 的私有鄰點(diǎn)) ； ( f ) 如果”是g f b 】的孤立點(diǎn)并且僅有一個外日一冊，記為”，則 ) n h = 毗 ( g ) 設(shè)k 為g 【吲中非孤立點(diǎn)數(shù)且，令d = ( v o h n ( v ) n 屹i 芝2 ) 且i c i = c 貝0n o 砌+ k + c 命題3 3 3 l 設(shè)= ( ，h ，v 2 ) 是無孤立點(diǎn)圖g 的個佃一函數(shù)，使得n 1 最小 則； ( a ) 是獨(dú)立集且k u 耽是個覆蓋； ( b ) ； ( c ) k 中的每一個頂點(diǎn)至多鄰接u 中的個頂點(diǎn)，即k 是一個2 一分離 6 塑宣盔堂堡主堂垡絲塞 集； ( d ) 設(shè) g 吲恰有兩個外一p n ，記為 1 ，坳v o ，則不存在點(diǎn)y l ，拋 使得， 1 ， ，地，y 2 ) 是一條路p 5 的頂點(diǎn)序列； e ) n e 3 n 7 ，并且這個界是緊的 命題3 4 3 】對任何階數(shù)為n 且最大度為的圖g ， 晶郇) 命題3 5 3 1 對任何階數(shù)為n 的圖g ， 榔脅等籌 注意1 ：此處可能由于作者的疏忽出現(xiàn)丁一些計(jì)算性錯誤，從而結(jié)論有誤，在后 面應(yīng)用時給予指出并修正 命題3 6 1 3 1 7 r ( p 。) ：垤( 島) ：f 娑 命題3 7 1 3 設(shè)g = k m ，。，。是完全p 一部劃分圖，并且使得 i 7 1 m , 2 ；則： ( a ) 如果m l 3 ，則7 a ( a ) = 4 ； ( b ) 如果m l = 2 ，則7 r ( a ) = 3 ； ( c ) 如果m l = 1 ，則7 r ( g ) = 2 ； 命題3 s 1 3 如果g 是個階數(shù)為n 且包含一個n 一1 度的頂點(diǎn)的圖，則7 ( g ) = 1 且7 r ( g ) = 2 命題3 9 ( 3 】對任何2 n 格圖g 2 m7 r ( g 2 ，。) = n + 1 命題3 1 0 1 3 】如果g 是階數(shù)為n 的無孤立點(diǎn)的圖，則7 r ( g ) = n 當(dāng)且僅當(dāng)n 是 偶數(shù)且g = ；鮑，其中；尬代表；個鮑的拷貝 命題3 1 1 1 3 如果g 是個階數(shù)為n 的連通圖，則7 a ( a ) = 7 ( g ) + 1 當(dāng)且僅當(dāng) 存在口v 使得d ( v ) = n 一7 ( g ) 命題3 1 2 f 3 j 如果t 是一個非平凡樹，則他口) = 7 + 1 當(dāng)且僅當(dāng)t 是一個病 態(tài)的蜘蛛樹 命題3 1 3 1 3 g 是一個階數(shù)為n 的連通圖，則他( g ) = 1 ( g ) + 2 當(dāng)且僅當(dāng)： ( a ) a 不含度為n 一7 ( g ) 的頂點(diǎn)； 塑查盔堂塑主堂垡堡塞 7 ( b ) g 有個度為n 一，y ( g ) 一1 的頂點(diǎn)或者有兩個頂點(diǎn)v 和t c l 使得l n v l u n w l l = n 一7 ( g 1 + 2 命題3 1 4 1 3 】圖g 是羅馬圖當(dāng)且僅當(dāng)它有一個垤一函數(shù)，= ( ，h ，) 使得 ”1 = i i = 0 命題3 1 5 1 3 】圖g 是羅馬圖當(dāng)且僅當(dāng)7 ( g ) 7 ( g s ) + i i s i ，對每一個扯分離 集s v 命題3 1 6 1 4 如果g 是個階數(shù)為n 的連通圖，則 y r i ( g ) = ，y ( g ) + 當(dāng)且僅當(dāng)： ( a ) v1 j 一1 ，g 不含一個階數(shù)為j 的子集s y 使得l 舊l 竹一( 7 ( g ) + i ) + 勿：j i 七一1 ( b ) a 含有一個子集島v 使1 i s o i 且i n s o i = n n ( g ) + ) + 2 f 島| 3 2 圖的弱羅馬控制 有關(guān)圖的弱羅馬控制的一些已知結(jié)果 命題3 1 7 1 1 1 圖g 的任何個r d f 也是一個w r d f 命題3 1 8 1 1 】對任何圖g ，7 ( g ) * ( g ) 他( g ) 2 7 ( g ， 命題3 1 9 1 v 口21 ，竹嘛) = 孥1 ；v n 24 ，* ( r ) ：* ( 島) ；娑1 命題3 2 0 1 】對任何圖g ，7 ( g ) ；竹( g ) 當(dāng)且僅當(dāng)存在一個，y ( g ) 一集s 使得： ( 1 ) v 口只弘0 ，s ) 導(dǎo)出一個團(tuán)； ( 2 ) vt v ( g ) 一s 不是任何s 的私有鄰點(diǎn)，存在一個點(diǎn)口s 使得 冊( 口，印u ”，導(dǎo)出一個團(tuán) 命題3 2 1 1 1 】如果圖g 滿足* ( g ) = 2 7 ( g ) ，則對每一個1 ( g ) 一集s 和每一個 口s ，外私有鄰集q m ( ，s ) 包含兩個不相鄰的點(diǎn) 8 煎宣盔堂堡主堂焦堡塞 第四章主要結(jié)果與證明 這一章是得到的主要結(jié)果以及結(jié)論的證明其中第一節(jié)給出弱羅馬控制數(shù)的 一些特殊值，第二節(jié)給出圖的弱羅馬控制的一些性質(zhì)以及弱羅馬控制數(shù)的上下界， 第三節(jié)刻畫滿足* ( = 7 ( 的樹t 的特征，第四節(jié)刻畫圖g 滿足* ( g ) = 7 ( g ) + 1 的特征，第五節(jié)給出了圖g 滿足* ( g 9 = 2 7 ( g ) 的些性質(zhì) 4 1 弱羅馬控制數(shù)的一些特殊值 e j c o c k a ：y n e 3 等給出了一些羅馬控制數(shù)的特殊值，例如命題3 , 6 1 3 ，命題3 7 1 3 ： 命題3 8 f 3 j ，命題3 9 1 3 ，命題3 , z o 3 而m a h e n n i n g 1 等也已經(jīng)給出了路和圈的弱 羅馬控制數(shù)，例如命題3 1 9 1 1 作為補(bǔ)充我們再給出弱羅馬控制數(shù)的一些特殊值 命題1 如果圖g = 似聊的階數(shù)為n 且包含一個度為n 一1 的頂點(diǎn)，則1 ( g ) = 1 并 且如果g = ，則竹( g ) = ，y ( g ) = 1 ；否則，* ( g ) = 他( g ) = 2 證明；設(shè)d 扣) = n 一1 ，則顯然 。) 是一個控制集，即1 ( g ) = f ) i = 1 如果g = j h ，則v ”v ( g ) ，= 一t ”) ， 口h 毋) 是g 的一個弱羅馬控制函 數(shù)( 因?yàn)槿谓o”丘= ( v 一 u ) ， “) ，o ) 沒有未防御點(diǎn)) 所以7 ( g ) * ( g ) ( ，) = i 口) f = 1 = 7 ( g ) ，即* ( g = 7 ( g ) = i 如果g j 矗，則必存在點(diǎn)z ，y 使得礎(chǔ)e 且n 3 ，顯然由命題3 1 8 l l 和命題3 s 3 1 有竹( g ) 協(xié)( g ) = 2 假如，= ( ，耽) 是一個竹( g ) 一函數(shù)且1 r ( g ) = 1 ，則設(shè)= o ，k = “) ， = v 一 u ) 顯然u 。，g ( 否則y 或z 將為未防御點(diǎn)，矛盾) ，所以，( z ) = ，( ) = 0 ， 但是厶= ( v 一 。 ， z ，o ) 有一個未防御點(diǎn)們矛盾 故竹( g ) 2 因此* ( g ) = 仰( g ) = 2 口 塑宣盍堂塑主堂垡絲塞 9 命題2 設(shè)g = k m ，t ，1 2 。是完全n 一部劃分圖并且m ls 砌 h ( a ) 如果m 124 且n = 2 ，則竹( g ) = 4 ； ( b ) 如果”l24 且n 3 或m 1 = 3 ，則( g ) = 3 ； ( c ) 如果m l = 2 ，則* ( g ) = 2 ； ( d ) 如果“1 = 1 ，則 們) ： 1 ，如果g = i2 ，否則 證明；( a ) 如果m l 4 且n = 2 ，則g = k m ，m 為完全二部圖記( x ，y ) 為i f , 的頂點(diǎn)劃分，使得v = x u y ，x n y = 織i x l = m 1 ，l y l = m 2 下證，銣( g ) 4 假設(shè)* ( g ) 4 ，即* ( g ) 3 ，則存在一個弱羅馬控制函數(shù)，= ( ，砼) 使得 ”( ，) = i h i + 2 i 班l(xiāng) = 3 因此有下面兩種情形之一成立： 情形( 1 ) ：i i = 3 ，i k l = o ；情形( 2 ) ：i m i = 1 ，i l = 1 情形( 1 ) ：若h i = 3 ，i i - 0 。則分下面四種情況討論：( 1 1 ) h = z 1 ，z 2 ，。3k ( 1 2 ) = 。l ，$ 2 ，舭，；( 1 3 ) m = ( z 1 ，饑，拋，；( 1 4 ) k = y l ，軌，拈) ，其中戤x ，譏 ei = 1 ，2 ，3 若= $ 1 ，卻，知) ，1 k l = 0 由于i x l = m 1 4 ，則至少存在一頂點(diǎn)z 4 x 使 ，( 。4 ) = 0 顯然釓點(diǎn)為未防御點(diǎn)，與假設(shè)矛盾 故( 1 1 ) 不成立同理，( 1 4 ) 也不成立 若u = 。1 ，現(xiàn)，姐) ，i i = 0 由于 x = m 1 4 ，則至少存在兩個頂點(diǎn)$ 3 ，瓤 x 使，( z 3 ) = ，( z 4 ) = 0 即。3 ，z 4 而鋤，瓤只與h u 中的點(diǎn)譏相鄰，令 厶；m u i ， z 3 ) ，u 。3 ) 1 ) ，班) ，而z 4 為未防御點(diǎn)，與假設(shè)矛盾 故( 1 2 ) 不成立同理：( 1 3 ) 也不成立 因此( 1 ) i h l = 3 ，i 班i = 0 不成立 情形( 2 ) 若i h i = 1 ，i l = 1 ，則分下面四種情況討論：( 2 1 ) = z l k = 。2 ) ； ( 2 2 ) h = z 1 ) ，= 1 ) ；( 2 3 ) = 譏， = 2 1 ) ；( 2 1 ) h = 譏 ，= 拋) ；其 中氟x ，璣y i = 1 ，2 1 0 河南大學(xué)碩士學(xué)盟論文 若h = z 1 ) ，k = z 2 k 由于陋l = m 1 4 ，則至少存在兩個頂點(diǎn)$ 3 ，9 4 x 使f ( x 3 ) = ，( 。4 ) = 0 顯然z 3 ，$ 4 為未防御點(diǎn)，與假設(shè)矛盾 故( 2 1 ) 不成立同理；( 2 4 ) 也不成立 若u = 譏 ，耽= 研) ，由于i x i = m 1 4 ，則至少存在三個頂點(diǎn)z 2 ，z 3 ，x 4 x 使，渤) = ，渤) = ，洶) = 0 而2 ，翔，2 7 4 只與u 硯= ( z i ，y 1 ) 中的點(diǎn)饑相鄰 令厶= m u y 1 ) $ 2 ) ，u x 2 ) ( 1 ) ，) ，而為未防御點(diǎn)，與假設(shè)矛盾 故( 2 3 ) 不成立同理：( 2 , 2 ) 也不成立 綜合情形( 1 ) ( 2 ) 可知* ( g ) 芝4 設(shè)z 1 五口1 y ，則顯然，= ( v 一 l ，1 ) ，o ， 2 l ，y 1 ) ) 是圖g 的一個r d f 且 權(quán)f ( v ) = ( ，) = 2 i 。1 ，y 1 ) i = 4 又由命題3 1 7 1 】可知，也是g 的個w r d f ，故 ，是圖g 的一個竹( g ) 函數(shù)且* ( g ) = 4 ( b ) 設(shè)( 溉，弱，) 是g 的頂點(diǎn)劃分，使得v = x 1 u 恐u u ，i 蜀i = 訛，x i n = 兒其中i j ，i ，j = 1 ，2 ，m 著m 1 = 3 ，則竹( g ) 23 假設(shè)* ( g ) 3 ，即竹( g ) 2 ，則存在一個弱羅馬控制函數(shù)，= m ，k ，u ) 使得 ”( ，) = i h l + 2 f f = 2 因此有下面兩種情形之一成立： 情形( 1 ) ：1 1 = 2 ，1 1 = o ；情形( 2 ) ：l 1 = 0 ，1 y 2 1 = 1 ， 情形( 1 ) ：若f k l = 2 ， 班f = 0 ，貝4 分下面兩種情況討論；( i 1 ) k = 甄【，鋤 ，其中 。n ，t 2 蜀，忙1 ，2 ，仃( 1 2 ) = z n ，x j l ) ，其中茹 l 墨，即1 瑪，t j ，i ，j = 1 ，2 ，n 若( 1 1 ) 成立，由于阢l = 訛m 1 = 3 ，i = 1 ，2 ，n 則至少存在一頂點(diǎn) z 3 置使，( 。謅) = 0 顯然z i 3 為未防御點(diǎn)，與假設(shè)矛盾 若( 1 2 ) 成立，由于阢l = 佻m 1 = 3 ，i = 1 ，2 ，n 則至少存在兩個頂點(diǎn) $ 口，z 置使，( 。拯) = y ( = i 3 ) = 0 而z 拯，$ 侶只與u = ( $ m 巧1 ) 中的點(diǎn)l 相鄰令厶= ( 叭巧1 ) 。但 ，u 1 1 ：i 2 ) l ，) ，而為未防御點(diǎn)，與假設(shè) 矛盾 情形( 2 ) ：若i h i = 0 ，i l = 1 ，則設(shè)他= 。；1 ) ，其中。n 噩，i = 1 ，2 ，n 由于隴f = m f 鉚= 3 ，i = 1 ，2 ，n 則至少存在兩個頂點(diǎn)。誼，z i 3 咒使 塑宣盔堂塑主堂絲堡塞 1 1 ，扛程) = ， 得) = 0 顯然鋤，翰為未防御點(diǎn)，與假設(shè)矛盾 綜合情形( 1 ) ( 2 ) 可知* ( g ) 3 又，= ( v 一，0 ) ( 其中= z l l ，z 1 2 ，z 1 3 ) 是g 的一個w r d f 且( ，) = 陬l = 3 ( 事實(shí)上，v 。詣v u ， = 2 ，n ，1 k ，f ( x 諏) = 0 且訊與z t l 相 鄰，令厶= 一h $ 玨) z 1 1 ) ，m u x i k ) z n ) ，口) ，沒有未i 勞御點(diǎn)) 故，是一個竹( g ) 一函數(shù)且* ( g ) = ( ，) = i n i = 3 若m l 4 且n 3 ，則竹( g ) 3 假設(shè)* ( g ) ( ，) ，矛盾我們 有f ( z i o i ) = ，( 一1 ) = o 如果，( “) = l ，黜有盎”，x 和牽( 丘”。) 毋( ，) ，矛 盾我們有，扛o + 1 ) = ，( + 1 ) = 0 ( 3 1 ) 當(dāng)如；2 或者，( 一2 ) = ，( 一2 ) = 0 時，我們必須從?；? ) 調(diào)動個軍 團(tuán)來保衛(wèi)：r o - 1 ( 一i ) ，而且不能使2 o + 1 ( + 1 ) 成為未防御點(diǎn)因而我們有，( + 2 ) = ，( + 2 ) = 1 這樣一來，我們定義 1 x 使得 1 4 塑墮盍堂塑主堂焦迨塞 h i ( ) = 1 ，= 礬。一1 ，z i o + 3 0 ， = y i o ，x i o + 2 ； ，0 ) ， 其它， 則曲( h 1 ( ，) ，矛盾 ( 3 2 ) 因此我們有i o 3 和，( 2 如一2 ) 十，( 一2 ) 2 1 ，如果，( 一2 ) = ，( 一2 ) = 1 ， 我們定義h 2 x 使得 h 2 ( v ) = 則( 2 ) 妒( ，) ，矛盾 ，( + 2 ) = 1 ( 3 3 ) 不妨設(shè)班n 鋤，識 h 3 x 使得 h s ( v ) = 1 ， 2 肌。一3 ，z o + 1 ； 0 ， 2 蚍。一2 ，$ 如； ，( u ) ，其它 因而我們有，( z 。一2 ) + ，( 一2 ) = 1 同理，0 + 2 ) + i o 一2 s 口+ 2 ) = x l o - 2 ，+ 2 ) ，我們定義 1 ， 口= 們。一1 ，x i o + l 0 ， 口= o i o ，y i o ； ，扣) ， 其它 則( h 3 ) ( 門，矛盾因此任給1 蘭i n 一3 ，我們有，( z ) + ( w ) 曼1 ( 4 ) 若，( z 1 ) = ，( 譏) = 0 ，則有，( z 2 ) = f ( y 2 ) = 1 ，矛盾因此不妨設(shè)，p i ) = 0 ，( w ) = 1 我們有f ( x 2 ) 十，) = 1 假設(shè)f ( x 2 ) = 0 ，劬) = l ，如果，( 3 ) = ，( 拋) = 0 ，則有，( 。4 ) = f ( y 4 ) = 1 ，矛 盾因此我們有，( z 3 ) + ，) = 1 。我們定義k x 使得 地( ”) = 則陬) ( ，) ，矛盾 i1 ，口= x 2 ，y 4 ； 0 ， 2y 2 ，z 3 ，船，0 4 ； l l ，o ) ， 其它 因此我們有，( z 2 ) = 1 ，f ( v 2 ) = 0 ，lli，、ii、 迥直態(tài)堂塑主蘭垡迨塞 1 5 ( 5 ) 若( x s ) + ，) = 1 ，我們定義h s x 使得 f ， 一馳； h s ( v ) = 0 ，口= 奶，y 3 ； i ，( 。 其它， 則廬慨) ( ，) ，矛盾因此，( z 3 ) = ( y s ) = 0 ( 6 ) 顯然f ( y 4 ) = 1 ( 否則始為未防御點(diǎn)) 那么f ( x 4 ) = 0 若f ( x 5 ) = 0 ，則我們只 能從馭調(diào)動軍團(tuán)來保衛(wèi)$ 4 ，使得船成為未防御點(diǎn)因此，0 5 ) = 1 ，f ( y 5 ) = o ( ”如果f ( z 6 ) = f ( y 6 ) = 0 ，考慮到我們必須從粕調(diào)動軍團(tuán)來保衛(wèi)孔，而且不能 使z 6 成為未防御點(diǎn)因此f ( x 7 ) = ，西) = 1 ，矛盾因而f ( m 6 ) + f ( v 6 ) = 1 假設(shè)f ( x 6 ) = 1 ，f ( y 6 ) = 0 ，如果，( 。7 ) = ，( 們) = 0 ，則有f ( x 8 ) = f ( v s ) = 1 ，矛 盾，因此我們有f ( x 7 ) + f ( y 7 ) = 1 我們定義k x 使得 ft ，u = 蜘，z s ； 蠔( 。) = 0 ，口= $ 6 ，研，斬，y s ； i ，( ”) ， 其它 則( k ) ( ，) ，矛盾因此我們有f ( x 6 ) = 0 ，f ( y 6 ) = 1 ， ( 8 ) 設(shè)h = g 一 戤，挑：1 t 4 ) 則有乃( 硼= t n y ( 日) ，n y ( 日) ，耽n y ( 日) ) 是日的個弱羅馬控制函數(shù)而且我們有( ( h ) ) = ( ，) 一3 s 【竽j 一3 = 【塹；旦j ，與n = l i n 巴：竹( g 2 ，t ) 【挈j + 1 下面由圖1 的構(gòu)造我們證明： * ( a 2 ，。) 引甬+ l 事實(shí)上，設(shè)g 2 ，。的頂點(diǎn)集合y 為協(xié)，瓠：l i ，設(shè)u = ：t 莖氌 5 0 ，2 ，5 ( r o o d 8 ) 1 3 ?。篿 n ， ；1 ，4 ，6 ( m o d 8 ) ， 定義f = ( r o ，h ，) 如下： 當(dāng)n j0 ，3 ( m o d 8 ) 時，令h = ( u u 一1 ，) ) z 。) 當(dāng)t i i4 ，7 ( m o d 8 ) 時， 令= u t j z 。) 當(dāng)n i1 ，2 ，5 ，6 ( m o d 8 ) 時，令k = 阢 1 6 煎宣盔堂堡圭堂焦迨塞 令= 0 令g o = v 則有”( ，) = 【警j + 1 ，而且，是g 2 。的一個弱羅馬控制函數(shù) 因此命題得證口 5 4 2 弱羅馬控制數(shù)的上下界 e j c o c k a y n e 3 等給出了很多羅馬控制的性質(zhì)，例如命題3 1 1 3 ，命題3 2 【3 ，命題 a 3 1 3 】等，并且m a h e n n l n g 1 1 等也給出了一些弱羅馬控制的性質(zhì)，例如命題3 1 7 i ， 命題3 1 s l l 】等作為補(bǔ)充，我們將給出圖的弱羅馬控制的一些性質(zhì)以及弱羅馬控制 數(shù)的上下界 命題5 設(shè)，= ( v o ，h ，k ) 是圖g 的一個* ( g ) 一函數(shù)則： ( a ) 設(shè)s = u ，則對任意的口k ，肼( ”，s ) 導(dǎo)出一個團(tuán)； ( b ) 設(shè)s = k u ，若9 v o ，d ( 如) = 2 ，口l 如，u 2 v o 曰( g ) ，n u l j 一 鈾) 和 阻2 卜 v o ) 導(dǎo)出個團(tuán)并且