本文關(guān)鍵詞：圖的極大鄰集搜索算法序列及序列終點(diǎn)的性質(zhì)研究，，由筆耕文化傳播整理發(fā)布。

【摘要】：本文主要研究極大鄰集搜索算法(Maximal Neighborhood Search,簡(jiǎn)記為MNS),重點(diǎn)考慮由這種算法在圖上生成的序列和序列終點(diǎn)所滿足的性質(zhì).論文首先分析了MNS算法與字典序廣度優(yōu)先搜索(LexBFS)算法、最大勢(shì)能搜索(MCS)算法以及字典序深度優(yōu)先搜索(LexDFS)算法的相似性.我們用與LexBFS、MCS和LexDFS類似的方法,從弦圖入手,發(fā)現(xiàn)MNS序列不一定是moplex刪除序列,區(qū)別于已知的LexBFS、MCS和LexDFS序列都可以定義moplex刪除序列.之后為了尋找圖的極小分割集和極大團(tuán),考慮到MNS算法的特性,我們從指標(biāo)搜索(label search)的角度入手,探索出當(dāng)MNS序列中標(biāo)號(hào)相鄰的點(diǎn)的指標(biāo)集滿足一定條件后,我們便可以通過(guò)相鄰兩點(diǎn)中標(biāo)號(hào)較晚的點(diǎn)的指標(biāo)求得圖的極小分割集,并通過(guò)相鄰兩點(diǎn)中標(biāo)號(hào)較早的點(diǎn)和它的指標(biāo)集導(dǎo)出圖的極大團(tuán).文章中我們利用數(shù)學(xué)歸納法從不同角度證明了這種方法的正確性.同時(shí),給出反例說(shuō)明這種方法在非弦圖上并不適用.最后,我們研究了MNS序列終點(diǎn)的性質(zhì),并證實(shí)了弦圖中MNS序列終點(diǎn)一定屬于某個(gè)molpex.然而在將結(jié)論推廣到一般圖上時(shí)發(fā)現(xiàn)非弦圖上的MNS序列終點(diǎn)不滿足這個(gè)性質(zhì).
【關(guān)鍵詞】：極大鄰集搜索算法 序列 極小分割集 極大團(tuán) moplex
【學(xué)位授予單位】：蘭州大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5
【目錄】：

• 中文摘要3-4
• Abstract4-6
• 第一章 引言6-8
• 1.1 極大鄰集搜索算法的背景及研究現(xiàn)狀6-7
• 1.2 本文研究?jī)?nèi)容7
• 1.3 本文結(jié)構(gòu)7-8
• 第二章 基本概念及符號(hào)說(shuō)明8-11
• 第三章 極大鄰集搜索序列及序列終點(diǎn)的性質(zhì)11-27
• 3.1 極大鄰集搜索序列與moplex刪除序列的關(guān)系11-13
• 3.2 在弦圖上利用極大鄰集搜索算法尋找極小分割集13-23
• 3.3 在弦圖上利用極大鄰集搜索算法尋找極大團(tuán)23-25
• 3.4 極大鄰集搜索算法在弦圖上終點(diǎn)的性質(zhì)研究25-27
• 第四章 總結(jié)27-28
• 附錄28-29
• 參考文獻(xiàn)29-30
• 致謝30

【相似文獻(xiàn)】

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

1 黃帥;馬良;;多目標(biāo)0-1規(guī)劃的和聲搜索算法[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);2012年17期

2 雍龍泉;劉三陽(yáng);拓守恒;熊文濤;陳濤;;改進(jìn)的和聲搜索算法求絕對(duì)值方程[J];黑龍江大學(xué)自然科學(xué)學(xué)報(bào);2013年03期

3 王慧敏;賀興時(shí);盛孟龍;;一種改進(jìn)的和聲搜索算法[J];紡織高校基礎(chǔ)科學(xué)學(xué)報(bào);2013年03期

4 馮遠(yuǎn)靜;俞立;馮祖仁;;蟻群協(xié)同模式搜索算法及其收斂性分析[J];控制理論與應(yīng)用;2007年06期

5 劉勇;馬良;;非線性極大極小問(wèn)題的混沌萬(wàn)有引力搜索算法求解[J];計(jì)算機(jī)應(yīng)用研究;2012年01期

6 金文梁;;量子搜索算法的多相位關(guān)系研究[J];計(jì)算機(jī)學(xué)報(bào);2012年07期

7 張偉;李華天;劉積仁;;線性可采納搜索算法的充要條件[J];控制與決策;1992年02期

8 李樹(shù)榮;陳國(guó)霞;雷陽(yáng);張強(qiáng);;一種多策略協(xié)同的加速和聲搜索算法[J];系統(tǒng)科學(xué)與數(shù)學(xué);2013年10期

9 余鵬;雋志才;;兩層應(yīng)急搶修系統(tǒng)選址問(wèn)題的核搜索算法[J];計(jì)算機(jī)應(yīng)用研究;2013年11期

10 歐陽(yáng)海濱;高立群;鄒德旋;孔祥勇;;和聲搜索算法探索能力研究及其修正[J];控制理論與應(yīng)用;2014年01期

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

1 張玲;姜立志;;能量抵消測(cè)量相位中的相位搜索算法[A];2009年全國(guó)水聲學(xué)學(xué)術(shù)交流暨水聲學(xué)分會(huì)換屆改選會(huì)議論文集[C];2009年

2 李金;蔣國(guó)平;;一種改進(jìn)的復(fù)雜網(wǎng)絡(luò)搜索算法[A];2007中國(guó)控制與決策學(xué)術(shù)年會(huì)論文集[C];2007年

3 羅家祥;唐立新;李小林;劉建榮;鄔成新;;分散搜索算法在板坯匹配優(yōu)化問(wèn)題中的應(yīng)用研究[A];全國(guó)冶金自動(dòng)化信息網(wǎng)2009年會(huì)論文集[C];2009年

4 李瀟磊;伍瑞卿;朱維樂(lè);;運(yùn)動(dòng)搜索算法的比較與改進(jìn)[A];2007北京地區(qū)高校研究生學(xué)術(shù)交流會(huì)通信與信息技術(shù)會(huì)議論文集（上冊(cè)）[C];2008年

5 程振波;鄧志東;;優(yōu)化策略模型下的匹配律算法[A];2009年中國(guó)智能自動(dòng)化會(huì)議論文集（第五分冊(cè)）[東南大學(xué)學(xué)報(bào)（增刊）][C];2009年

6 彭明僑;羅先覺(jué);鄒曉松;;基于改進(jìn)概率搜索算法的模擬電路故障診斷[A];第四屆中國(guó)測(cè)試學(xué)術(shù)會(huì)議論文集[C];2006年

7 常新杰;李言俊;;搜索算法的研究進(jìn)展[A];1998年中國(guó)智能自動(dòng)化學(xué)術(shù)會(huì)議論文集（上冊(cè)）[C];1998年

8 糜玉林;左斌;;基于協(xié)同控制的極值搜索算法與控制器一體化設(shè)計(jì)[A];2007年中國(guó)智能自動(dòng)化會(huì)議論文集[C];2007年

9 鐘普查;鮑皖蘇;;基于相位變換的量子搜索算法研究[A];第十三屆全國(guó)量子光學(xué)學(xué)術(shù)報(bào)告會(huì)論文摘要集[C];2008年

10 羅春華;張繼勇;鄭方;徐明星;;一種基于HTK的詞圖搜索算法[A];第六屆全國(guó)人機(jī)語(yǔ)音通訊學(xué)術(shù)會(huì)議論文集[C];2001年

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前8條

1 孫杰;基于絕熱演化的量子搜索算法研究[D];華中科技大學(xué);2013年

2 張映玉;絕熱量子搜索算法研究[D];華中科技大學(xué);2011年

3 閻興

本文編號(hào)：261194