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

《特殊圖類的彩虹邊染色畢業(yè)論文》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。

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

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

3、概念，這是對經典連通性概念的一種加強。我們都知道，彩虹連通數是一個自然的組合概念，除了具有理論上的意義，更重要的是在網絡問題中有著很重要的應用。事實上，政府機構之間需要進行一些機密信息的傳遞，這些傳輸要保證其安全性，于是便產生了彩虹連通的這些概念。假設信息的傳輸是在一個蜂窩形狀的網絡中，而這個網絡中的任意兩個頂點之間都有一條路相連，并且這條路徑上的每一段路需要分配一個獨特的頻道（比如說，分配不同波段的頻率）。顯然，我們想要網絡中所使用的不同的頻道的個數最少，而這個最少的個數就是這個蜂窩網絡所對應的無向圖的彩虹連通數。在了解圖的彩虹連通數之前，我們先對

4、用到的一些圖論基礎知識做一個簡單的介紹。首先，需要了解圖的定義，圖定義為一個二元組使得，記作。其中，代表圖的頂點的集合，記作；代表圖的邊的集合，記作?？梢钥闯?，邊集中的元素是頂點集中元素的元子集，并且默認和的交集為空集。圖的分類眾多，本文所研究的圖均為有限的簡單無向圖。XXIX圖分為有限的、無限的、可數的等等，是根據圖的階進行分類的。圖的階是指頂點的個數稱，記作。在本文中研究的圖，我們總是假定為有限的，階為的有限圖，即。另外，若圖只有一個頂點，即，那么這樣的圖稱為平凡圖，相反，若，那么這樣的圖就稱為非平凡圖。簡單圖就是既不含平行邊也不含自環(huán)的圖，所說

5、的平行邊是指在無向圖中，如果和頂點和相關聯(lián)的無向邊多于一條，那么則稱這些邊為平行邊，平行邊的條數稱為重數。而自環(huán)是指兩端連接著同一頂點的邊。前面有說到無向圖，簡單說就是不具有方向性的圖。定義在圖的邊的集合中，每個元素為一對頂點構成的無序對，表示頂點和相關聯(lián)的一條無向邊，若是無向圖，那么和表示的是同一條邊。有圖必然會有由產生而來的別的圖，這里只介紹子圖的概念。假設和是兩個圖，如果頂點集是的一個子集，邊集也是的子集，那么就稱圖是圖的一個子圖。我們常常以圖的度作為研究圖的一個參考，一個頂點的度數是指與它相關聯(lián)的邊的數目，若頂點的度為，則稱該頂點為孤立頂點，

6、也就是不與其它任何頂點相連接的點。我們把圖中最小頂點度稱為最小度，記作，把圖中最大頂點度稱為最大度，記作。研究圖，必然需要知道什么是路。圖是一條路，其頂點集和邊集分別為，，這里的均互不相同。在此，頂點和由路連接，并稱它們是路的端點，而稱為的內部頂點。一條路上的邊數稱為路的長度，記，稱是一條和之間的路。另外，需要了解下研究圖的另一個參考量，連通度。一個圖是連通的，如果無向圖中的任意一對頂點都是連通的。頂點連通是指在無向圖中，若從頂點到有路相連，則稱和是連通的。相反，如果一個不連通的無向圖，稱為非連通圖。連通圖是指一個圖的任意兩個不同頂點之間都至少有條相

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

8、的彩虹邊染色。如果使用了種顏色，那么稱是一個彩虹染色。如果是對圖進行彩虹邊染色所需的最少顏色數，稱為圖的彩虹