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