關(guān)于圖的彩虹（頂點）連通數(shù)若干問題的研究

《關(guān)于圖的彩虹（頂點）連通數(shù)若干問題的研究》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。

1、萬方數(shù)據(jù)中圖分類號：UDC：學校代碼：10055密級：公開高蕊犬浮博士學位論文關(guān)于圖的彩虹(頂點)連通數(shù)若干問題的研究SomeTopicsonRainbow(Vertex一)ConnectionNumbersofGraphs南開大學研究生院二。一四年四月萬方數(shù)據(jù)南開大學學位論文使用授權(quán)書根據(jù)《南開大學關(guān)于研究生學位論文收藏和利用管理辦法》，我校的博士、碩士學位獲得者均須向南開大學提交本人的學位論文紙質(zhì)本及相應電子版。本人完全了解南開大學有關(guān)研究生學位論文收藏和利用的管理規(guī)定。南開大學擁有在《著作權(quán)法》規(guī)定范圍內(nèi)的學位論文使用權(quán)，即

2、：(1)學位獲得者必須按規(guī)定提交學位論文(包括紙質(zhì)印刷本及電子版)，學校可以采用影印、縮印或其他復制手段保存研究生學位論文，并編入《南開大學博碩士學位論文全文數(shù)據(jù)庫》；(2)為教學和科研目的，學?？梢詫⒐_的學位論文作為資料在圖書館等場所提供校內(nèi)師生閱讀，在校園網(wǎng)上提供論文目錄檢索、文摘以及論文全文瀏覽、下載等免費信息服務；(3)根據(jù)教育部有關(guān)規(guī)定，南開大學向教育部指定單位提交公開的學位論文：(4)學位論文作者授權(quán)學校向中國科技信息研究所及其萬方數(shù)據(jù)電子出版社和中國學術(shù)期刊(光盤)電子出版社提交規(guī)定范圍的學位論文及其電子版并收入相

3、應學位論文數(shù)據(jù)庫，通過其相關(guān)網(wǎng)站對外進行信息服務。同時本人保留在其他媒體發(fā)表論文的權(quán)利。非公開學位論文，保密期限內(nèi)不向外提交和提供服務，解密后提交和服務同公開論文。論文電子版提交至校圖書館網(wǎng)站：http：#202．113．20．163：8001／paper／index．jsp。本人承諾：本人的學位論文是在南開大學學習期間創(chuàng)作完成的作品，并己通過論文答辯；提交的學位論文電子版與紙質(zhì)本論文的內(nèi)容一致，如因不同造成不良后果由本人自負。本人同意遵守上述規(guī)定。本授權(quán)書簽署一式兩份，由研究生院和圖書館留存。作者暨授權(quán)人簽字：陵麴麴2014年6

4、月6日南開大學研究生學位論文作者信息論文題目關(guān)于圖的彩虹(頂點)連通數(shù)若干問題的研究姓名陳莉莉?qū)W號1120090012答辯日期2014年5月25日論文類別博士一學歷碩士口碩士專業(yè)學位口高校教師口同等學力碩士口院／系／所組合數(shù)學中心專業(yè)應用數(shù)學聯(lián)系電話15222526920EmailLily60612@126．com通信地址(郵編)：南開大學組合數(shù)學中一11,(300071)備注：是否批準為非公開論文否注：本授權(quán)書適用我校授予的所有博士、碩士的學位論文。由作者填寫(一式兩份)簽字后交校圖書館，非公開學位論文須附《南開大學研究生申請非

5、公開學位論文審批表》。萬方數(shù)據(jù)南開大學學位論文原創(chuàng)性聲明f

6、UlIIIIIIllllIIIIIIIIIY2755426本人鄭重聲明：所呈交的學位論文，是本人在導師指導下進行研究工作所取得的研究成果。除文中已經(jīng)注明引用的內(nèi)容外，本學位論文的研究成果不包含任何他人創(chuàng)作的、已公開發(fā)表或者沒有公開發(fā)表的作品的內(nèi)容。對本論文所涉及的研究工作做出貢獻的其他個人和集體，均己在文中以明確方式標明。本學位論文原創(chuàng)性聲明的法律責任由本人承擔。學位論文作者簽名：隧麴蘊2014年6月6日非公開學位論文標注說明(本頁表中填寫內(nèi)容須打印)根據(jù)南開大學有關(guān)規(guī)定

7、，非公開學位論文須經(jīng)指導教師同意、作者本人申請和相關(guān)部門批準方能標注。未經(jīng)批準的均為公開學位論文，公開學位論文本說明為空白。論文題目申請密級口限制(≤2年)口秘密(≤lO年)口機密(≤20年)保密期限20年月日至20年月日審批表編號批準日期20年月日南開大學學位評定委員會辦公室蓋章(有效)注：限制★2年(可少于2年)：秘密★10年(可少于10年)：機密★20年(可少于20年)萬方數(shù)據(jù)摘要設(shè)圖G是一個具有邊染色的非平凡連通圖，其中相鄰邊可以染相同顏色。稱圖G的一條路是彩虹路，如果這條路上的任意兩條邊都染不同顏色。如果對圖G的任意兩個

8、頂點u和V，都存在一條彩虹路連接u和V，則稱圖G是彩虹連通的。使得圖G是彩虹連通的所需的最少顏色數(shù)稱為圖G的彩虹連通數(shù)，用rc(G1表示。彩虹連通數(shù)的概念是由Chartrand等人在2008年提出來的。它可以看成是連通度的加強，因為如果一個圖是彩虹連通的，那么它顯然是連通的。彩虹連通數(shù)概念的提出來源于政府機構(gòu)之間的信息傳遞。當我們在機構(gòu)之間傳遞信息時，為了安全，我們需要足夠多的密碼，使得任意兩個機構(gòu)之間都至少存在一條信息傳遞路，并且這條路上的每段被分配一個不同的密碼。另一方面，我們又希望所用的密碼盡可能的少。如果我們用圖來表示這個

9、信息傳遞網(wǎng)，用邊染色表示密碼，那么這個最少的密碼數(shù)就是我們所說的彩虹連通數(shù)。Krivelevich和Yuster接著提出了彩虹頂點連通數(shù)的概念。設(shè)圖G是一個具有頂點染色的非平凡連通圖。稱圖G的一條路是彩虹頂點連通路，如果這條路的內(nèi)部頂點都染不同顏色