【正文】 ， }8,2,1{, ??ji 且ji? ，于是決定將此條路染色成彩虹路，因此邊分別染 色，色，色， 821 ??vK i ，8,2,1 ??i ，這樣的染色方法確保了 8 個內(nèi)部頂點(diǎn)之間的最短路徑 ji KvK ?? 是一條彩虹路。 考慮新輪圖 knW? ， 一個 n 階的圈 1121 , vvvvvC nnn ?? ?? ，還有 k 個頂點(diǎn)kuuu ?, 21 連接圈 nC 的每個頂點(diǎn)，且這 k 個頂點(diǎn)之間沒有邊直接相連，這樣構(gòu)成的圖就是新輪圖 knW? 。類似的， 1)( 1 ??vvc n XVI 使得 2)( 2 ?vvc ?，F(xiàn)在，做一個相反的假設(shè)， 2)( ?nWrc ，同樣定義輪圖 nW 的一個彩虹 ?2 染色 c? ，并假設(shè) 1)( 1 ?? vvc 。定義一個 ?3 邊染色 }3,2,1{)(: ?nWEc 如下：如果 i 是奇數(shù)，則 1)( ?vvc i ；如果 i 是偶數(shù)，則 2)( ?vvc i ；對于每個 )( nCEe? ，有 3)( ?ec 。 再考慮，當(dāng) 64 ??n 時，輪圖 nW 不再是一個完全圖，于是 2)( ?nWrc 。 在推導(dǎo)新輪圖 knW? 的彩虹連通數(shù)之前，讓我們先來看看輪圖 nW 的彩虹連通數(shù)，參考了文獻(xiàn) ]7[ 。 輪圖 nW 是一個有 1個內(nèi)部頂點(diǎn) 1K ， n 個葉子頂點(diǎn)，且被一個圈連接的圖，根據(jù) Halin 圖的定義，可知輪圖 nW 是一個特殊的 Halin 圖，最小度 3?? 。做一個簡單的 計(jì)算，可以得到： 5 329)(423)( 2 ??????? ? xkx GrcGrc ，當(dāng) Nkk ?? ,3 時。 綜上所述，很容易推出： 5 )1(3)( ?? nGrc 。于是，我們有： 515 )1(32 151532 1)()( ??????????? ??????????? ????? tshtshtsHrcHrc 這就和 H 的極大性矛盾了。如果 ts? 是奇數(shù)，那么我們可以使路徑 bvvxvuuau ts ?? 2121的 2??ts 條邊染色，需要 2 1??ts 種新顏色。我們可以把頂點(diǎn) ts uuuxvvv ?? , 2121 加入 H 中，從而構(gòu)成一個更大的子圖 H? ，它有 1??? tsh 個頂點(diǎn)。而且，其中的所有頂點(diǎn)都滿足上述的屬性，我們選擇頂點(diǎn) x 使得三條路徑的其中一條長度為 1，比如說 00 eP? ，而使路徑 1P 和 2P 的長度之和盡可能大。我們可以把這四個頂點(diǎn) 4321 , xxxx加入圖 H 中，從而形成一個更大的子圖 H? ，它有 4?h 個頂點(diǎn)。如果，kC )5,4( ?? kk 是圖 G 的一個子圖，令 kCH? ，那 么 51532)( ????????? kkCrc k 。接下來，我們將對連通度為 3)( ?Gk 的彩虹連通數(shù)343)( ?? nGrc 的上界做出改善，即 5 )1(3)( ?? nGrc 。然后， Chandran 等人認(rèn)為這樣的結(jié)果并不令人滿意，于是改善了 hKrivelevic 和 Yuster 的關(guān)于彩虹連通數(shù))(Grc 的上界，即 313)( ??? ? nGrc ，并且證明了對于所有階數(shù)為 n ，最小度為 ? 的連通圖 G 都是適用的。但是，利用這個上界驗(yàn)證之前，在它的基礎(chǔ)上對于這個上界做了一些改善，使得更為緊一些，即 5 )1(3)( ?? nGrc ，再以改善后的這個上界來驗(yàn)證本文的結(jié)論?；蛟S，還存在比本文更優(yōu)的一種染色方法，使得最后得到更優(yōu)的彩虹連通數(shù)，由于知識水平有限，本文就不會進(jìn)一步研究了。因此，無論哪種情況，此種染色方法得到的 Halin 圖都能滿足，圖 xG 中任意兩個頂點(diǎn)之間至少有一條彩虹路相連。情況 1：圖 xG 中任取的兩個頂點(diǎn)恰巧位于同一個子圖 iH 中， 3230 ???? ki 。將所有這樣的子圖用上述的方法進(jìn)行染色，共使用七種顏色，而伴隨圈nC 上未染色的邊可選取 }7,6,5,4,3,2,1{ 中的任意一種顏色對其進(jìn)行染色。 層數(shù)為 1的 Halin 圖正如圖 所示，顯然，這是一個完全圖，因此，彩虹連通數(shù)為 1)( 1 ?Hrc 。此時，伴隨圈 nC 上還有一些邊未染色，我們選取}7,6,5,4,3,2,1{ 中的任意一種顏色對其進(jìn)行染色，比如說，我們選取了顏色 1對這些邊進(jìn)行染色。比如，所示的圖 3 ，這是一個 4 層的 Halin 圖 4G ，含有 nC 與相連的結(jié)點(diǎn)構(gòu)成的七個頂點(diǎn)的子圖，即 543210 , HHHHHH 。對一個度為 3 ，有 k 層的 Halin 圖 G ，記第 i（ ki??1 ）層為 iG ， ki??1 ，其總的頂點(diǎn)數(shù)為 223 ??? kn 。 第一節(jié) 度數(shù)為 3 的 Halin 圖的彩虹連通數(shù) 上面已經(jīng)給出了 Halin 圖的定義，我們要研究是頂點(diǎn)度數(shù)為 3 的一類特殊Halin 圖。這樣得到的圖被稱作 Halin 圖，樹 T 叫做特征樹，圈 nC叫做伴隨圈。 定理 .1 令 G 是大?。旤c(diǎn)數(shù)）為 n 的非平凡連通圖，即圖 G 的階為 n ，則有： ).1( 1)( ??nGrc ； ).2( 1)( ?Grc ， G 是完全圖； ).3( 1)( ??nGrc ， G 是一棵樹； ).4( ? ?2)( nCrc n ? ， G 是頂點(diǎn)數(shù) 4?n 的圈 nC 。 通過上述的例子，我們已經(jīng)初步了解到圖的彩虹染色，彩虹連通數(shù)等概念，本文針對三類特殊的圖進(jìn)行彩虹染色，并且給出了彩虹連通數(shù)的一個上界。又得考慮，如果 1)( 22 ?? vuc ， 2)( 33 ?? vuc ，那么在這種染色下，圖 G 中沒有彩虹 32 vu? 路；如果 3)( 22 ?? vuc ， 2)( 33 ?? vuc ，那么在這種染色下，圖 G 中沒有彩虹 12 vu? 路。 接下來，考慮其它邊的染色，首先，如果 x 和 y 是圖 G 的任意兩個頂點(diǎn)，并且 2),( ?yxd ，那么在圖 G 中僅有一條長度為 2 的 yx? 路，而其它所有的 yx? 路的長度是 4 或者更大，因此，這就說明在圖 G 中沒有兩條相鄰的邊染色是相同的。假設(shè)， c 是圖 G 的一個最小彩虹染色，并且說明了 4)( ?Grc 。假設(shè)，圖 P 有一個彩虹 ?2 染色 c ，那么對于圖 P 的相鄰的兩條邊可能染同種顏色，比如說，邊uwe? 和邊 wvf? 染相同的顏色。 為了說明上述的 )1( ，我們考慮 Petersen 圖 P 。顯然，彩虹連通圖一定是連通的，且將所有邊染不同顏色可以得到連通圖的一個彩虹染色。如果圖 G 中的一條路徑 P 上的邊分別染不同的顏色，那么稱 P 是圖 G 一條彩虹路； 如果圖 G 任意兩個不同頂點(diǎn) u 和 v 之間至少有一條彩虹路相連，則稱圖 G 是彩虹連通的。 IV 邊連通度是指，使得圖 G 是 ?l 邊連通的最大整數(shù) l ，記作 )(G? 。相反，如果一個不連通的無向圖，稱為非連通圖。一條路上的邊數(shù)稱為路的長度，記 kxxxP ?10? ，稱 P 是一條 0x 和 kx 之間的路。我們把圖 G 中最小頂點(diǎn)度稱為最小度，記作 )(G? ，把圖 G 中最大頂點(diǎn)度稱為最大度，記作 )(G? 。定義在圖 G 的邊的集合中，每個元素 ),( vu 為一對頂點(diǎn)構(gòu)成的無序?qū)?，表示頂點(diǎn) u 和 v 相關(guān)聯(lián)的一條無向邊，若是無向圖，那么 ),( vu 和 ),( uv 表示的是同一條邊。另外，若圖 只有一個頂點(diǎn)，即 1?n ，那么這樣的圖稱為平凡圖，相反，若 1?n ，那么這樣的圖就稱為非平凡圖。 圖的分類眾多，本文所研究的圖均為有限的簡單無向圖。 在了解圖的彩虹連通數(shù)之前，我們先對用到的一些圖論基礎(chǔ)知識做一個簡單的介紹。我們都知道，彩虹連通數(shù)是一個自然的組合概念，除了具有理論上的意義，更重要的是在網(wǎng)絡(luò)問題中有著很重要的應(yīng)用。而說到圖的染色的實(shí)際應(yīng)用，我們得介紹下何謂染色。 I 畢業(yè)論文 特殊圖類的彩虹邊染色 II 1 前言 我們都知道，圖論是源于一個著名的問題 —— 哥尼斯堡七橋問題。說到實(shí)際應(yīng)用，對于圖論的許多公開問題，比如說，企業(yè)生產(chǎn)管理， 交通運(yùn)輸，計(jì)算機(jī)網(wǎng)絡(luò)，甚至軍事等眾多領(lǐng)域一直以來都有許多專家學(xué)者所研究。 2020 年， Chartrand, Johns, McKeon 和 Zhang 首次提出了圖的彩虹連通性的概念，這是對經(jīng)典連通性概念的一種加強(qiáng)。顯然，我們想要網(wǎng)絡(luò)中所使用的不同的頻道的個數(shù)最少，而這個最少的個數(shù)就是這個蜂窩網(wǎng)絡(luò)所對應(yīng)的無向圖的彩虹連通數(shù)?？梢钥闯觯吋?E 中的元素是頂點(diǎn)集 V 中元素的 ?2 元子集，并且默認(rèn) V 和 E 的交集為空集。在本文中研究的圖，我們總是假定為有限的，階為 n的有限圖，即 Gn? 。 前面有說到無向圖，簡單說就是不具有方向性的圖。 我們常常以圖的度作為研究圖的一個參考，一個頂點(diǎn) u 的度數(shù)是指與它相關(guān)聯(lián)的邊的數(shù)目，若頂點(diǎn)的度為 0 ，則稱該頂點(diǎn)為孤立頂點(diǎn)，也就是不與其它任何頂點(diǎn)相連 接的點(diǎn)。在此，頂點(diǎn) 0x 和 kx 由路 P 連接，并稱它們是路的端點(diǎn)，而 11 , ?kxx ? 稱為 P 的內(nèi)部頂點(diǎn)。頂點(diǎn)連通是指在無向圖 G 中，若從頂點(diǎn) u 到 v 有路相連，則稱 u 和 v 是連通的。 ?l 邊連通圖 G 是指一個圖 G 的任意兩個不同頂點(diǎn)之間至少有 l 條相互獨(dú)立的路相連。 假設(shè)圖 G 是非平凡的連通的，定義一個邊染色 },2,1{)(: kGEc ?? Nk? ，其中相鄰的邊可能染同種顏色。如果 k 是對圖 G進(jìn)行彩虹 ?k 邊染色所需的最少顏色數(shù)， 稱為圖 G 的彩虹連通數(shù)，記作 )(Grc 。如果圖 G 是一個邊數(shù)為 m 的 非平凡連通圖，則有 mGrcGdi am ?? )()( )1( 。因?yàn)?2)(diam ?G ，所以，圖 P 的任何彩虹染色至少使用了兩種顏色，即 2)( ?Prc 。 V 圖 1 彩虹 ?3 染色 Petersen 圖 P 接下來，我們考慮另外一個例子，在這個例子中，圖 G 是彩虹 ?4 染色的。進(jìn)一步假設(shè)， 1)( 1 ??uuc ， 2)( 11 ?? vuc ， 3)( 1 ?? vvc 。情況 2， 2)( 2 ?? vvc ， 1)( 3 ??vvc ，那么 }3,1{)( 22 ?? vuc ， 2)( 33 ?? vuc 。 圖 2 圖 G ： 4)( ?Grc 通過這兩個例子，我們可以得出， 如果圖 G 是一個大小為 m 的非平凡連通圖，則有： mGrcGdi am ?? )()( 。 VII 第一章 特殊圖類的彩虹連通數(shù) 在本文中所研究的圖均考慮是 有限簡單無向圖。再做一個圈 nC 連接 T 的所有葉子頂點(diǎn)，即圈 nC 上的頂點(diǎn)是由 T 的所有葉子頂點(diǎn)組成。但是，在文獻(xiàn) ]12[ 中，作者證明了對于任意的 ?3 連通圖的彩虹連通數(shù)的上界，即 5 )1(3)( ?? nGrc ?？梢詮膱D中看出，第一層有 3 個頂點(diǎn)，第二層有 6 個頂點(diǎn)，第三層有 12個頂點(diǎn)，第四層有 24 個頂點(diǎn)，以此類推，第 k 層有 123 ??k個頂點(diǎn)。首先考慮伴隨圈 nC 的染色，因?yàn)槠漤旤c(diǎn)（特征樹 T 的葉子結(jié)點(diǎn)）與相連的結(jié)點(diǎn)構(gòu)成了七個頂點(diǎn)的子圖 1H ，只考慮這個部分，對子圖 1H 進(jìn)行這樣的彩虹邊染色。相應(yīng)地，其它的五個子 圖使用相同的染色方法，同樣只需要 }7,6,5,4,3,2,1{ 七種顏色。 IX 圖 3 4 層的 Halin 圖 4G 接下來，我們考慮其它層數(shù) k 的 Halin 圖，并且推導(dǎo)出了其彩虹連通數(shù))( xGrc ： 情況 1：當(dāng) 1?k 時，則有 1)( 1 ?Grc 。 圖 2?k 的 Halin 圖 情況 3：當(dāng) 3?k 時 我們的染色方法同 4?k 時的 Halin 圖的染色方法相同， k 層的 Halin 圖 kG 的頂點(diǎn)數(shù) 223 ??? kn ，圖 kG 中包含了 323 ??k