特殊圖類的彩虹邊染色

《特殊圖類的彩虹邊染色》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

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

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

3、,McKeon和Zhang首次提出了圖的彩虹連通性的概念，這是對經(jīng)典連通性概念的一種加強(qiáng)。我們都知道，彩虹連通數(shù)是一個(gè)自然的組合概念，除了具有理論上的意義，更重要的是在網(wǎng)絡(luò)問題中有著很重要的應(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ú)特的頻道（比如說，分配不同波段的頻率）。顯然，我們想要網(wǎng)絡(luò)中所使用的不同的頻道的個(gè)數(shù)最少，而這個(gè)最少的個(gè)數(shù)

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

5、的圖稱為平凡圖，相反，若，那么這樣的圖就稱為非平凡圖。簡單圖就是既不含平行邊也不含自環(huán)的圖，所說的平行邊是指在無向圖中，如果和頂點(diǎn)和相關(guān)聯(lián)的無向邊多于一條，那么則稱這些邊為平行邊，平行邊的條數(shù)稱為重?cái)?shù)。而自環(huán)是指兩端連接著同一頂點(diǎn)的邊。前面有說到無向圖，簡單說就是不具有方向性的圖。定義在圖的邊的集合中，每個(gè)元素為一對頂點(diǎn)構(gòu)成的無序?qū)Γ硎卷旤c(diǎn)和相關(guān)聯(lián)的一條無向邊，若是無向圖，那么和表示的是同一條邊。有圖必然會有由產(chǎn)生而來的別的圖，這里只介紹子圖的概念。假設(shè)和是兩個(gè)圖，如果頂點(diǎn)集是的一個(gè)子集，邊集也是的子集，那么就稱圖是圖的一

6、個(gè)子圖。我們常常以圖的度作為研究圖的一個(gè)參考，一個(gè)頂點(diǎn)的度數(shù)是指與它相關(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ù)稱為路的長度，記，稱是一條和之間的路。另外，需要了解下研究圖的另一個(gè)參考量，連通度。一個(gè)圖是連通的，如果無向圖中的任意一對頂點(diǎn)都是連通的。頂點(diǎn)連

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

8、種顏色。如果圖中的一條路徑上的邊分別染不同的顏色，那么稱是圖一條彩虹路；如果圖任意兩個(gè)不同頂點(diǎn)和之間至少有一條彩虹路相連，則稱圖是彩虹連通的。在這種情況下，染色稱為圖的彩虹邊染色。如果使用了種顏色，那么稱是一個(gè)彩虹染色。如果是對圖進(jìn)行彩虹邊染色所需的最少顏色數(shù)，稱為圖的彩虹連通數(shù)，記作。顯