本文關鍵詞：無線傳感器網(wǎng)絡能效優(yōu)先通信技術研究，由筆耕文化傳播整理發(fā)布。

《上海交通大學》 2008年

圖的控制集的一些相關問題的研究

彭茂  

【摘要】： 控制集是圖論中的重要概念,它定義為圖中的一個點集,使得圖中其它任何一點都與該點集中的某點相鄰.這一概念的提出始于Konig、Berge和Ore,他們的著作和Cockayne, Hedetniemi,以及Larskar和Walikar等人的文章為后來的研究者提供了有益的啟示. 在過去的30多年里,對圖的各類控制集參數(shù)問題以及控制參數(shù)與圖的其他參數(shù)的關系問題的研究已經(jīng)成為圖論研究的一個重要領域.在此期間,各種新的控制參數(shù)被不斷提出,如具有“連通性”的控制集,具有“距離控制性”的控制集,具有“無贅性”的控制集等等,本文在連通控制集和距離控制集的基礎上引入一種新的控制集–“[r,R]-控制集”,并從算法的角度來討論它的性質(zhì). 如何尋找圖的最小控制集是一個NP困難問題,它不能通過回溯法或隨機化算法有效地解決,在這種情況下,對于其中的一些問題,代之以設計近似算法,我們要保證它是一個多項式時間算法,并且能得到一個近似于最優(yōu)解的“合理”的解.對于最小化問題,算法的近似解與最優(yōu)解的比值稱為算法的近似比.近似比與1越靠近,算法所得的解就與最優(yōu)解越接近.遺憾的是,并不是所有問題都能找到近似比為常數(shù)的近似算法,比如,已經(jīng)證明:在P = NP的前提下,最小控制集問題就不可能找到比O(lnn)更好的算法. 在本文第二章中,我們首先引入了[r,R]-控制集的準確定義,然后對一般圖中的最小[r,R]-控制集問題提出了一個近似比為lnΔ_r + [(2r+1)/R]-1的算法,這已經(jīng)與O(lnn)同階,可以認為,在一般圖中,其改進的余地已經(jīng)很小.然后我們分別考慮圖的[r,R]-控制數(shù)與圖的大小的關系、圖的[r,R]-控制數(shù)與其補圖的[r,R]-控制數(shù)的關系、圖的[r,R]-控制集與全控制集的關系,得到了圖的[r,R]-控制數(shù)的三個不同上界. 在第三章,我們從實際應用出發(fā),將最小[r,R]-控制集限定在單位圓盤圖中,考慮單位圓盤圖中的特殊幾何結(jié)構(gòu),得到了近似比為[4r(r + 1)(1 - (2θ-sin(2θ)/π)][(r+1)/R](常數(shù))的算法,其中θ= arccos 2rR+1.在r,R取特殊參數(shù)的情況下,對算法的近似比進行了更細致的刻劃. 在第四章,我們將最小[r,R]-控制集限定在隨機正則圖中,利用極大獨立集給出了一個隨機算法,并通過微分方程的方法分析了算法的返回值,進而得到了正則圖中最小[r,R]-控制集的漸近界,并且證明,在r足夠大的時候,最小[r,r + 1]-控制集的漸近界不超過d d/((d - 2)(d - 1)~(d/(d-2)).在對隨機算法進行分析的過程中,我們指出了一篇主要參考文獻在數(shù)據(jù)處理上的錯誤. 最后,我們給出對未來工作的展望作為結(jié)尾.

【關鍵詞】：
【學位授予單位】：上海交通大學
【學位級別】：博士
【學位授予年份】：2008
【分類號】：O157.5
【目錄】：

摘要5-7

ABSTRACT（英文摘要)7-11

第一章 緒論11-23

1.1 控制集與近似算法11-12

1.2 幾類特殊的控制集12-18

1.2.1 連通控制集12-15

1.2.2 弱連通控制集15-17

1.2.3 距離控制集17-18

1.3 本文內(nèi)容18-23

1.3.1 一般圖中的[r,R]-控制集18-20

1.3.2 UDG中的[r,R]-控制集20-21

1.3.3 正則圖中的[r,R]-控制集21-23

第二章 一般圖中的[r,R]-控制集23-39

2.1 [r,R]-控制集的引入23-27

2.1.1 RNP問題介紹23-24

2.1.2 [r,R]-控制集的引入24-27

2.2 一般圖中[r,R]-控制集的近似算法27-30

2.2.1 [r,R]-控制集的算法描述27-29

2.2.2 [r,R]-控制集算法的性能分析29-30

2.3 一般圖中[r,R]-控制數(shù)的界30-39

2.3.1 [r,R]-控制數(shù)的上界30-35

2.3.2 Nordhaus-Gaddum型結(jié)果35-36

2.3.3 [r,R]-控制數(shù)與全控制數(shù)的關系36-39

第三章 UDG中的[r,R]-控制集39-47

3.1 UDG中的獨立集與控制集39-41

3.2 UDG中最小[r,R]-控制集的算法41-44

3.3 特殊參數(shù)下的改進44-47

第四章 正則圖中的[r,R]-控制集47-59

4.1 隨機正則圖與微分方程47-48

4.2 正則圖中的[r,R]-控制集48-59

4.2.1 正則圖中[r,r + 1]-控制集的隨機算法48-49

4.2.2 [r,r + 1]-控制集的隨機算法的平均分析49-57

4.2.3 正則圖中最小[r,R]-控制集的界57-59

第五章 結(jié)論與未來工作展望59-62

附錄A62-63

參考文獻63-71

主要符號對照表71-72

攻讀博士學位期間完成的論文72-73

致謝73

下載全文 更多同類文獻

CAJ全文下載

(如何獲取全文？ 歡迎：購買知網(wǎng)充值卡、在線充值、在線咨詢)

CAJViewer閱讀器支持CAJ、PDF文件格式

【共引文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 陳冬松;劉治國;王光興;;移動Ad-hoc網(wǎng)絡管理中基于節(jié)點定位的簇生成算法[J];兵工學報;2007年10期

2 丁立軍;劉凱;李漢濤;張軍;;自組織網(wǎng)絡中UPMA協(xié)議的群間仿真[J];北京航空航天大學學報;2006年03期

3 薛楠;周賢偉;周健;;認知無線電網(wǎng)絡自私行為問題及安全解決方案[J];北京科技大學學報;2009年09期

4 王海濤;移動Ad hoc網(wǎng)絡的分簇算法及性能比較[J];北京郵電大學學報;2004年01期

5 薛鈺;曾志民;郭義武;郭彩麗;;認知無線電中基于相似性的自適應分簇算法[J];北京郵電大學學報;2008年03期

6 王海濤;分簇結(jié)構(gòu)在Ad Hoc網(wǎng)絡中的應用綜述[J];重慶郵電學院學報(自然科學版);2003年04期

7 王海濤,李桂倫;Adhoc網(wǎng)絡中骨干網(wǎng)的建立和維護[J];重慶郵電學院學報(自然科學版);2005年01期

8 王琳珠;范亞芹;胡可剛;;基于Ad Hoc的有效廣播路由算法[J];吉林大學學報(信息科學版);2009年01期

9 張靜,孫雨耕,房朝暉;能量有效的最小連通支配集近似算法[J];傳感技術學報;2004年04期

10 鄭嬋;尹令;孫世新;;無線傳感器網(wǎng)絡中d-Hop 2-連通容錯支配集的分布式構(gòu)造算法[J];傳感技術學報;2012年05期

中國重要會議論文全文數(shù)據(jù)庫 前10條

1 張強;夏艷;龔正虎;;一種基于信譽評估與能量輔助約束的混合MANET分簇協(xié)議[A];第八屆全國信息隱藏與多媒體安全學術大會湖南省計算機學會第十一屆學術年會論文集[C];2009年

2 趙光勝;王曉東;劉權(quán);國文成;;混合式MANET中一種基于虛擬認證者的接入認證系統(tǒng)[A];第18屆全國多媒體學術會議（NCMT2009）、第5屆全國人機交互學術會議（CHCI2009）、第5屆全國普適計算學術會議（PCC2009）論文集[C];2009年

3 王瑜;孟濤;相敬林;夏靖波;;一種應用于Ad hoc網(wǎng)絡管理的分簇算法[A];2005中國控制與決策學術年會論文集（下）[C];2005年

4 包永平;任亞萍;;無線自組織網(wǎng)網(wǎng)絡分群算法研究[A];2007通信理論與技術新發(fā)展——第十二屆全國青年通信學術會議論文集（下冊）[C];2007年

5 ;SLID: A Secure Lowest-ID Clustering Algorithm[A];Proceedings of the 1st Chinese Conference on Trusted Computing and Information Security[C];2004年

6 趙寧;;軍用自組織網(wǎng)絡體系結(jié)構(gòu)研究[A];開創(chuàng)新世紀的通信技術——第七屆全國青年通信學術會議論文集[C];2001年

7 王海濤;張學平;;Ad Hoc網(wǎng)絡中骨干網(wǎng)的建立和維護[A];現(xiàn)代通信理論與信號處理進展——2003年通信理論與信號處理年會論文集[C];2003年

8 李漢濤;劉凱;張軍;;高動態(tài)自組織網(wǎng)絡中的高效多址接入?yún)f(xié)議[A];2005通信理論與技術新進展——第十屆全國青年通信學術會議論文集[C];2005年

9 包永平;劉作學;;無線自組織網(wǎng)的網(wǎng)絡分群算法研究[A];四川省通信學會2005年學術年會論文集[C];2005年

10 陳太尚;;一種基于認知無線電的組合加權(quán)分簇算法[A];2009年全國無線電應用與管理學術會議論文集[C];2009年

中國博士學位論文全文數(shù)據(jù)庫 前10條

1 李青;無線移動自組網(wǎng)MAC關鍵技術研究[D];解放軍信息工程大學;2009年

2 王偉;無線傳感器網(wǎng)絡若干關鍵技術研究[D];華中科技大學;2011年

3 趙楠楠;無線傳感器網(wǎng)絡拓撲控制算法研究[D];北京郵電大學;2011年

4 楊凱;無線Mesh網(wǎng)絡高性能路由協(xié)議研究[D];西安電子科技大學;2011年

5 馬闖;無線傳感器網(wǎng)絡容錯關鍵技術研究[D];哈爾濱工業(yè)大學;2011年

6 王旭東;基于圖論的智能電網(wǎng)最優(yōu)孤島劃分模型和算法[D];天津大學;2011年

7 石勝林;基于無線Mesh網(wǎng)QoS關鍵技術研究[D];華中科技大學;2011年

8 掌明;無線傳感器網(wǎng)絡能效優(yōu)先通信技術研究[D];南京郵電大學;2011年

9 陳育斌;高速分組無線網(wǎng)關鍵技術研究[D];西安電子科技大學;2000年

10 張文柱;無線Ad Hoc網(wǎng)絡中若干關鍵技術研究[D];西安電子科技大學;2003年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 黃江;Ad Hoc網(wǎng)絡分簇路由協(xié)議的研究與優(yōu)化[D];南昌大學;2010年

2 潘霞;能量有效的無線傳感器網(wǎng)絡分群路由協(xié)議的研究與實現(xiàn)[D];解放軍信息工程大學;2010年

3 靳超;戰(zhàn)術自組網(wǎng)的分群與連通性問題的研究[D];東華大學;2011年

4 李云紅;無線傳感器網(wǎng)絡能量均衡路由算法研究[D];西安電子科技大學;2011年

5 石玲玲;Ad Hoc網(wǎng)絡證書撤銷機制的分析和研究[D];西安電子科技大學;2011年

6 趙金輝;小區(qū)PHS系統(tǒng)深度覆蓋設計[D];西安電子科技大學;2008年

7 楊東東;Ad Hoc網(wǎng)絡中廣播算法的研究[D];吉林大學;2011年

8 于亮亮;智能用電小區(qū)無線自組織網(wǎng)絡方案設計[D];華北電力大學（北京）;2011年

9 王楠楠;無線網(wǎng)絡中基于CDS的拓撲控制算法研究[D];曲阜師范大學;2011年

10 高永康;VANET路由及路由安全研究[D];北京郵電大學;2011年

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 羅永萍;楊愛民;;有向路和有向圈的控制集數(shù)[J];高等學校計算數(shù)學學報;2007年01期

2 張忠輔,張建勛;若干圖參數(shù)的關系[J];科學通報;1990年16期

3 閆慶旭;一類控制系統(tǒng)的控制集和最優(yōu)控制[J];煙臺大學學報(自然科學與工程版);1990年02期

4 陳衛(wèi)東,孟小華;求圖控制集問題的模擬退火算法的改進[J];重慶師范大學學報(自然科學版);2004年02期

5 陳宏宇;牛翠霞;鄒青松;;樹的k-分支限制控制數(shù)的一個下界[J];山東大學學報(理學版);2010年02期

6 孫天川,趙敏,康麗英;循環(huán)圖及單圈圖的有效控制集與完美控制集[J];上海大學學報(自然科學版);2004年05期

7 王璐;劉展鴻;熊黎明;;一類含有兩個分支2-因子的無爪圖[J];江西教育學院學報;2007年03期

8 徐保根;羅茜;丁宗鵬;;關于圖的集控制數(shù)[J];華東交通大學學報;2011年05期

9 阿勇嘎,斯欽;圖的臨界控制集與優(yōu)控制集[J];寶雞文理學院學報(自然科學版);2004年04期

10 齊登記,梁希泉;關于圖的控制數(shù)Vizing's定理的推廣[J];東北師大學報(自然科學版);2005年01期

中國重要會議論文全文數(shù)據(jù)庫 前10條

1 沈志君;;歐盟、美國、英國及中國反壟斷法立法目的及客體異同初探[A];2009中華全國律師協(xié)會知識產(chǎn)權(quán)專業(yè)委員會年會暨中國律師知識產(chǎn)權(quán)高層論壇論文集（下）[C];2009年

2 許立儉;韓崇昭;萬百五;;工業(yè)過程穩(wěn)態(tài)優(yōu)化控制ISOPE算法的魯棒性初探[A];1992年中國控制與決策學術年會論文集[C];1992年

3 張勤照;張文武;楊清;高德欣;;青鋼小型一廠泵房電氣智能集中管控系統(tǒng)設計[A];全國冶金自動化信息網(wǎng)2009年會論文集[C];2009年

4 宋獻中;李源;;持股相近型公司大股東的監(jiān)督與聯(lián)盟行為——基于中國上市公司的研究[A];中國會計學會2006年學術年會論文集（中冊）[C];2006年

5 趙文榮;侯學章;朱廣田;;關于雙線性分布參數(shù)系統(tǒng)的一類最優(yōu)控制[A];1994年中國控制會議論文集[C];1994年

6 陳奕琳;馬樹萍;程兆林;;線性奇異系統(tǒng)的二次指標最優(yōu)控制問題[A];1996年中國控制會議論文集[C];1996年

7 陶剛;張冬;;傳媒集團財務系統(tǒng)遠程接入的實現(xiàn)[A];中國新聞技術工作者聯(lián)合會2008年學術年會論文集（上）[C];2008年

8 王琦;秦軍;楊水陸;;樂灘水電站洪水系列一致性評價[A];中國水力發(fā)電工程學會水文泥沙專業(yè)委員會第七屆學術討論會論文集（下冊）[C];2007年

9 邢科義;胡保生;陳浩勛;;受控Petri網(wǎng)的極大允許狀態(tài)反饋控制律的綜合算法[A];1993中國控制與決策學術年會論文集[C];1993年

10 王新;李燕萍;袁兵;;基于回路的無線自組網(wǎng)的拓撲發(fā)現(xiàn)和路由管理[A];科技、工程與經(jīng)濟社會協(xié)調(diào)發(fā)展——中國科協(xié)第五屆青年學術年會論文集[C];2004年

中國重要報紙全文數(shù)據(jù)庫 前10條

1 賽迪顧問通信產(chǎn)業(yè)研究中心副總經(jīng)理 楊凱;[N];通信產(chǎn)業(yè)報;2007年

2 本報記者 次仁羅布;[N];山南報(漢);2006年

3 蔣少龍;[N];證券時報;2007年

4 常虹;[N];中國工業(yè)報;2004年

5 ;[N];中國經(jīng)營報;2003年

6 湖南省邵東職業(yè)中專 朱世民;[N];電子報;2006年

7 胡文佳;[N];中國企業(yè)報;2003年

8 韋巍　陳楫寶;[N];21世紀經(jīng)濟報道;2005年

9 屈連志 記者 高靖峰;[N];錦州日報;2007年

10 本報記者 凌云峰;[N];上海證券報;2008年

中國博士學位論文全文數(shù)據(jù)庫 前10條

1 陳磊;圖中配對控制集問題的機械化算法研究[D];華東師范大學;2010年

2 李憲越;關于一些網(wǎng)絡最優(yōu)化問題的近似算法的研究[D];蘭州大學;2009年

3 劉清海;幾類組合優(yōu)化問題的算法研究[D];新疆大學;2012年

4 陳星;幾類圖的連通性和控制集[D];新疆大學;2011年

5 胡夫濤;圖的約束數(shù)研究[D];中國科學技術大學;2012年

6 蔣紅星;圖的幾類控制參數(shù)研究[D];上海大學;2009年

7 單而芳;圖的控制數(shù)及其相關參數(shù)[D];上海大學;2005年

8 陸由;圖的控制理論研究[D];中國科學技術大學;2010年

9 董九英;圖的彩虹連通數(shù)的若干上界[D];南開大學;2013年

10 趙衍才;圖的某些控制參數(shù)的計算[D];上海大學;2011年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 秦敏艷;路和圈的定位控制集問題[D];華東師范大學;2010年

2 李業(yè)芳;無線傳感器網(wǎng)絡中連通控制集問題的研究[D];北京郵電大學;2010年

3 李秀英;求最小2連通r步控制集的兩種算法[D];新疆大學;2011年

4 何永能;圖的電力控制集問題[D];華東師范大學;2012年

5 盛斌;立方圖的配對控制集問題上界[D];華東師范大學;2013年

6 吳亞娜;無爪圖配對控制集問題上界的研究[D];華東師范大學;2013年

7 秦云龍;連通控制集的構(gòu)造與維護算法研究[D];曲阜師范大學;2010年

8 呂杰;圖中K-控制參數(shù)之間的一些關系[D];大連理工大學;2008年

9 羅永萍;幾乎正則多部競賽圖的Hamilton性和有向圖中幾個計數(shù)問題[D];山西大學;2005年

10 鄧婉婷;基于許可證的數(shù)字版權(quán)管理策略研究[D];華中科技大學;2006年

  本文關鍵詞：無線傳感器網(wǎng)絡能效優(yōu)先通信技術研究，由筆耕文化傳播整理發(fā)布。

，

本文編號：162027