【正文】 一條彩虹路，比如說(shuō)，是一條彩虹路。假設(shè)，是圖的一個(gè)最小彩虹染色，并且說(shuō)明了。因此。假設(shè)，圖有一個(gè)彩虹染色，那么對(duì)于圖的相鄰的兩條邊可能染同種顏色，比如說(shuō)，邊和邊染相同的顏色。故圖的3邊染色是一個(gè)彩虹染色，從而。為了說(shuō)明上述的，我們考慮圖。連通圖的任意兩個(gè)頂點(diǎn)之間距離中的最大值，稱(chēng)為是圖的直徑，記作。顯然，彩虹連通圖一定是連通的，且將所有邊染不同顏色可以得到連通圖的一個(gè)彩虹染色。如果使用了種顏色，那么稱(chēng)是一個(gè)彩虹染色。如果圖中的一條路徑上的邊分別染不同的顏色，那么稱(chēng)是圖一條彩虹路；如果圖任意兩個(gè)不同頂點(diǎn)和之間至少有一條彩虹路相連，則稱(chēng)圖是彩虹連通的。認(rèn)識(shí)了圖的一些基本概念以后，我們來(lái)了解下本文研究的圖的彩虹連通數(shù)。邊連通度是指，使得圖是邊連通的最大整數(shù)，記作。連通度是指，使得圖是連通的最大整數(shù)，記作。相反，如果一個(gè)不連通的無(wú)向圖，稱(chēng)為非連通圖。一個(gè)圖是連通的，如果無(wú)向圖中的任意一對(duì)頂點(diǎn)都是連通的。一條路上的邊數(shù)稱(chēng)為路的長(zhǎng)度，記，稱(chēng)是一條和之間的路。圖是一條路，其頂點(diǎn)集和邊集分別為，這里的均互不相同。我們把圖中最小頂點(diǎn)度稱(chēng)為最小度，記作，把圖中最大頂點(diǎn)度稱(chēng)為最大度，記作。假設(shè)和是兩個(gè)圖，如果頂點(diǎn)集是的一個(gè)子集，邊集也是的子集，那么就稱(chēng)圖是圖的一個(gè)子圖。定義在圖的邊的集合中，每個(gè)元素為一對(duì)頂點(diǎn)構(gòu)成的無(wú)序?qū)?，表示頂點(diǎn)和相關(guān)聯(lián)的一條無(wú)向邊，若是無(wú)向圖，那么和表示的是同一條邊。而自環(huán)是指兩端連接著同一頂點(diǎn)的邊。另外，若圖只有一個(gè)頂點(diǎn)，即，那么這樣的圖稱(chēng)為平凡圖，相反，若，那么這樣的圖就稱(chēng)為非平凡圖。圖的階是指頂點(diǎn)的個(gè)數(shù)稱(chēng)，記作。圖的分類(lèi)眾多，本文所研究的圖均為有限的簡(jiǎn)單無(wú)向圖。其中，代表圖的頂點(diǎn)的集合，記作；代表圖的邊的集合，記作。在了解圖的彩虹連通數(shù)之前，我們先對(duì)用到的一些圖論基礎(chǔ)知識(shí)做一個(gè)簡(jiǎn)單的介紹。假設(shè)信息的傳輸是在一個(gè)蜂窩形狀的網(wǎng)絡(luò)中，而這個(gè)網(wǎng)絡(luò)中的任意兩個(gè)頂點(diǎn)之間都有一條路相連，并且這條路徑上的每一段路需要分配一個(gè)獨(dú)特的頻道（比如說(shuō)，分配不同波段的頻率）。我們都知道，彩虹連通數(shù)是一個(gè)自然的組合概念，除了具有理論上的意義，更重要的是在網(wǎng)絡(luò)問(wèn)題中有著很重要的應(yīng)用。同樣，圖的染色在許多領(lǐng)域都會(huì)涉及到將某種對(duì)象的集合按照一定的規(guī)則進(jìn)行分類(lèi)，比如說(shuō)，學(xué)生選課系統(tǒng)、電路布局、排序問(wèn)題、會(huì)議安排、電路安排、考試安排等，這些問(wèn)題都與圖的染色理論密切相關(guān)，專(zhuān)家學(xué)者對(duì)圖的不同染色問(wèn)題的研究，已經(jīng)有了較為豐富的結(jié)果，并且這些結(jié)果仍在進(jìn)一步完善中。而說(shuō)到圖的染色的實(shí)際應(yīng)用，我們得介紹下何謂染色。談到了圖論中的著名問(wèn)題，那就不得不提世界近代三大數(shù)學(xué)難題，同時(shí)對(duì)圖論發(fā)展產(chǎn)生了重大影響的——“四色猜想”，這使得圖論中的染色問(wèn)題成為了研究的熱點(diǎn)問(wèn)題，圖的染色問(wèn)題不但在理論上有著重要的意義而且在實(shí)際問(wèn)題中也有著重要的應(yīng)用。畢業(yè)論文特殊圖類(lèi)的彩虹邊染色1 前言我們都知道，圖論是源于一個(gè)著名的問(wèn)題——哥尼斯堡七橋問(wèn)題。后來(lái)英國(guó)的數(shù)學(xué)家漢密爾頓通過(guò)十二面體“繞行世界”的游戲，使得很多人開(kāi)始關(guān)注這個(gè)圖論中的另一個(gè)著名問(wèn)題，即漢密爾頓問(wèn)題。說(shuō)到實(shí)際應(yīng)用，對(duì)于圖論的許多公開(kāi)問(wèn)題，比如說(shuō)，企業(yè)生產(chǎn)管理，交通運(yùn)輸，計(jì)算機(jī)網(wǎng)絡(luò)，甚至軍事等眾多領(lǐng)域一直以來(lái)都有許多專(zhuān)家學(xué)者所研究。所謂的染色問(wèn)題，就是給定一個(gè)圖，需要把圖中的所有的頂點(diǎn)，或者所有的邊進(jìn)行染色，使得相鄰的頂點(diǎn)或者邊所染的顏色不同，其中優(yōu)秀的染色方法，就是盡量使得需要的顏色數(shù)最少。2008年，Chartrand, Johns, McKeon和Zhang首次提出了圖的彩虹連通性的概念，這是對(duì)經(jīng)典連通性概念的一種加強(qiáng)。事實(shí)上，政府機(jī)構(gòu)之間需要進(jìn)行一些機(jī)密信息的傳遞，這些傳輸要保證其安全性，于是便產(chǎn)生了彩虹連通的這些概念。顯然，我們想要網(wǎng)絡(luò)中所使用的不同的頻道的個(gè)數(shù)最少，而這個(gè)最少的個(gè)數(shù)就是這個(gè)蜂窩網(wǎng)絡(luò)所對(duì)應(yīng)的無(wú)向圖的彩虹連通數(shù)。首先，需要了解圖的定義，圖定義為一個(gè)二元組使得，記作?？梢钥闯觯吋械脑厥琼旤c(diǎn)集中元素的元子集，并且默認(rèn)和的交集為空集。圖分為有限的、無(wú)限的、可數(shù)的等等，是根據(jù)圖的階進(jìn)行分類(lèi)的。在本文中研究的圖，我們總是假定為有限的，階為的有限圖，即。簡(jiǎn)單圖就是既不含平行邊也不含自環(huán)的圖，所說(shuō)的平行邊是指在無(wú)向圖中，如果和頂點(diǎn)和相關(guān)聯(lián)的無(wú)向邊多于一條，那么則稱(chēng)這些邊為平行邊，平行邊的條數(shù)稱(chēng)為重?cái)?shù)。前面有說(shuō)到無(wú)向圖，簡(jiǎn)單說(shuō)就是不具有方向性的圖。有圖必然會(huì)有由產(chǎn)生而來(lái)的別的圖，這里只介紹子圖的概念。我們常常以圖的度作為研究圖的一個(gè)參考，一個(gè)頂點(diǎn)的度數(shù)是指與它相關(guān)聯(lián)的邊的數(shù)目，若頂點(diǎn)的度為，則稱(chēng)該頂點(diǎn)為孤立頂點(diǎn)，也就是不與其它任何頂點(diǎn)相連接的點(diǎn)。研究圖，必然需要知道什么是路。在此，頂點(diǎn)和由路連接，并稱(chēng)它們是路的端點(diǎn)，而稱(chēng)為的內(nèi)部頂點(diǎn)。另外，需要了解下研究圖的另一個(gè)參考量，連通度。頂點(diǎn)連通是指在無(wú)向圖中，若從頂點(diǎn)到有路相連，則稱(chēng)和是連通的。連通圖是指一個(gè)圖的任意兩個(gè)不同頂點(diǎn)之間都至少有條相互獨(dú)立的路相連。邊連通圖是指一個(gè)圖的任意兩個(gè)不同頂點(diǎn)之間至少有條相互獨(dú)立的路相連。其中，最簡(jiǎn)單的2連通圖是圈，并且其它的2連通圖都可以由一個(gè)圈通過(guò)不斷添加路而得到。假設(shè)圖是非平凡的連通的，定義一個(gè)邊染色 ，其中相鄰的邊可能染同種顏色。在這種情況下，染色稱(chēng)為圖的彩虹邊染色。如果是對(duì)圖進(jìn)行彩虹邊染色所需的最少顏色數(shù)，稱(chēng)為圖的彩虹連通數(shù)，記作。如果圖中的兩個(gè)頂點(diǎn)和之間有路相連，則稱(chēng)和之間所有路中最短路的長(zhǎng)度為和之間的距離，記為。如果圖是一個(gè)邊數(shù)為的非平凡連通圖，則有。圖給出了圖的一個(gè)3邊染色，可以驗(yàn)證圖中任意兩個(gè)不同頂點(diǎn)之間都有彩虹路相連。因?yàn)?，所以，圖的任何彩虹染色至少使用了兩種顏色，即。由于圖中任意兩個(gè)不相鄰頂點(diǎn)之間有且僅有一條長(zhǎng)度為2 的路，而和之間的2長(zhǎng)路不是一條彩虹路，故和之間沒(méi)有彩虹路相連，這與是圖是一個(gè)彩虹染色的假設(shè)相矛盾。圖 彩虹染色圖接下來(lái)，我們考慮另外一個(gè)例子，在這個(gè)例子中，圖是彩虹染色的。顯然，從圖中可以得到。進(jìn)一步假設(shè)。據(jù)此，我們可以這樣染色，即圖，這樣的染色假設(shè)不失一般性。情況2，那么。綜上所述，在假設(shè)下的邊染色中至少有兩個(gè)頂點(diǎn)之間不存在彩虹路，這與假設(shè)圖中至少有一條是彩虹路是矛盾的。圖 圖：通過(guò)這兩個(gè)例子，我們可以得出，如果圖是一個(gè)大小為的非平凡連通圖，則有：。對(duì)于彩虹連通數(shù)，定理給出了等人對(duì)于圖是完全圖，或是一棵樹(shù)，或是一個(gè)圈的彩虹連通數(shù)，這個(gè)定理對(duì)于本文研究的第一類(lèi)特殊圖，度數(shù)為的圖的彩虹染色有相應(yīng)地運(yùn)用。第1章 特殊圖類(lèi)的彩虹連通數(shù)在本文中所研究的圖均考慮是有限簡(jiǎn)單無(wú)向圖。補(bǔ)充說(shuō)明，一個(gè)圖是完全圖，那么圖中任意兩個(gè)頂點(diǎn)之間都有一條路相連接。再做一個(gè)圈連接的所有葉子頂點(diǎn)，即圈上的頂點(diǎn)是由的所有葉子頂點(diǎn)組成。根據(jù)定義，我們可以知道，圖是一個(gè)連通圖。但是，在文獻(xiàn)中，作者證明了對(duì)于任意的連通圖的彩虹連通數(shù)的上界，即。定義 定義一個(gè)特殊圖類(lèi)滿足以下條件的圖：（1）特征樹(shù)的每個(gè)內(nèi)部頂點(diǎn)（包括根結(jié)點(diǎn)）的度數(shù)均為；（2）伴隨圈的頂點(diǎn)（即的葉子頂點(diǎn)）與相關(guān)聯(lián)的上一層的結(jié)點(diǎn)構(gòu)成了三角形；（3）從根結(jié)點(diǎn)到每一個(gè)葉子頂點(diǎn)的層數(shù)是相同的?？梢詮膱D中看出