特殊圖類的彩虹邊染色畢業(yè)論文

《特殊圖類的彩虹邊染色畢業(yè)論文》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、1前言我們都知道，圖論是源于一個(gè)著名的問(wèn)題——哥尼斯堡七橋問(wèn)題。后來(lái)英國(guó)的數(shù)學(xué)家漢密爾頓通過(guò)十二面體“繞行世界”的游戲，使得很多人開始關(guān)注這個(gè)圖論中的另一個(gè)著名問(wèn)題，即漢密爾頓問(wèn)題。談到了圖論中的著名問(wèn)題，那就不得不提世界近代三大數(shù)學(xué)難題，同時(shí)對(duì)圖論發(fā)展產(chǎn)生了重大影響的——“四色猜想”，這使得圖論中的染色問(wèn)題成為了研究的熱點(diǎn)問(wèn)題，圖的染色問(wèn)題不但在理論上有著重要的意義而且在實(shí)際問(wèn)題中也有著重要的應(yīng)用。說(shuō)到實(shí)際應(yīng)用，對(duì)于圖論的許多公開問(wèn)題，比如說(shuō)，企業(yè)生產(chǎn)管理，交通運(yùn)輸，計(jì)算機(jī)網(wǎng)絡(luò)，甚至軍事等眾多領(lǐng)域一直以來(lái)都有許多專家學(xué)者所研究。而說(shuō)到圖

2、的染色的實(shí)際應(yīng)用，我們得介紹下何謂染色。所謂的染色問(wèn)題，就是給定一個(gè)圖，需要把圖中的所有的頂點(diǎn)，或者所有的邊進(jìn)行染色，使得相鄰的頂點(diǎn)或者邊所染的顏色不同，其中優(yōu)秀的染色方法，就是盡量使得需要的顏色數(shù)最少。同樣，圖的染色在許多領(lǐng)域都會(huì)涉及到將某種對(duì)象的集合按照一定的規(guī)則進(jìn)行分類，比如說(shuō)，學(xué)生選課系統(tǒng)、電路布局、排序問(wèn)題、會(huì)議安排、電路安排、考試安排等，這些問(wèn)題都與圖的染色理論密切相關(guān)，專家學(xué)者對(duì)圖的不同染色問(wèn)題的研究，已經(jīng)有了較為豐富的結(jié)果，并且這些結(jié)果仍在進(jìn)一步完善中。2008年，Chartrand,Johns,McKeon和Zhang首

3、次提出了圖的彩虹連通性的概念，這是對(duì)經(jīng)典連通性概念的一種加強(qiáng)。我們都知道，彩虹連通數(shù)是一個(gè)自然的組合概念，除了具有理論上的意義，更重要的是在網(wǎng)絡(luò)問(wèn)題中有著很重要的應(yīng)用。事實(shí)上，政府機(jī)構(gòu)之間需要進(jìn)行一些機(jī)密信息的傳遞，這些傳輸要保證其安全性，于是便產(chǎn)生了彩虹連通的這些概念。假設(shè)信息的傳輸是在一個(gè)蜂窩形狀的網(wǎng)絡(luò)中，而這個(gè)網(wǎng)絡(luò)中的任意兩個(gè)頂點(diǎn)之間都有一條路相連，并且這條路徑上的每一段路需要分配一個(gè)獨(dú)特的頻道（比如說(shuō)，分配不同波段的頻率）。顯然，我們想要網(wǎng)絡(luò)中所使用的不同的頻道的個(gè)數(shù)最少，而這個(gè)最少的個(gè)數(shù)就是這個(gè)蜂窩網(wǎng)絡(luò)所對(duì)應(yīng)的無(wú)向圖的彩虹連通數(shù)

4、。在了解圖的彩虹連通數(shù)之前，我們先對(duì)用到的一些圖論基礎(chǔ)知識(shí)做一個(gè)簡(jiǎn)單的介紹。首先，需要了解圖的定義，圖定義為一個(gè)二元組使得，記作。其中，代表圖的頂點(diǎn)的集合，記作；代表圖的邊的集合，記作?？梢钥闯?，邊集中的元素是頂點(diǎn)集中元素的元子集，并且默認(rèn)和的交集為空集。圖的分類眾多，本文所研究的圖均為有限的簡(jiǎn)單無(wú)向圖。圖分為有限的、無(wú)限的、可數(shù)的等等，是根據(jù)圖的階進(jìn)行分類的。圖的階是指頂點(diǎn)的個(gè)數(shù)稱，記作。在本文中研究的圖，我們總是假定為有限的，階為的有限圖，即。另外，若圖只有一個(gè)頂點(diǎn)，即，那么這樣的圖稱為平凡圖，相反，若，那么這樣的圖就稱為非平凡圖。簡(jiǎn)

5、單圖就是既不含平行邊也不含自環(huán)的圖，所說(shuō)的平行邊是指在無(wú)向圖中，如果和頂點(diǎn)和相關(guān)聯(lián)的無(wú)向邊多于一條，那么則稱這些邊為平行邊，平行邊的條數(shù)稱為重?cái)?shù)。而自環(huán)是指兩端連接著同一頂點(diǎn)的邊。前面有說(shuō)到無(wú)向圖，簡(jiǎn)單說(shuō)就是不具有方向性的圖。定義在圖的邊的集合中，每個(gè)元素為一對(duì)頂點(diǎn)構(gòu)成的無(wú)序?qū)?，表示頂點(diǎn)和相關(guān)聯(lián)的一條無(wú)向邊，若是無(wú)向圖，那么和表示的是同一條邊。有圖必然會(huì)有由產(chǎn)生而來(lái)的別的圖，這里只介紹子圖的概念。假設(shè)和是兩個(gè)圖，如果頂點(diǎn)集是的一個(gè)子集，邊集也是的子集，那么就稱圖是圖的一個(gè)子圖。我們常常以圖的度作為研究圖的一個(gè)參考，一個(gè)頂點(diǎn)的度數(shù)是指與它相

6、關(guān)聯(lián)的邊的數(shù)目，若頂點(diǎn)的度為，則稱該頂點(diǎn)為孤立頂點(diǎn)，也就是不與其它任何頂點(diǎn)相連接的點(diǎn)。我們把圖中最小頂點(diǎn)度稱為最小度，記作，把圖中最大頂點(diǎn)度稱為最大度，記作。研究圖，必然需要知道什么是路。圖是一條路，其頂點(diǎn)集和邊集分別為，，這里的均互不相同。在此，頂點(diǎn)和由路連接，并稱它們是路的端點(diǎn)，而稱為的內(nèi)部頂點(diǎn)。一條路上的邊數(shù)稱為路的長(zhǎng)度，記，稱是一條和之間的路。另外，需要了解下研究圖的另一個(gè)參考量，連通度。一個(gè)圖是連通的，如果無(wú)向圖中的任意一對(duì)頂點(diǎn)都是連通的。頂點(diǎn)連通是指在無(wú)向圖中，若從頂點(diǎn)到有路相連，則稱和是連通的。相反，如果一個(gè)不連通的無(wú)向圖，

7、稱為非連通圖。連通圖是指一個(gè)圖的任意兩個(gè)不同頂點(diǎn)之間都至少有條相互獨(dú)立的路相連。連通度是指，使得圖是連通的最大整數(shù)，記作。邊連通圖是指一個(gè)圖的任意兩個(gè)不同頂點(diǎn)之間至少有條相互獨(dú)立的路相連。邊連通度是指，使得圖是邊連通的最大整數(shù)，記作。其中，最簡(jiǎn)單的2-連通圖是圈，并且其它的2-連通圖都可以由一個(gè)圈通過(guò)不斷添加路而得到。認(rèn)識(shí)了圖的一些基本概念以后，我們來(lái)了解下本文研究的圖的彩虹連通數(shù)。假設(shè)圖是非平凡的連通的，定義一個(gè)邊染色，其中相鄰的邊可能染同種顏色。如果圖中的一條路徑上的邊分別染不同的顏色，那么稱是圖一條彩虹路；如果圖任意兩個(gè)不同頂點(diǎn)和之

8、間至少有一條彩虹路相連，則稱圖是彩虹連通的。在這種情況下，染色稱為圖的彩虹邊染色。如果使用了種顏色，那么稱是一個(gè)彩虹染色。如果是對(duì)圖進(jìn)行彩虹邊染色所需的最少顏色數(shù)，稱為圖的彩虹連通數(shù)，記作。顯