圖的彩虹連通數(shù)與距離

《圖的彩虹連通數(shù)與距離》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、中圖分類號(hào)：UDC-學(xué)校代碼：10055密級(jí)：公開薏越失法博士學(xué)位論文圖的彩虹連通數(shù)與距離RAINBOWCO．NNECTIONM瓜忸ERANDDISTANCEOFGRAPHS評(píng)閱人篋鍪明刻掛真閏掛墓韭獨(dú)壬毖勝貴南開大學(xué)研究生院二O一三年四月南開大學(xué)學(xué)位論文使用授權(quán)書根據(jù)《南開大學(xué)關(guān)于研究生學(xué)位論文收藏和利用管理辦法》，我校的博士、碩士學(xué)位獲得者均須向南開大學(xué)提交本人的學(xué)位論文紙質(zhì)本及相應(yīng)電子版。本人完全了解南開大學(xué)有關(guān)研究生學(xué)位論文收藏和利用的管理規(guī)定。南開大學(xué)擁有在《著作權(quán)法》規(guī)定范圍內(nèi)的學(xué)位論文使用權(quán)，即：(1)學(xué)位獲得者必須按規(guī)定提交學(xué)位論文(包括紙質(zhì)印刷本及電子版)，學(xué)校可以采

2、用影印、縮印或其他復(fù)制手段保存研究生學(xué)位論文，并編入《南開大學(xué)博碩士學(xué)位論文全文數(shù)據(jù)庫》；(2)為教學(xué)和科研目的，學(xué)?？梢詫⒐_的學(xué)位論文作為資料在圖書館等場所提供校內(nèi)師生閱讀，在校園網(wǎng)上提供論文目錄檢索、文摘以及論文全文瀏覽、下載等免費(fèi)信息服務(wù)；(3)根據(jù)教育部有關(guān)規(guī)定，南開大學(xué)向教育部指定單位提交公開的學(xué)位論文；(4)學(xué)位論文作者授權(quán)學(xué)校向中國科技信息研究所及其萬方數(shù)據(jù)電子出版社和中國學(xué)術(shù)期刊(光盤)電子出版社提交規(guī)定范圍的學(xué)位論文及其電子版并收入相應(yīng)學(xué)位論文數(shù)據(jù)庫，通過其相關(guān)網(wǎng)站對(duì)外進(jìn)行信息服務(wù)。同時(shí)本人保留在其他媒體發(fā)表論文的權(quán)利。非公開學(xué)位論文，保密期限內(nèi)不向外提交和提供服務(wù)

3、，解密后提交和服務(wù)同公開論文。論文電子版提交至校圖書館網(wǎng)站：h塹p；叢2Q2：!!三：2Q：l互3；墨鯉!』P亟籃叢nd叢jsP。本人承諾：本人的學(xué)位論文是在南開大學(xué)學(xué)習(xí)期間創(chuàng)作完成的作品，并已通過論文答辯；提交的學(xué)位論文電子版與紙質(zhì)本論文的內(nèi)容一致，如因不同造成不良后果由本人自負(fù)。本人同意遵守上述規(guī)定。本授權(quán)書簽署一式兩份，由研究生院和圖書館留存。作者暨授權(quán)人簽字：李恒哲2013年6月7日南開大學(xué)研究生學(xué)位論文作者信息論文題目圖的彩虹連通數(shù)與距離姓名李恒哲學(xué)號(hào)1120100010答辯日期2013年5月30日論文類別博士一學(xué)歷碩士口碩士專業(yè)學(xué)位口高校教師口同等學(xué)力碩士口院／系／所組合數(shù)

4、學(xué)中心專業(yè)應(yīng)用數(shù)學(xué)聯(lián)系電話13821190201Em蚰lhz2010@mail．nankai．edu．cn通信地址(郵編)：南開大學(xué)組合數(shù)學(xué)中，心(300071)·備注：是否批準(zhǔn)為非公開論文+否注：本授權(quán)書適用我校授予的所有博士、碩士的學(xué)位論文。由作者填寫(一式兩份)簽字后交校圖書館，非公開學(xué)位論文須附《南開大學(xué)研究生申請(qǐng)非公開學(xué)位論文審批表》。南開大學(xué)學(xué)位論文原創(chuàng)性聲明本人鄭重聲明：所呈交的學(xué)位論文，是本人在導(dǎo)師指導(dǎo)下進(jìn)行研究工作所取得的研究成果。除文中已經(jīng)注明引用的內(nèi)容外，本學(xué)位論文的研究成果不包含任何他人創(chuàng)作的、已公開發(fā)表或者沒有公開發(fā)表的作品的內(nèi)容。對(duì)本論文所涉及的研究工作做出

5、貢獻(xiàn)的其他個(gè)人和集體，均已在文中以明確方式標(biāo)明。本學(xué)位論文原創(chuàng)性聲明的法律責(zé)任由本人承擔(dān)。學(xué)位論文作者簽名：奎垣蜇2013年6月7日非公開學(xué)位論文標(biāo)注說明(本頁表中填寫內(nèi)容須打印)根據(jù)南開大學(xué)有關(guān)規(guī)定，非公開學(xué)位論文須經(jīng)指導(dǎo)教師同意、作者本人申請(qǐng)和相關(guān)部門批準(zhǔn)方能標(biāo)注。未經(jīng)批準(zhǔn)的均為公開學(xué)位論文，公開學(xué)位論文本說明為空白。論文題目申請(qǐng)密級(jí)口限制(≤2年)口秘密(≤10年)口機(jī)密(≤20年)保密期限20年月日至20年月日審批表編號(hào)批準(zhǔn)B期20年月日南開大學(xué)學(xué)位評(píng)定委員會(huì)辦公室蓋章(有效)注：限制★2年(可少于2年)：秘密★10年(可少于10年)：機(jī)密★20年(可少于20年)中文摘要一個(gè)交

6、互網(wǎng)絡(luò)通?？梢猿橄蟪梢粋€(gè)圖，其中點(diǎn)代表開關(guān)元件或交換器，邊代表通信鏈路。一方面，為了防止黑客入侵，人們?cè)诿總€(gè)鏈路上設(shè)置一個(gè)密碼。另一方面，為了便于管理，密碼的總數(shù)要求在滿足下面的條件下盡可能的少：任意兩個(gè)交換器可以通過一系列密碼不同的鏈路來交換信息。這個(gè)問題可以抽象成一個(gè)圖，并且通過彩虹連通數(shù)來研究。彩虹連通數(shù)是由Chartrand等人在2008弓I入的。一個(gè)圖G=(V，E)的尼．邊著色是一個(gè)映射c：E寸S，其中S是一個(gè)由k種顏色組成的集合，也就是說，把G的邊用k種顏色來著。通常k種顏色的集合我們?nèi)閧1，2，．．．，足)。圖G是一個(gè)邊著色圖，其中相鄰的邊可以著同一種顏色，如果一條路上

7、的任意兩條邊的顏色不同，那么這條路稱為彩虹路。圖G是一個(gè)足．邊著色圖。如果圖G的任意兩個(gè)頂點(diǎn)之間存在一條彩虹路，那么該著色稱為七．彩虹邊著色。如果一個(gè)圖G有一個(gè)足一彩虹邊著色，那么該圖是七一彩虹邊連通的。一個(gè)圖G的彩虹連通數(shù)rc(C)是最小的整數(shù)k使得圖G有一個(gè)k．彩虹邊著色。對(duì)于整數(shù)n和k，讓t(n，k)表示n個(gè)頂點(diǎn)七．彩虹連通圖的最小邊數(shù)。本論文共分七章。第一章，我們首先引入彩虹連通數(shù)的定義和研究背景。然后我們縱覽一下本文的主要結(jié)果。由于直