關(guān)于特殊圖的彩虹連通數(shù)的研究

《關(guān)于特殊圖的彩虹連通數(shù)的研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、萬(wàn)方數(shù)據(jù)分類號(hào)UDC密級(jí)單位代碼!Q151大連海事大學(xué)碩士學(xué)位論文關(guān)于特殊圖的彩虹連通數(shù)的研究劉怡筱指導(dǎo)教帥王．芯平職稱教授學(xué)位授予單位大連海事大學(xué)申請(qǐng)學(xué)位類別理學(xué)碩士學(xué)科(專業(yè))數(shù)學(xué)論文完成口期2015年12月答辯日期2016年3月答辯委員會(huì)’卜席萬(wàn)方數(shù)據(jù)TheRainbowconnectionofthespecialgraphAthesisSubmittedtoDalianMaritimeUniversityIIlllIlllIllllIIlY2999096InpartialfulfillmentoftherequirementsforthedegreeofMas

2、terofSciencebyLiuYixiao(AppliedMathematics)ThesisSupervisor：ProfessorWangZhipingMarch2016萬(wàn)方數(shù)據(jù)大連海事大學(xué)學(xué)位論文原創(chuàng)性聲明和使用授權(quán)說(shuō)明原創(chuàng)性聲明本人鄭重聲明：本論文是在導(dǎo)師的指導(dǎo)下，獨(dú)立進(jìn)行研究工作所取得的成果，撰寫成博／碩士學(xué)位論文：：苤王掛鐾圖的受塹連通數(shù)的盟塞：：。除論文中已經(jīng)注明引用的內(nèi)容外，對(duì)論文的研究做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。本論文中不包含任何未加明確注明的其他個(gè)人或集體己經(jīng)公開發(fā)表或未公開發(fā)表的成果。本聲明的法律責(zé)任由本人承擔(dān)。學(xué)位論

3、文作者簽名：烈性救學(xué)位論文版權(quán)使用授權(quán)書本學(xué)位論文作者及指導(dǎo)教師完全了解大連海事大學(xué)有關(guān)保留、使用研究生學(xué)位論文的規(guī)定，即：大連海事大學(xué)有權(quán)保留并向國(guó)家有關(guān)部門或機(jī)構(gòu)送交學(xué)位論文的復(fù)印件和電子版，允許論文被查閱和借閱。本人授權(quán)大連海事大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索，也可采用影印、縮印或掃描等復(fù)制手段保存和匯編學(xué)位論文。同意將本學(xué)位論文收錄到《中國(guó)優(yōu)秀博碩士學(xué)位論文全文數(shù)據(jù)庫(kù)》(中國(guó)學(xué)術(shù)期刊(光盤版)電子雜志社)、《中國(guó)學(xué)位論文全文數(shù)據(jù)庫(kù)》(中國(guó)科學(xué)技術(shù)信息研究所)等數(shù)據(jù)庫(kù)中，并以電子出版物形式出版發(fā)行和提供信息服務(wù)。保密的論文在解密后遵守此

4、規(guī)定。本學(xué)位論文屬于：保密口在年解密后適用本授權(quán)書。不保密口(請(qǐng)?jiān)谝陨戏娇騼?nèi)打“4”)論文作者簽名：劉胳懾導(dǎo)師簽名：日期：汐形年弓月，9日萬(wàn)方數(shù)據(jù)中文摘要摘要著名的格尼斯堡七橋問題是圖論問題的起源，隨后圖論便成為應(yīng)用數(shù)學(xué)研究中的一個(gè)重要分支。特殊圖的染色問題一直是圖論研究領(lǐng)域的熱門問題，它不但具有理論價(jià)值，更具有重要的現(xiàn)實(shí)意義。連通性是圖論中最重要的性質(zhì)之一，基于這些方面，一種加強(qiáng)版的連通性概念——圖的彩虹連通性的問題應(yīng)運(yùn)而生。在2008年，Chartrand、Johnson等人最先把這個(gè)概念引入到文獻(xiàn)中。在過去的幾年里，圖的彩虹連通數(shù)一直作為圖論中的熱門問題受到眾多

5、數(shù)學(xué)專家的廣泛關(guān)注，同時(shí)也被應(yīng)用到網(wǎng)絡(luò)信息安全、密碼學(xué)等領(lǐng)域。如果G是一個(gè)非平凡連通圖，對(duì)G的邊全部染上顏色。若用數(shù)字表示顏色，則c：E(G)_÷(1，2，?．kk∈J『＼『)即G為的一種著色方式。當(dāng)經(jīng)過圖G中的一條路P上的邊都被染成不同顏色時(shí)，則稱路P為圖G的一條彩虹路。如果對(duì)于連通圖G來(lái)說(shuō)，任意兩點(diǎn)間都存在一條彩虹路，則稱圖G是彩虹連通的。稱使得圖G為彩虹路連通的所使用的最少顏色數(shù)k為圖G的彩虹連通數(shù)，記為rc(G)。其后，Krivelevich和Yuster提出了彩虹頂點(diǎn)連通的概念。顯然這是對(duì)圖形的頂點(diǎn)進(jìn)行染色。一個(gè)連通圖的任意兩個(gè)頂點(diǎn)之間至少存在一條內(nèi)部頂點(diǎn)染

6、成不同顏色的路相連，則稱該圖是彩虹頂點(diǎn)連通的。類比圖的彩虹連通數(shù)的概念可知，彩虹頂點(diǎn)連通數(shù)就是使得連通圖G彩虹頂點(diǎn)連通的所必須的起碼的顏色數(shù)，記為rvc(G)。本文研究了一些特殊圖的彩虹連通性的問題，主要結(jié)果如下：(1)介紹了彩虹連通性問題的基本概念和己有的結(jié)論。(2)利用數(shù)學(xué)歸納法、分類討論思想，計(jì)算出了完全圖刺圖、圈的刺圖、風(fēng)車圖的彩虹連通數(shù)及強(qiáng)彩虹連通數(shù)。(3)運(yùn)用數(shù)學(xué)歸納法和分類討論的的數(shù)學(xué)思想，將原有圖進(jìn)行推廣，對(duì)一些日暈圖的彩虹連通數(shù)問題進(jìn)行了研究。(4)對(duì)3．連通圖的彩虹頂點(diǎn)連通數(shù)進(jìn)行了求解。關(guān)鍵詞：特殊圖；彩虹連通數(shù)；彩虹頂點(diǎn)連通數(shù)萬(wàn)方數(shù)據(jù)英文摘要AB

7、STRACTAstheoriginofthegraphtheory，thefamousKonigsbergBridgeProblem，promotesthedevelopmentofthegraphtheory．Thecoloringofagraphhasalwaysbeenahotissueinthefieldofgraphtheoryresearch．Itnotonlyhastheoreticalvalue，butalsohastheimportantpracticalsignificance．Moreover，theconnectivityis