（計算機(jī)軟件與理論專業(yè)論文）廣義petersen圖和循環(huán)圖的羅馬支配研究.pdf

大連理工大學(xué)碩士學(xué)位論文 摘要 羅馬問題始于康斯坦丁大帝網(wǎng)世時期的軍事駐扎問題 公元三世紀(jì) 當(dāng)羅馬統(tǒng)治歐 洲的時候 通過部署帝國的軍隊 他們能防御5 0 個地區(qū)包括最邊遠(yuǎn)的地區(qū) 隨后一個 世紀(jì) 羅馬帝國軍事力量下降 這時如何駐扎盡可能少的軍隊來防止羅馬軍隊同時受到 多處攻擊成了一個主要問題 1 9 9 7 年r e v e l l e 提出了羅馬問題 1 9 9 9 年及2 0 0 0 年s t e w a r t 和r e v e l l e 發(fā)起了羅馬 支配的研究 并用圖論的理論構(gòu)造了羅馬支配數(shù) 對于圖g v e 設(shè)f v 一 o 1 2 r v o k 是由f 誘導(dǎo)出的點集礦的有序集 其中當(dāng)江o 1 2 時 形 v 礦i 廠 v f 且 i 杉i z 函數(shù)f v o k 是羅馬支配函數(shù) r d f 當(dāng)圪 其中 指集合 支配 即v o n 畋 f 的權(quán)重是廠 y 刪廠 v 2 n 羅馬支配數(shù)用 g 表示 它 等于圖g 的r d f 的最小的權(quán)重 當(dāng)f k 砭 是一個r d f 且廠 礦 z r g 我們稱它 是一個y r f u n c t i o n 鑒于廣義p e t e r s e n 圖和循環(huán)圖的重要性 本文根據(jù)前人的研究成果 針對廣義 p e t e r s e n 圖p n k 循環(huán)圖c 刀 l 后 使用羅馬支配算法求得羅馬支配集中通用的規(guī) 律 然后研究了它們的關(guān)系 以及一些情況下的精確值 主要得出以下結(jié)論 1 爍 地2 li 8 nk 5 c2 f二 三蘭 二 三 f o 7 或者即 6 12 13 19 2 6 3 0 3 2 阱 鴕艦 同時給出了廣義p e t e r s e n 圖p n 尼 以及循環(huán)圖c o 1 i j 的羅馬支配數(shù)的上界 關(guān)鍵詞 羅馬支配 支配數(shù) 支配集 廣義p e t e r s e n 圖 循環(huán)圖 1 i z一 一引降 大連理工大學(xué)碩士學(xué)位論文 r e s e a r c ho nr o m a nd o mi n a t i o ni ng e n e r a l i z e dp e t e r s e ng r a p ha n d c i r c u l a n tg r a p h a b s t r a c t r o m a n p r o b l e mi sal o c a t i o np r o b l e mw h i c ha p p r o a c h e db yt h ee m p e r o rc o n s t a n t i n ei n t h e4 t hc e n t u r y i nt h e3 r dc e n t u r y w h e nr o m ed o m i n a t e de u r o p e i tw a sa b l et od e p l o y5 0 l e g i o n st h r o u g h o u tt h ee m p i r e s e c u r i n ge v e nt h ef u r t h e r m o s ta r e a s b yt h ef o l l o w i n gc e n t u r y t h ee m p i r eh a dl o s tm u c ho fi t sm u s c l e h o w e v e r a n dr o m e sf o r c e sh a dd i m i n i s h e dt oj u s t2 5 l e g i o n s s o h o wt od e f e n dt h er o m a ne m p i r ef r o mm u l t i p l ea t t a c k sb ys t a t i o n i n ga sf e w l e g i o n sa sp o s s i b l ew i l lb et h em o s ti m p o r t a n tp r o b l e m r e v e l l es u g g e s t e dr o m a nd o m i n a t i o ni n19 9 7 af e wy e a r se a r l i e r s t e w a r ta n dr e v e l l e g i v et h ed e f i n i t i o no fr o m a nd o m i n a t i o nw i t hg r a p ht h e o r yi n19 9 9 f o rag r a p hg y e l e tf v 一 0 1 2 a n dl e t z 0 巧 砭 b et h eo r d e r e dp a r t i t i o no fvi n d u c e db yf w h e r e 杉 1 v l f v i a n df 杉l n f f o ri 0 1 2 af u n c t i o nf k 砭 i s ar o m a nd o m i n a t i n gf u n c t i o n r d f i f d o m i n a t e sv 0 i e 圪 v 0 a n dt h ew e i g h to ff i s f v 創(chuàng)廠 v 2 n 2 刀1 t h em i n i m u mw e i g h to fa l l r d fo fgi sc a l l e dt h er o m a n d o m i n a t i o nn u m b e ro fg d e n o t e db y g a n dw es a yt h a taf u n c t i o nf v 0 k i s a7 尺一f u n c t i o ni f i ti sa nr d f a n d 廠 礦 y 只 g i nt h i sp a p e r i t ht h ea l g o r i t h mo fc a l c u l a t i n gt h er o m a nd o m i n a t i o nn u m b e ro fg r a p h s w es t u d yt h er o m a nd o m i n a t i o nn u m b e ro fg e n e r a l i z e dp e t e r s e ng r a p h sp n 后 a n dc i r c u l a n t g r a p h sc 咒 1 后 a n dt h e ng e tt h ef o l l o w i n gc o n c l u s i o n s 1 爍 2 l 等b 5 m 卜 槲 q m 嘶 1 4 憎z 4 ni i脅4nl i ii j k c o 1 4 iiiii ll l i f 0 7 o r n 6 1 2 1 3 1 9 2 6 3 0 3 2 f o rg e n e r a l i z e dp e t e r s e ng r a p h sp n k a n dc i r c u l a n tg r a p h sc z l 尼 t h eu p p e r b o u n d so ft h e i rr o m a nd o m i n a t i o nn u m b e r sa r eg i v e n k e yw o r d s r o m a nd o m i n a t i o n d o m i n a t i o nn u m b e r d o m i n a t i n gs e t i i i 大連理工大學(xué)學(xué)位論文獨創(chuàng)性聲明 作者鄭重聲明 所呈交的學(xué)位論文 是本人在導(dǎo)師的指導(dǎo)下進(jìn)行研究 工作所取得的成果 盡我所知 除文中已經(jīng)注明引用內(nèi)容和致謝的地方外 本論文不包含其他個人或集體已經(jīng)發(fā)表的研究成果 也不包含其他已申請 學(xué)位或其他用途使用過的成果 與我一同工作的同志對本研究所做的貢獻(xiàn) 均已在論文中做了明確的說明并表示了謝意 若有不實之處 本人愿意承擔(dān)相關(guān)法律責(zé)任 學(xué)位論文題目 差墊臣塑絲 蟄至竺壓蘭 莖立整墨壟翌塑篁 儲鮐弓粥l(xiāng) 魄坦年上月旦日 大連理工大學(xué)碩士研究生學(xué)位論文 大連理工大學(xué)碩士研究生學(xué)位論文版權(quán)使用授權(quán)書 本人完全了解學(xué)校有關(guān)學(xué)位論文知識產(chǎn)權(quán)的規(guī)定 在校攻讀學(xué)位期間 論文工作的知識產(chǎn)權(quán)屬于大連理工大學(xué) 允許論文被查閱和借閱 學(xué)校有 權(quán)保留論文并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版 可以將 本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索 可以采用影印 縮印 或掃描等復(fù)制手段保存和匯編本學(xué)位論文 學(xué)位論文題 作者簽名 導(dǎo)師簽名 大連理工大學(xué)碩士學(xué)位論文 1緒論 1 1前言 圖論是組合數(shù)學(xué)的一個重要分支 也是離散數(shù)學(xué)的一個重要組成部分 它是研究某 些事物及它們之間關(guān)系的學(xué)科 現(xiàn)實世界中的許多事物 或?qū)ο?能用圖表示其拓?fù)浣Y(jié)構(gòu) 把實際問題的研究轉(zhuǎn)化為圖的研究 利用圖論的相關(guān)結(jié)論對這些問題作出分析和判斷 因此 圖論在自然科學(xué)和社會科學(xué)的許多領(lǐng)域有著廣泛的應(yīng)用 同時也是計算機(jī)科學(xué)的 重要基礎(chǔ) 1 7 3 6 年 e u l e r 解決了k 6 n i g s b e r g 七橋問題 這是有文字記載的最早的圖論研究文 獻(xiàn) 因此 這一事件被大家認(rèn)為是圖論作為 f j 獨立的學(xué)科出現(xiàn)的標(biāo)志 1 8 4 7 年 k i r c h h o f f 為了解一類線性聯(lián)立方程組而發(fā)展了樹的理論 1 8 5 7 年 c a y l e y 在研究有機(jī)化學(xué) 領(lǐng)域的問題時 也研究了樹的理論 在e u l e r 之后的二百年中 許多數(shù)學(xué)家各自獨立地 研究了圖論中的一些問題 但是其研究結(jié)果并沒有形成一個較為完善的體系 由于圖論 長期以來不是數(shù)學(xué)研究的主流領(lǐng)域 圖論一直在緩慢地發(fā)展著 1 9 3 6 年 k 6 n i g 編寫了 第一本圖論專著 總結(jié)了圖論二百年發(fā)展的主要成果 自二十世紀(jì)中期以來 現(xiàn)實世界的需要使得圖論領(lǐng)域的研究呈現(xiàn)出蓬勃發(fā)展的趨 勢 隨著計算機(jī)技術(shù)的廣泛應(yīng)用 圖論的研究也注入了新的活力 利用計算機(jī)技術(shù)解決 圖論問題成為一個令人感興趣的研究方向 1 9 7 6 年 美國的h a n k e r 等人利用計算機(jī)用 了1 2 0 0 小時的計算時間 解決了數(shù)學(xué)家們一百多年來所未能解決的一個著名的圖論難 題一四色問題 這一事件表明計算機(jī)技術(shù)的應(yīng)用促進(jìn)了圖論的研究與發(fā)展 因此 它在 圖論的發(fā)展歷史中占有一個重要的位置 圖論最吸引人的特色是它蘊(yùn)含著大量強(qiáng)有力的思想 漂亮的圖形和巧妙的論證 同 時 圖論又是最接近群眾生活 最易于向科學(xué)水準(zhǔn)低的人們闡述的一門學(xué)科 即使是非 常困難的尚未解決的問題也易于表達(dá) 問題外表的簡單樸素和本質(zhì)上的難以解決 使每 個搞圖論的人在圖論問題面前都必須謹(jǐn)慎嚴(yán)肅的思考問題 常常是一個貌似簡單的問 題 即使是幸運(yùn)的得出證明 證明中包含的細(xì)節(jié)也十分繁瑣 并且往往需要極艱苦的計 算 圖論發(fā)展至今 已經(jīng)積累了許多難題 至今仍找不到有效的算法去解決 如求圖中 h a m i l t o m 回路 r a m s e y 問題 籠問題以及計算任意圖的支配數(shù)問題等等 這些問題均 屬于n p 一完全問題 圖的支配問題是近年來圖論中一個比較活躍的研究領(lǐng)域 圖的支配數(shù)是在實際問題中提出的 因此 在現(xiàn)實生活的許多領(lǐng)域都有廣泛的應(yīng)用 廣義p e t e r s e n 圖和循環(huán)圖的羅馬支配研究 例如 在一個通訊網(wǎng)絡(luò)的一些節(jié)點上放置發(fā)射器 要求每個發(fā)射器的節(jié)點一定和某個發(fā) 射器的節(jié)點有一個直接的通訊線路 如何選擇節(jié)點 使得放置的發(fā)射器的數(shù)目最小 對支配數(shù)的研究 目前國內(nèi)外的研究集中在以下幾個方面 1 支配數(shù) 2 完全支配數(shù) 3 羅馬支配數(shù) 4 p a c k i n gn u m b e r 5 邊支配數(shù) 1 2 基本概念 本文中未定義的術(shù)語請參見徐俊明的 圖論及其應(yīng)用 1 b o n d y 和m u r t y 的 g r a p h t h e o r yw i t ha p p l i c a t i o n 2 h a y n e s h e d e t n i 和s l a t e r 的 f u n d a m e n t a l so fd o m i n a t i o ni n g r a p h s 3 和 d o m i n a t i o ni ng r a p h s a d v a n c e dt o p i c s 4 我們稱數(shù)學(xué)結(jié)構(gòu)g y g e g 尼 為一個圖 g r a p h 其中v v g 是一個非空 集 厶是從集合e g 到v g 礦 g 的一個映射 則稱g 是一個以v g 為頂點集 以 e g 為邊集的有向圖 d i r e c t e dg r a p h v g 中的元素稱為圖g 的頂點 v e r t e x e g 中 的元素稱為圖g 的邊 e d g e 尼稱為g 的關(guān)聯(lián)函數(shù) 若尼0 似v p e 耳g 1 9 1 坎g z 6 3 則簡寫成e u v 稱材是有向邊e 的尾 為有向邊e 的頭 在圖中用箭頭從 指向v 來表示一條有向邊 如果把有向圖中的箭 頭取消 則得到無向圖 u n d i r e c t e dg r a p h 一個圖g 中項點的數(shù)目 稱為圖g 的階 o r d e r 用i 坎o l 來表示 圖g 中邊的數(shù)目 即圖g 的邊數(shù) s i z e 稱為圖g 的大小 用 以回l 來表示 若l 坎g i i 以g i 也稱為u 的開鄰域 而頂點集合n u 材 u n u 則稱作頂點u 的閉鄰接點 集合 c l o s e dn e i g h b o r h o o d 也稱為u 的閉鄰域 如果有兩條或兩條以上的邊連接同一對頂點 則稱這些邊為多重邊 兩個端點重合 為一點的邊稱環(huán) l o o p 不包含多重邊和環(huán)的圖稱為簡單圖 s i m p l eg r a p h 大連理工大學(xué)碩士學(xué)位論文 本文所考慮的圖均為無環(huán) 無重邊的簡單有限無向圖 由圖的定義可知 一個集合v 和v 上的一個二元關(guān)系就是一個圖 因此圖的最本質(zhì) 的內(nèi)容就是一個二元關(guān)系 也就是頂點和邊的關(guān)聯(lián)關(guān)系 一個系統(tǒng)或一個結(jié)構(gòu)若具有二 元關(guān)系便可用圖作為數(shù)學(xué)模型 設(shè)v v g g 中與v 關(guān)聯(lián)的邊的個數(shù)稱為v 的度 d e g r e e 記作d v 其中每個環(huán) 在計算度數(shù)時被算作兩條邊 若d v 0 則稱1 為孤立點 i s o l a t e dv e r t e x 若d v 1 則稱v 為懸掛點 p e n d a n t v e r t e x 與懸掛點關(guān)聯(lián)的邊則稱為懸掛邊 p e n d a n te d g e 若圖g 的各頂點的度數(shù)相同 則稱圖g 為 貝l j r e g u l a rg r a p h 若對任意的v v g d v 則稱圖g 為 正則 圖 設(shè)g 是一個力階 3 缸正則圖 若對任意的u 1 y g u v 滿足 1 若u 與v 相鄰 則i n u n v i 力 2 若u 與v 不相鄰 則i n v l 則稱g 為具有參數(shù) k 名 的強(qiáng)正則圖 簡稱0 k 兄 a 強(qiáng)正則圖 而且 w v o e v 一1 e k v k 為首尾相連的邊的順序排列 v 一 v 為e t 的端點 若w 中的頂點均不 相同 則w 稱為路徑 p a t h 含甩個頂點的路徑記作 起點與終點重合的道路叫做回 路 c i r c u i t 或圈 c y c l e 含 個頂點的回路記作g 設(shè) v v g 若在g 中存在一條 材 v 路徑 則稱頂點u 和v 是連通的 c o n n e c t e d 若g 中每一對不同的頂點都連通 則稱g 為連通圖 c o n n e c t e dg r a p h 否則稱為非連通 圖 d i s c o n n e c t e dg r a p h 我們稱沒有回路的簡單連通圖為樹 t r e e 設(shè) 1 礦 g 若 v 連通 則稱最短的 材 v 路徑為測地線 g e o d e s i c 測地線的 長度稱為u 與v 之間的距離 d i s t a n c e 記作d u y 若 v 不連通 則d u v 0 0 連通圖g 中最長的測地線的長叫做g 的直徑 d i a m e t e r 記作坊口聊 g 即 d i a m g m a x d u v u v y g 每對不同項點之間均有一條邊相連的簡單圖稱為完全圖 c o m p l e t eg r a p h 玎個頂點 的完全圖記作k 對于任意連通圖g 朋 頂點v 礦 g 如果g v 不連通 則v 是g 的割點 對于g 的連通子圖b 稱為一塊 b l o c k 當(dāng)且僅當(dāng)滿足 任意子圖b g bsb b b 至少有一個割點 一個塊b 稱為最后塊 e n db l o c k 當(dāng)且僅當(dāng)滿足 召至多包含一個割 廣義p e t e r s e n 圖和循環(huán)圖的羅馬支配研究 點 圖g 稱為塊圖 b l o c kg r a p h 當(dāng)且僅當(dāng)滿足 g 的任何塊 b l o c k 都是一個完全圖 如果圖g 包含唯一一個圈 則g 是個單循環(huán)圖 如果每條邊都至多在一個圈上 則g 成 為仙人掌圖 c a c t u sg r a p h 一個圖的頂點集礦若能分成兩個非空子集x 和 使x uy v xn y a 且g 的每條邊的兩個端點分居在x 和 中 則稱此圖為二分圖 b i p a r t i t eg r a p h 記作 g x y 有時記作 x y e x y 稱為y 的一個二分戈u b i p a r t i t i o n 對于簡單二分圖g x y e 若x j x 咒 y 有 t 咒 e 則g 稱為完全二 分l 至l c o m p l e t eb i p a r t i t eg r a p h 若i x m l y n 則記為e 墨 稱為星 s t a r 設(shè)g 日是兩個任意的圖 若存在v g 到v h 上的一個一一對應(yīng)函數(shù)廠 使得 v v g 刎 e g 當(dāng)且僅當(dāng)f u f v e 忉 則稱g 日是同構(gòu)的 i s o m o r p h i c 記為g 蘭h 同構(gòu)圖具有相同的性質(zhì) 一個無標(biāo)號的圖可被看作是所有與之同構(gòu)的圖的 代表 設(shè)簡單圖g v e 互 材 v u 1 甜 v v 則稱圖h v 巨 e 為g 的補(bǔ)圖 c o m p l e m e n tg r a p h 記作h g 圖g 和日 如果v h cv g e h e g 則稱日為g 的子i 蛩 s u b g r a p h 記 為日 g 如果v h v g 或e h e g 稱日為g 的真子圖 t r u es u b g r a p h 記為 hcg 令集合scv g 若圖g 的一個子圖日滿足如下關(guān)系 v h s 且 e h u v 甜 1 s 圳 e g 則稱子圖日是從集合s 導(dǎo)出的子圖 簡稱為圖g 的導(dǎo) 出子圖 i n d u c e ds u b g r a p h 記作g s 若圖g 的一個子圖日滿足v h v g 則稱子 圖日是圖g 的生成子圖 s p a n n i n gs u b g r a p h 在圖g 中 如果頂點托 v 是相鄰的 通常稱 是u 的一個鄰接點 頂點 的鄰域集 合是圖g 中所有與u 相鄰的頂點的集合 記作 yiu v e g n u 似 un u 稱作頂點u 的閉鄰域 設(shè)u v g 稱d u ln u i 為u 的度 圖g 的頂點的最大度和最小度分別用a g 和a g 表示 若圖g 的各項點的度相同 則稱圖g 為正則圖 若任取u y g d k 則稱 圖g 為k 一正則圖 稱它的正則度為k 此時 n u vlu g e g 如圖1 1 所示的圖 為3 正則圖 完全二分圖k 是滿足以下條件所構(gòu)成的圖類 大連理工大學(xué)碩士學(xué)位論文 1 頂點分為二個集合k 圪 其中l(wèi)k m i i 刀 2 對于任意材 k v 巧 若f j 則 v 相鄰 f 1 2 如圖1 2 所示的圖為k 2 4 完全二分圖 圖1 13 正則圖 f i g 1 13 r e g u l a rg r a p h 我們把聊 1 時的完全二分圖k 稱為星圖 已知圖g v e 和h y e 如果v 日 y g e h e g 并且日中邊 的重數(shù)不能超過g 中對應(yīng)邊的重數(shù) 則稱日是g 的 s u b g r a p h 記作 g 圖1 2 k 2 4 完全二分圖 f i g 1 2 k 2 4c o m p l e t eb i p a r t i t eg r a p h 如果h 是g 的子圖 并且h g 則稱日是g 的真子圖 p r o p e rs u b g r a p h 記作 hcg 已知圖日是g 的子圖 并且v h v g 則稱日是g 的生成子圖 s p a n n i n g s u b g r a p h 如圖1 3 所示 其中 2 3 分別是圖g 的子圖 4 是圖g 的生成子圖 已知圖g v e 和h 礦 e 如果v h sy g e 日 e g 并且日中邊 的重數(shù)不能超過g 中對應(yīng)邊的重數(shù) 則稱日是g 的予圖 s u b g r a p h 記作日冬g 如果日是g 的子圖 并且h g 則稱日是g 的真子圖 p r o p e rs u b g r a p h 記作 hcg 已知圖g y e s 是礦的一個非空子集 以s 為頂點集 以兩端點均在s 中的邊 的全體為邊集所組成的子圖 稱為由s 導(dǎo)出的g 的子圖 記作g s 或簡稱g s 是g 的 廣義p e t e r s e n 圖和循環(huán)圖的羅馬支配研究 導(dǎo)出 子 i n d u c e ds u b g r a p h 圖g 的一個頂點和邊相繼交替出現(xiàn)的有限非空序列w r o e l v l e 2 l i i e t v t 其中e 的端點是v h 和1 1 i k 叫做從v 到1 的一條途徑 1 2 3 圖1 3 子圖與生成子圖 f i g 1 3s u b g r a p ha n ds p a n n i n gs u b g r a p h 4 若途徑w r o e l l l e 2 v t 1 e t 咋的頂點和邊均不相同 則稱形為通路 p a t h 起點和終點重合的通路叫做回路 c i r c u i t 或稱為圈 c y c l e 設(shè) v g 如果甜和v 連通 則稱最短的 1 一通路為測地線 g e o d e s i c 測地 線的長稱為u 與v 之間的距離 記作d u 1 一個連通圖g 中任何一條最長的測地線的長叫做g 的直徑 d i a m e t e r 記作d g 即 d g m a x d u v iu v y g 1 3 支配集和支配數(shù) 1 3 1 起源與發(fā)展 雖然圖的支配集的相關(guān)研究開始于1 9 6 0 年 但這個問題的相關(guān)領(lǐng)域的研究最早可 以追溯一百多年前 18 6 2 年 j a e n i s c h t 5 研究了如下一個問題 問題1 1 確定覆蓋 或支配 個n 聆國際象棋棋盤所需王后的最小個數(shù) 在18 9 2 年出版的 m a t h e m a t i c a lr e c r e a t i o na n dp r o b l e m so fp a s ta n dp r e s e n tt i m e s 中 r o u s eb a l l t 6 1 總結(jié)了1 9 世紀(jì)末關(guān)于國際象棋棋盤上的組合問題的研究分為如下三個 基本類型的問題 1 覆蓋問題 覆蓋 攻擊或支配 一個刀 刀棋盤上所有格子所需的某種棋子 王 王后 馬 相 車和卒 的最小個數(shù) 這個問題實質(zhì)是在以棋盤格子為頂點 以棋子的某種走法為邊所 產(chǎn)生的圖 在該圖上求其元素個數(shù)最小的支配集 大連理工大學(xué)碩士學(xué)位論文 2 獨立覆蓋問題 支配一個n r 棋盤上所有格子所需的彼此互不攻擊的某種棋子的最小個數(shù) 這個 問題實質(zhì)是在以棋盤格子為頂點 以棋予的某種走法為邊所產(chǎn)生的圖 在該圖上求其 元素個數(shù)最小的獨立支配集 3 最大獨立集問題 在棋盤上的格子中放入某種棋子 要求任意兩個棋子之間彼此互不攻擊 支配 按 這種方法 最多能放多少個棋子 這個問題實質(zhì)是在以棋盤格子為頂點 以棋子的某種 走法為邊所產(chǎn)生的圖 在該圖上求其元素個數(shù)最大的獨立集 當(dāng)我們選用的棋子為王后 這個問題就是著名的 皇后問題 1 9 6 4 年左右 y a g l o m l 7 兄弟研究了這三類問題 對于棋子王 馬 相和車的情形 他們對上述問題給出了一個很優(yōu)美地結(jié)果 表1 1 1 9 9 8 2 0 0 7 美國數(shù)學(xué)評論收錄的有關(guān)支配數(shù)的文章統(tǒng)計結(jié)果 t a b 1 1 d o m i n a t i o np a p e r sf r o mm r i n19 9 8 2 0 0 7 b e r g e 8 在他于1 9 6 2 年出版的圖論書中 第一次提出了圖的支配數(shù)的定義 當(dāng)時他稱 之為c o e f f i c i e n to fe x t e r n a l s t a b i l i t y 同一年 在o r e 9 1 出版的圖論書中第一次使用了圖 的支配集和圖的支配數(shù)的概念 他用d g 表示一個圖g 的支配數(shù) 到了1 9 7 7 年的時候 c o c k a y n e 和h e d e t n i e m i 為到當(dāng)時為止在支配問題領(lǐng)域的所有結(jié)果寫了一篇綜述 在這 篇綜述中 c o c k a y n e 和h e d e t n i e 觚 l o 第一次使用y g 表示一個圖g 的支配數(shù) 從此以 后 支配數(shù)的概念和表示符號就固定下來 被人們接受了 c o c k a y n e 和h e d e t n i e m i 的這篇文獻(xiàn)綜述開啟了支配理論現(xiàn)代研究的序幕 到1 9 9 8 年為止 在這二十年中 有關(guān)支配理論的義獻(xiàn)超過了1 2 0 0 多篇 并且還在不斷地穩(wěn)步 增長中 利用美國數(shù)學(xué)評論的搜索引擎 我們檢索了1 9 9 8 年 2 0 0 6 年間美國數(shù)學(xué)評論 收錄的文獻(xiàn)中 分類號為0 5 c 圖論問題 并且題目中帶有支配數(shù)的文獻(xiàn) 得到的結(jié)果如 表1 1 所示 這說明支配問題的研究在現(xiàn)代圖論研究中占有一個重要的地位 1 3 2 支配數(shù)的基本概念 文獻(xiàn) 3 的附錄中給出了7 0 多種支配數(shù)及相關(guān)類型的集合的定義和簡單說明 在本 文中給出基本支配數(shù) 連通支配數(shù)和樹支配數(shù)的定義及它們相關(guān)集合的定義 廣義p e t e r s e n 圖和循環(huán)圖的羅馬支配研究 定義1 1 令集合s 是一個任意圖g 的頂點集的子集 即 5 sy g 如果對任意頂 點v 坎g 有w n s 則稱s 是圖g 的一個支配集 d o m i n a t i o ns e t 如果它的任何真 子集都不是圖g 的支配集 我們稱s 為圖g 的一個極小支配集 m i n i m a ld o m i n a t i n gs e t 如果對任意一個圖g 的極小支配集s 他們滿足l s f f s f 則我們就稱極小支配集s 為 圖g 的一個最小支配集 m i n i m u md o m i n a t i n gs e t 則把集合s 的元素個數(shù)稱為圖g 的支 配數(shù) d o m i n a t i o nn u m b e r 記作 g 定義1 2 令集合s 是一個圖g 的頂點集的子集 即s y g 如果集合s 是圖g 的一個支配集 且其導(dǎo)出子圖g 嘲是連通的 那么稱集合s 是圖g 的一個連通支配集 c o n n e c t e dd o m i n a t i o ns e t 如果對任意一個圖g 的連通支配集s 滿足i s l l s i 稱連 通支配集s 為圖g 的一個最小連通支配集 m i n i m u mc o n n e c t e dd o m i n a t i n gs e t 則把集 合s 的元素個數(shù)稱為圖g 的連通支配數(shù) c o n n e c t e dd o m i n a t i o nn u m b e r 記作r a g 定義1 3 設(shè)圖g 含有的頂點數(shù)i g i 如果刪除任何一個至多含有r 一1 個點的集合 s 后 g 坎回 翻是連通的 則稱g 是r 連通的 定義1 4 設(shè)圖g 如果g 是 連通的 則g 有一個支配集s 且g 嘲是個廠連通的 子圖 那么這個支配集s 就稱為一個 連通支配集 圖g 的最小 連通支配集的大小記 作 g 圖1 4 圖g 和其補(bǔ)圖g f i g 1 4 t h eg r a p hga n di t sc o m p l e m e n tg r a p hg 定義1 5 令集合s 是一個圖g 的頂點集的子集 即s 礦 g 如果集合s 是圖g 的一個支配集 且其導(dǎo)出子圖g 閻是樹 那么我們稱集合s 為圖g 的一個樹支配集 t r e e d o m i n a t i n gs e t 如果對任意一個圖g 的樹支配集f 滿足i s i i s l 稱該樹支配集s 為 圖g 的 個最小的樹支配集 m i n i m u mt r e ed o m i n a t i n gs e t 則把集合s 的元素個數(shù)稱為 圖g 的樹支配數(shù) t r e ed o m i n a t i o nn u m b e r 記作o g 定義1 6 一個集合s v g 叫做一個g 的p a c k i n g 集當(dāng)且僅當(dāng)任意兩個點 1 s 時 都有d u y 3 也就是說s 是一個p a c k i n g 集當(dāng)且僅當(dāng)任意1 y g 有 大連理工大學(xué)碩士學(xué)位論文 in v f q si 1 p a c k i n gn u m b e r 就是所有p a c k i n g 集當(dāng)中所含頂點數(shù)最少的集合s 的元素 個數(shù) 記為p a 定義1 7 對于圖g 定義函數(shù)f e g 一 1 一1 為邊支配函數(shù)其中對于e e g 有 廠 p l 圖g 的邊支配數(shù)為y g m i n 叫g(shù) 廠 p i 俜一個邊支配函數(shù) 定義1 8 設(shè)簡單圖g v e e l 材 v iu v u v 則稱圖h y 巨 e 為 g 的補(bǔ)圖 c o m p l e m e n tg r a p h 記作h g 或g 如圖1 4 所示 定義1 9 我們稱圖g h e 為圖的連接運(yùn)算 其中圖g 是通過將頂點u y 日 與頂點v v f 合并成一個頂點u 圖中其它的邊和頂點保持不變 如圖1 5 所示 一 一1 圖1 5 兩個圖的連接運(yùn)算 f i g 1 5 t h ea s s o c i a t i v eo p e r a t o rb e t w e e nt w og r a p h s 定義1 1 0 對于圖g v e 設(shè)f v 一 0 1 2 且 k 圪 是由廠誘導(dǎo)出的點集y 的有序集 其中當(dāng)f o 1 2 時 杉 v v l f v 且i l 刀 由于廠 y 專 o 1 2 和礦的 有序集 k 之間存在1 1 的映射關(guān)系 所以我們可以寫成f 圪 k 砭 函數(shù)廠 v o v l 圪 是羅馬支配函數(shù) r d f 當(dāng) 其中 指集合 支配 如 v o 畋 f 的權(quán)重是廠 y 刪 v 2 n 以 羅馬支配數(shù)用廠 g 表示 它等于圖g 的r d f 的最小的權(quán)重 當(dāng)f v o k 圪 是 一個r d f 且f v g 我們稱它是一個y r f u n c t i o n 定義1 1 1 對于每個頂點v v g 都被支配了iu v n s1 次 我們定義個函數(shù)以用 來記錄一個頂點v 被重復(fù)支配的次數(shù) r d v in v n si 1 對于一個頂點集合v 互v g 令r d v r d v 萬 1 3 3 支配數(shù)的計算復(fù)雜性 計算任意一個圖的支配數(shù)是一個很復(fù)雜的問題 即使是我們把問題減小到只針對一 類具體的圖來計算支配數(shù) 也不一定能夠得到一個多項式時間的有效算法 廣義p e t e r s e n 圖和循環(huán)圖的羅馬支配研究 表1 2 給出了上面介紹的兩種支配數(shù)的對若干類圖的計算復(fù)雜性 其中n p 表示問 題是n p 問題 p 表示問題存在多項式時間的有效算法 表1 2 支配數(shù)的計算復(fù)雜性 t a b 1 2 c o m p u t i n gc o m p l e x i t yo fd o m i n a t i o nn u m b e r 從表中可以看出除了一些簡單圖我們可以找到一個多項式算法以外 別的圖都是 n p 困難問題 所以就目前為止我們只能對某一類圖進(jìn)行研究 1 3 4 支配集的應(yīng)用 在 f u n d a m e n t a l so f d o m i n a t i o ni ng r a p h s 的引言和第一章中 h a y n e s h e d e t n i e m i 和s l a t e r 等人給出了幾類支配集的應(yīng)用例子 支配集和網(wǎng)絡(luò)設(shè)計有很大關(guān)系 近年來 傳感器網(wǎng)絡(luò)和移動自組網(wǎng)絡(luò)的應(yīng)用中 連 通支酉己集占有一個很重要的地位 因為這兩類網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是隨機(jī)的 不斷發(fā)生變化 的 因此在網(wǎng)絡(luò)通訊中需要構(gòu)建一個虛擬的骨干網(wǎng) 而這個問題實質(zhì)上是在一個圖中尋 找連通支配集 這方面的主要討論見文獻(xiàn) 1 1 1 6 1 4羅馬支配的起源與發(fā)展 據(jù)可查的文獻(xiàn)記載 軍事駐扎問題始于康斯坦丁大帝四世時期 他所遇到的問題就 是為了避免受到別國入侵 如何部署羅馬軍隊 公元三世紀(jì) 當(dāng)羅馬統(tǒng)治歐洲的時候 他們能通過部署帝國的軍隊來保護(hù)5 0 個地區(qū)即使是最遠(yuǎn)的地區(qū) 隨后一個世紀(jì) 羅馬 帝國軍事力量下降 削減到只能部署2 5 個地區(qū) 康斯坦丁大帝提出這樣一個問題 在 不放棄核心 羅馬 的情況下如何駐扎軍隊使其有更強(qiáng)的力量來保護(hù)帝國前方的領(lǐng)土 他設(shè)計了一下防御策略來處理下降的羅馬政權(quán) 首先 它把軍隊集中劃分成若干個 軍團(tuán) p e b b l e 保證每個軍團(tuán)都有能力防御羅馬的任何一個地區(qū) 一個地區(qū)被認(rèn)為是 安全的當(dāng)他本身有這樣的軍團(tuán)駐扎或者在他鄰近的地區(qū)有兩個以上的這樣的軍團(tuán)駐扎 如圖1 6 1 7 可以用四支軍隊來保護(hù)羅馬 1 9 9 7 年r e v e l l e 在 1 7 8 中提出了羅馬閥題 1 9 9 9 年及2 0 0 0 年s t e w a r t 和r e v e l l e 大連理工大學(xué)碩士學(xué)位論文 在 1 9 2 0 q h 發(fā)起了羅馬支配的研究 2 0 0 0 年7 月e r n i ej c o c k a y n e 和p a u la d r e y e rj r 等人在 2 1 q h 給出了羅馬支配數(shù)的一些結(jié)論 1 對于任意圖g r g y r g 2 y g 2 對于任意n 個點的圖g y g g 當(dāng)且僅當(dāng)g k 3 對于任意的 一f u n c t i o nf 廠 k 則 k 的導(dǎo)出子圖g 阮 的度最大為1 k 和吒中的點不會有連邊 中的點最多跟兩個與k 相鄰的點 以是圖g v ou 一個7 一s e t 一 設(shè)日 g v ou 則每一個點1 最少有兩個日一p n n 一 如果v 是g 畋 中的孤立點且只有一個外部的h p n 稱為w v o 則 n w nk 矽 設(shè)g 眈 中的非孤立點的個數(shù)為后 使c 1 v o l v n l 2 1 rc i c i 則 n o n 2 k t c f i g 1 6s i m p l eg r a p h1o fr o m a n 4 對于刀個頂點且其最大度數(shù)為 的圖g 五2 石n g 5 對于聆個頂點的圖g g z 墨旦號宰鏟 6 對于完全 z 分圖g k 其中朋l m 2 m 則 廣義p e t e r s e n 圖和循環(huán)圖的羅馬支配研究 如果m 1 3 則y r g 4 如果m 1 2 則y r g 3 如果m 1 1 則y 月 g 2 7 如果g 是有以個結(jié)點的連通圖且 g 廠 g 1 當(dāng)且僅當(dāng)有一個點v v 其度 為n r g 8 如果g 是有n 個結(jié)點的連通圖且 g f g 2 當(dāng)且僅當(dāng) 不存在點v v 其度為刀一y g 存在一個點v v 其度為n r g 一1 或者g 有兩個點v 和w 能夠使得 i v u w n y g 2 9 如果g 是r o m a n 當(dāng)且僅當(dāng)它有一個y r f u n c t i o nf f v o k v 2 有 n l 吲 0 f i g 1 7s i m p l eg r a p h2o fr o m a n 2 0 0 1 年7 月m i c h a e la h e n n i n g 和s t e p h e nt h e d e t n i e m i 在 2 2 中探索出一種新的 策略在仍然保護(hù)羅馬帝國的情況下 使得軍事消耗盡可能少 并得出以下結(jié)論 1 對于任意圖g 的羅馬支配函數(shù)r d f 也是該圖的弱羅馬支配函數(shù)形勝灑 2 對于任意圖g g y g g 2 y g 3 當(dāng)n 3 時 只 c l 2 n 3i 4 如果一個圖g 有7 個頂點的路徑p 路徑內(nèi)的第一個點的度至少為2 則對于 圖g 的任意一個w r d f 廠有 廠 礦 尸 3 5 對于任意圖g 的任意點甜 通過從點 增加一個長為7 的路徑所得的圖日滿足 大連理工大學(xué)碩士學(xué)位論文 以 日 以 g 3 6 凱 1 時 從驢引 7 如果圖h 是圖g 的生成子圖 則 以 g 以 日 8 如果圖g 有一個以 g 一f u n c t i o n 存在兩個相鄰的點u 和v 其值為0 則 以 g 以 g u v 1 1 9 當(dāng)?shù)?4 時 以 g 7 j 等i l l 1 0 對于任意圖g z g 以 g 當(dāng)且僅當(dāng)存在一個y g 一s e ts 滿足 對于任意的點1 s p n v s 導(dǎo)出一個團(tuán) 對于任意的非s 的私有鄰域的點u v g 一s 存在一個點v s 使得 p n v s u u 導(dǎo)出一個團(tuán) 1 1 如果圖g 滿足2 y g 以 g 則對于每一個z g 一s e ts 和每一個點v s 集 合e p n v s 包括兩個不相鄰的點 1 2 弱羅馬支配w r d f 屬于 p c o m p l e t e 問題 即使是二部圖或者弦圖 2 0 0 1 年1 2 月m i c h a e la h e n n i n g 在 2 3 中用圖論的理論給出了通過駐扎盡可能少的 軍隊來防止羅馬軍隊同時受到多處攻擊的一些定義和概念 并得出以下結(jié)論 1 對于任意的連通圖g 并且k l 顯然有r g y g 2 對于任意的連通圖g v e k 1j ty g y g 如果s 是一個y g s e t 則 對于任意的v s e p n v s u v 是一個團(tuán) 對于任意的非s 中點的私有鄰域的點甜 v s 存在一個點v s 使得 u 卜e p n v s u v 3 當(dāng)k 1 時 一個樹丁滿z y zz t 7 丁 當(dāng)且僅當(dāng)k 1 而且丁 f 或者尼 1 而且 丁是一個樹的冠 4 對于任意的連通圖g 并且k 1 有蝶 g k 1 g 5 對于任意的連通圖g v e k 1 且y g k 1 r g 對于每一個 y g 一s e ts 和每一個點v s e p n v s 包括一個k 1 個點的獨立集 6 對于一個度最少為3 的樹r 丁只有唯一的一個y 丁 一s e t 當(dāng)且僅當(dāng)丁有一個 r t 一s e ts 使得對于任意一個點v s 有ie p n v s i 2 廣義p e t e r s e n 圖和循環(huán)圖的羅馬支配研究 7 如果k 1 且樹丁滿足蝶 z 七 1 廠叮 則7 有唯一的一個r t s e t 8 如果k 1 且樹丁有唯一的一個y t s e ts 則甌 1 t 量s 9 如果七 l 且樹丁有唯一的一個7 丁 一s e ts 且s 的每一個點都是 七 1 一s u p p o r t 則7 t k 1 r t 1 0 如果k 1 且樹丁有唯一的一個y 丁 一s e ts 且s 的每一個點都不是 尼 1 一s u p p o r t 則y 丁 后 1 y 丁 1 1 如果森林f 有唯一的一個y f 一s e ts 且f 有一部沒有 k 1 一s u p p o r t 的點 貝0 y f 1 1 1 v l v o 2 v 2 v 2 v o u 3 l 3 v 3 v o f i l 礦 e 1 e f 1 1 l 1 l 1 2 v o u 2 u 3 甜1 1 l v l v 2 v 2 v o v o l 9 2 v o u 3 2 0 0 6 年h e n n i n gf e m a u 在 2 8 中給出了一種用參數(shù)化的方法來計算圖的羅馬支配 數(shù) 并得出對于任意的圖羅馬支配的計算時間復(fù)雜度是r v 2 卜c o m p l e t e 2 0 0 6 年7 月李書超和朱忠熏在 2 9 中利用圖論的方法研究了圖g 以及同其補(bǔ)圖g 的 r o m a n 控制數(shù) 得到了完全圖和完全多部圖的補(bǔ)圖的r o m a n 控制數(shù)及圖g 同其補(bǔ)圖g 的r o m a n 控制數(shù)的關(guān)系 還研究了圖g 的生成子圖日同g 的r o m a n 控制數(shù)的關(guān)系和極 大無完美匹配的簡單圖g 的r o m a n 控制數(shù) 2 0 0 6 年10 月f ux u e l i a n g 和y a n gy u a n s h e n g 在 30 中針對e m i ej c o c k a y n e 和p a u l 廣義p e t e r s e n 圖和循環(huán)圖的羅馬支配研究 a d r e y e rj r 等人在2 0 0 0 年提出的公開問題 給出了一些屬于羅馬圖的正則圖并得出以 下結(jié)論 1 當(dāng)?shù)?7 且 2 4 m o d 5 循環(huán)圖c n 1 3 是羅馬圖 2 當(dāng) z 4 n 2 k f 1 2 k b 2 且 2 l m o d 2 k 1 循環(huán)圖c n 1 2 后 是羅 馬圖 l 盟 1 3 當(dāng)胛 0 m d 4 e i o k 畢時 廣義p e t e r s e n 圖尸 殤2 七 1 是羅馬圖 4 當(dāng)n 3rn 2 m o d 4 時 廣義p e t e r s e n 圖p n 1 是羅馬圖 5 當(dāng)?shù)?11 或者1 7 gn 3 模4 時 廣義p e t e r s e n 圖p n 3 是羅馬圖 6 當(dāng)n 1rm 1 時 笛卡爾積g m c 5 是羅馬圖 2 0 0 6 年1 2 月r u b a l c a b a 和s l a t e r 在 3 1 q b 給出了羅馬支配數(shù)的影響參數(shù)的定義 并 得出以下結(jié)論 1 對于任意1 1 個點的圖g 有只 g 刀 r 露 g 2 對于任意的圖g 有疋 g f g 3 對于任意刀 z 3 個點的圖g 且疋 g n 則對于任意的有效的羅馬支配函數(shù) 廠有k 4 f r g 眇 g j 表示r 霄 g 陟 g i 但是反過來卻不成立 5 對于任意的圖g 有r 尺 g r g 6 對于任意有刀個點的樹丁 有r 尺 t 胛 2 0 0 7 年12 月f a v a r o n 和k a r a m i 等人在 3 2 中針對e m i ej c o c k a y n