資源描述:
《平衡超立方體限制邊連通性》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、學(xué)位論文版權(quán)使用授權(quán)書本學(xué)位論文作者完全了解北京交通大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定.特授權(quán)北京交通大學(xué)可以將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索,并采用影印、縮印或掃描等復(fù)制手段保存、匯編以供查閱和借閱.同意學(xué)校向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和磁盤.(保密的學(xué)位論文在解密后適用本授權(quán)說(shuō)明)學(xué)位論文作者簽名:薌飪影導(dǎo)師簽名:簽字日期:2形步∥月ff日新鍛簽字日期:叨盧年歹歸肜日中圖分類號(hào):0157.50152.1UDC:519.1學(xué)校代碼:10004密級(jí):公開北京交通大學(xué)碩士學(xué)位論文平衡超立方體的限制邊連通性Res
2、trictededge—connectivityofbalancedhypercubes作者姓名:張茹學(xué)號(hào):10121849導(dǎo)師姓名:郝榮霞職稱:教授學(xué)位類別:理學(xué)學(xué)位級(jí)別:碩士學(xué)科專業(yè):運(yùn)籌學(xué)與控制論研究方向:圖、網(wǎng)絡(luò)與組合優(yōu)化北京交通大學(xué)2012年6月致謝本文是在我的導(dǎo)師郝榮霞教授的親切關(guān)懷和悉心指導(dǎo)下完成的.無(wú)論是在科研上,還是在平時(shí)的生活中,郝榮霞老師都給了我無(wú)微不至的關(guān)懷與鼓勵(lì)。當(dāng)我在專業(yè)課學(xué)習(xí)中遇到困難時(shí),她總能從更高的角度看問題,并且以獨(dú)特的講解使我豁然開朗;當(dāng)我在科研上遇到困惑時(shí),郝榮霞老師給了我很多新的思路和方法
3、,使我受益腰淺.在此深深的感謝郝榮霞老師兩年來(lái)在各個(gè)方面對(duì)我的關(guān)心和幫助!衷心感謝馮衍全、何衛(wèi)力、周進(jìn)鑫老師.諸位老師嚴(yán)謹(jǐn)?shù)闹螌W(xué)態(tài)度穰科學(xué)的工作方法對(duì)我有極大的幫助和影響,是我學(xué)習(xí)的榜樣.在平時(shí)的理論學(xué)習(xí)遇到困難時(shí),老師們耐心指導(dǎo),為我指點(diǎn)迷津.衷心感謝修乃華教授、常彥勛教授等.感謝他們?cè)谧隹蒲屑罢撐淖珜懮纤岢龅膶氋F意見.衷心感謝研究生期間和我一起學(xué)習(xí)生活的同窗好友們,他們是:高西娜、尚怡潔、楊大偉、杜曉靜、吳志霞、張偉娟等,是他們的鼓勵(lì)和熱心幫助,讓我解決了很多問題,共同的學(xué)習(xí)生活使我收獲多多.衷心感謝我的父母對(duì)我的培育和對(duì)我
4、學(xué)業(yè)的默默支持.最后衷心感謝各位專家在百忙中審閱我的論文.我愿意認(rèn)真聽取專家的寶貴意見,使本文更加完善,并為今后的學(xué)習(xí)及科研工作打下基礎(chǔ).北京交通大學(xué)碩士學(xué)位論文中文摘要摘要:平衡超立方體是目前發(fā)現(xiàn)的非常重要的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).平衡超立方體的連通性成為重要的研究課題.設(shè)G是一個(gè)有限簡(jiǎn)單無(wú)向圖,如果圖G的每一個(gè)最小邊割都孤立一個(gè)頂點(diǎn),則稱圖G為超邊連通圖.設(shè)F∈E(G),如果G—F是不連通的并且G—F的每一個(gè)連通分支至少含有兩個(gè)點(diǎn),那么我們稱F為圖G的限{
5、i9性邊割.如果圖G的每一個(gè)最小限制性邊割孤立一條邊,即每一個(gè)最小限制性邊割是與
6、G中度數(shù)最小的邊相關(guān)聯(lián)的,我們稱這個(gè)圖G是超限制邊連通圖.一條路P如果經(jīng)過圖G的所有點(diǎn)一次,這條路P被稱為圖G的漢密爾頓路.如果P=(ul,V2,?,V。一1,V竹)是漢密爾頓路,那么P又記為(V1,‰).漢密爾頓路.本文主要研究平衡超立方體的超限制邊連通性和漢密爾頓容錯(cuò)連通性.第一章緒論部分.主要介紹本文所要用到的圖論和連通的基本概念,以及相關(guān)的背景知識(shí)和主要研究工作.第二章總結(jié)了平衡超立方體的定義和性質(zhì).在第一節(jié)中引入平衡超立方體的定義,然后第二節(jié)余紹了平衡超立方體的性質(zhì)和已有結(jié)論.第三章證明了平衡超立方體是最大邊連通圖,超邊
7、連通圖,最大限制邊連通圖.同時(shí)也根據(jù)Wang證明定理的方法,類似地證明了連通的點(diǎn)傳遞圖平衡超立方體滿足度k>2,圍長(zhǎng)g=4,是超限制邊連通圖.第四章對(duì)平衡超立方體的性質(zhì)特點(diǎn)進(jìn)一步分析,證明了在有n一1條錯(cuò)誤邊的平衡超立方體中,對(duì)任意相鄰的鼴個(gè)頂點(diǎn)%V,一定存在一個(gè)無(wú)錯(cuò)(“,u)一漢密爾頓路.同時(shí)也證明了在有佗一1條錯(cuò)誤邊的平衡超立方體中,一定存在一個(gè)無(wú)錯(cuò)漢密爾頓圈.關(guān)鍵詞:平衡超立方體;超限制邊連通;容錯(cuò)性分類號(hào):0157.5;0152.1.111北京交通大學(xué)碩士學(xué)位論文ABSTRACTABSTRACT:Thebalancedhy
8、percubeisaveryimportantnetworktopologystructure.、Theconnectivityofbalancedhypercubeisanimportantresearchtopic.LetGbeafinite,simpleandundirectedgraph.AgraphGissaidtobesuperedge—connected,ifeveryminimumedge-cutofGisolatesavertex,thatis,everyminimumedge-cutofGisasetofedg
9、esadjacenttoacertainvertexwithminimumvertex-degreeinG.F∈E(G),ifG—FdisconnectedandG—Feverycomponenthasatleasttwovertices,then