【正文】 相互獨(dú)立的路相連。 研究圖，必然需要知道什么是路。 簡(jiǎn)單圖就是既不含平行邊也不含自環(huán)的圖，所說(shuō)的平行邊是指在無(wú)向圖 G中，如果和頂點(diǎn) u 和 v 相關(guān)聯(lián)的無(wú)向邊多于一條，那么則稱這些邊為平行邊，平行邊的條數(shù)稱為重?cái)?shù)。 首先，需要了解圖的定義，圖定義為一個(gè)二元組 ),( EV 使得 kVE ][? ，記作),( EVG? 。所謂的染色問(wèn)題，就是給定一個(gè)圖，需要把圖中的所有的頂點(diǎn)，或者所有的邊進(jìn)行染色，使得相鄰的頂點(diǎn)或者邊所染的顏色不同，其中優(yōu)秀的染色方法，就是盡量使得需要的顏色數(shù)最少。談到了圖論中的著名問(wèn)題，那就不得不提世界近代三大數(shù)學(xué)難題，同時(shí)對(duì)圖論發(fā)展產(chǎn)生了重大影響的 —— “四色猜想”，這使得圖論中的染色問(wèn)題成為了研究的熱點(diǎn)問(wèn)題，圖的染色問(wèn)題不但在理論上有著重要的意義而且在實(shí)際問(wèn)題中也有著重要的應(yīng)用。假設(shè)信息的傳輸是在一個(gè)蜂窩形狀的網(wǎng)絡(luò)中，而這個(gè)網(wǎng)絡(luò)中的任意兩個(gè)頂點(diǎn)之間都有一條路相連，并且這條路徑上的每一段路需要分配一個(gè) 獨(dú)特的頻道（比如說(shuō)，分配不同波段的頻率）。圖的階是指頂點(diǎn)的個(gè)數(shù)稱，記作 G 。假設(shè) G 和 H是兩個(gè)圖，如果頂點(diǎn)集 )(HV 是 )(GV 的一個(gè)子集，邊集 )(HE 也是 )(GE 的子集，那么就稱圖 H 是圖 G 的一個(gè)子圖。 一個(gè)圖 G 是連通的，如果無(wú)向圖 G 中的任意一對(duì)頂點(diǎn)都是連通的。 認(rèn)識(shí)了圖的一些基本概念以后，我們來(lái)了解下本文研究的圖的彩虹連通數(shù)。連通圖 G 的任意兩個(gè)頂點(diǎn)之間距離中的最大值，稱為是圖 G 的直徑，記作 )(Gdiam 。因此，3)( ?Prc 。接下來(lái)， }2,1{)}(),({ 32 ??? vvcvvc ，考慮兩種情況：情況 1， 1)( 2 ??vvc ，3)( 3 ??vvc ，那么 3)( 22 ?? vuc ， 1)( 33 ?? vuc ，在這種染色下，圖 G 中沒(méi)有彩虹 31 vu?路。參考文獻(xiàn) ]12[ ，作者證明了對(duì)于任意的 ?3 連 通圖的彩虹連通數(shù)的上界，即 5 )1(3)( ?? nGrc ，利用這個(gè)結(jié)論證明 度數(shù)為 3 的 Halin 圖的彩虹染色方法是有意義的； 參考了文獻(xiàn) ]7[ ，推導(dǎo)出了新輪圖 knW? 的彩虹連通數(shù)；參考了文獻(xiàn) ]18[ ， 從 ?l 連通圖 G 推導(dǎo)出圖 G 是一個(gè) ?2 連通的串并聯(lián)圖，進(jìn)一步根據(jù) ?2 連通串并聯(lián)圖 G ，最后得到了考慮廣義 ?? 圖，并且本文對(duì)廣義 ?? 圖進(jìn)行彩虹染色，得到了彩虹連通數(shù) )(?rc 。 在文獻(xiàn) ]11[ 中，作者證 明了：（找出哪篇文章里得到的這個(gè)結(jié)果）要計(jì)算出任意的一個(gè)圖的彩虹連通數(shù)是一個(gè) ?NP 困難的問(wèn)題。 考慮了度為 3 ，有 k 層的 Halin 圖的這些特點(diǎn)以后，我們可以這樣對(duì)其進(jìn)行邊染色。這樣就得到了 4 層的 Halin 圖 4G 的一種邊染色方法，使用了十六種顏色，可以驗(yàn)證，在這種染色方法下，圖 4G 是彩虹連通的，因此 16)( 4 ?Grc 。這樣得到的一個(gè)邊染色 0c 可驗(yàn)證此時(shí) kG 是彩虹連通的，邊染色 c 所用的顏色數(shù)為 423)323(7 22 ?????? ?? kk ，因此 423)( 2 ??? ?kkGrc 。 在這樣的 Halin 圖中，對(duì)于一些層數(shù)較少的，比如 2,1?k 的圖，可以通過(guò)簡(jiǎn)單的邊染色方法，就能計(jì)算出其彩虹連通數(shù)，并且彩虹連通數(shù)會(huì)少于由式子423)( 2 ??? ?kkGrc 計(jì)算出的彩 虹連通數(shù)。 XII hKrivelevic 和 Yuster 利用 ?2 階支配集的方法，證明了有 n 個(gè)頂點(diǎn)，最小度為 ? 的連通圖 G 的彩虹連通數(shù)為 ?nGrc 20)( ? 。 證明：假設(shè)存在這樣一個(gè) H 是圖 G 的一個(gè)最大連通 子圖，并且滿足5153)( ?? hHrc ，其中 h 是圖 H 的頂點(diǎn)數(shù)。那么我們對(duì) H 的選擇有了矛盾。路徑的前半部分染色是全部不相同的，路徑的后半部分相同序號(hào)的顏色是重復(fù)的。 現(xiàn)在，我們已經(jīng)證明了 3??nh 。首先定義圈1121 , vvvvvC nnn ?? ?? ，其邊為 1?? iii ve ， ni??1 。首先考慮，當(dāng) 3?n 時(shí)， 43 KW? 。 接下來(lái)，我們證明 3)( ?nWrc 。于是 2)( ?nWrc 。類似的，對(duì)于 k 個(gè)內(nèi)部頂點(diǎn)，要保證 k個(gè)內(nèi)部頂點(diǎn)中，任意兩個(gè)頂點(diǎn)之間有一條彩虹路相連，則需要的顏色數(shù)為 k 。斷言這種情況下的彩虹連通數(shù)應(yīng)是 kWrc kn ?? )( ，假設(shè) kWrc kn ?? )( ，那么對(duì)于內(nèi)部的 k 個(gè)頂點(diǎn)而言，會(huì)使得其中某些頂點(diǎn)之間沒(méi)有彩虹路相連，比如說(shuō)頂點(diǎn) ik 和 jk ， ji? ，},2,1{, kji ?? 之間連接的邊染了同種顏色，就沒(méi)有彩虹路。比如說(shuō)，圈 nC 中 500?n ，而內(nèi)部頂點(diǎn)數(shù) 2?k ，像這樣的 n 遠(yuǎn)遠(yuǎn)大于 k 的情況是不屬于情況 3 中所說(shuō)的范圍，我們只是針對(duì)kn? ，但是兩者之間較為接近的情況進(jìn)行的一個(gè)討論。這些定來(lái)自參考文獻(xiàn) ]18[ 。 Chandran 等人證明了，如果圖 G 的最小度為 ? ，那么313)( ???? nGrc ，并且證明了對(duì)于所有階數(shù)為 n ，最小度為 ? 的連通圖 G 都是適用的。 證明定理 4 ，我們是通過(guò)先證明一個(gè)強(qiáng)有力的定理 5 的 結(jié)論，然后間接證明定理 4 。因?yàn)槿我獾??l 連通圖都含有一個(gè)頂點(diǎn)至少是 l 的圈，于是令 0H 是圖 G 的一個(gè)頂點(diǎn)至少是 l 的圈。顯然， 0H 是一個(gè)圈，它是彩虹染色的。 彩虹染色 1Q 使用的顏色為 lFVmm ??? )(,1 ? 。 假設(shè)存在最大的整數(shù) s ， ls 211 ?? ，使得 2)(,),( 21 ?sQeQe ? ?，F(xiàn)在，假設(shè)對(duì)于 1?iH 的染色，至多使用了l HVl i )()1( 1?? 種顏色，定理 5 的 )1( 到 )3( 成立。 完成了 ?l 連通圖 G 的介紹，接下來(lái)考慮圖 G 是一個(gè) ?2 連通的串并聯(lián)圖， 參考文獻(xiàn) ]18[ ： 定理 .7 如果圖 G 是一個(gè) ?2 連通的串并聯(lián)圖，頂點(diǎn) 3?n ，那么 nGrc ?)(2 。每個(gè) )0( tiGi ?? 是一個(gè) ?2 連通串并聯(lián)圖。注意點(diǎn)， iQ 是加入到由 1?jQ 造出的外部界，當(dāng) iQ 加入 jG 的外部。 iQ 加入到 1?iG 的外部。但是在 G中，有唯一的一對(duì)不相交的 vu? 路，并且 P 是其中的一條路徑。以簡(jiǎn)單的只有 4 條路徑的廣義 ?? 圖來(lái)說(shuō)明染色方法，然后推理到有 t 條路徑的廣義 ?? 圖。剩下邊的染色，顏色一定取自這五種顏色，我們這么考慮，路徑 31 uv? ，也可以分為順時(shí)針的一條，和逆時(shí)針的一條，可以看到的是順時(shí)針的一條長(zhǎng)度是 5 ，所以考慮這條路徑的染色，發(fā)現(xiàn)邊 21 vv? 沒(méi)有染色，并且 5 中顏色中只剩下 色5 ，所以染 色5 。剩下邊的染色，顏色一定取自這五種顏色，所以我們可以這樣考慮，路徑 41 uv? ，也可以分為順時(shí)針的一條，長(zhǎng)度是 5 ，和逆時(shí)針的一條，長(zhǎng)度也是 5 ，還是對(duì)順時(shí)針的一條進(jìn)行染色，發(fā)現(xiàn)只有邊 21 vv? 沒(méi)有染色，并且五種顏色中只可以選取 色10 ，所以染 色10 。 接下來(lái)，我們考慮頂點(diǎn)數(shù)是 n（不計(jì)算端點(diǎn) X 和 Y ），路徑數(shù) 3?t 的廣義 ?? XXVIII 圖。所以，這類的廣義 ?? 圖的彩虹連通數(shù) 11212)( 1221 ???????? ?????????? ???? ?? ttt kkkkkrc ?，nkk t ????1 。第二類是：圈為 nC ，有 k 個(gè)內(nèi)部頂點(diǎn)的新輪圖 knW? ，按照本文的染色方法進(jìn)行彩虹染色，使得圖 knW? 是彩虹連通的，并計(jì)算出了這類圖的彩虹連通數(shù)，kWrc kn ?? )( ，其中圈上頂點(diǎn)數(shù) 3?n ，內(nèi)部的頂點(diǎn)數(shù) 2?k 。 [12]Xueliang Li, Yongtang connection in 3connected Graphs。第三類是： n 個(gè)頂點(diǎn)的廣義 ?? 圖，按照本文的染色方法進(jìn)行彩虹染色，使得廣義 ?? 圖是彩虹連通的，并計(jì)算出了這類圖的彩虹連通數(shù) )(?rc ，而現(xiàn)有的廣義 ?? 圖的彩虹連通數(shù)是 21)(2 ??? nnGrc 或 ，其中路徑數(shù) 3?t ，本文染色得出的 )(?rc 遠(yuǎn)比現(xiàn)有的 )(2 Grc 優(yōu)異許多。綜上所述， n 個(gè)頂點(diǎn)的廣義 ?? 圖的彩虹連通數(shù)是： ???????????????????????? ???????????? ???????? ???.3,3,212。這類廣義 ?? 圖從最里的一對(duì)路徑 1Q 和 2Q 開(kāi)始染色，直到最外的一對(duì)路徑 1?tQ 和 tQ 。再選取 XXVII 路徑 14 uv? ，選取順時(shí)針的一條，長(zhǎng)度是 5 ，只有邊 21 uu? 未染色，并且只能染 色7 。這樣的染色后，只剩下邊 1vX? 和邊 1uX? 未被染色，可以分別取 色2和 色3 ，就能確保在 YX ??? 21 中，任意兩個(gè)頂點(diǎn)之間至少有一條彩虹路，那么彩虹連通數(shù) 5)( 21 ???? YXrc 。我們的染色方法是從里面的路徑開(kāi)始，以相對(duì)的兩條路徑為一對(duì)來(lái)進(jìn)行染色。 XXV 接下來(lái)，對(duì) G 染色。因此，證明了，對(duì)于每個(gè) i ， iH 是彩虹連通的。最后，重復(fù)標(biāo)簽 11 , ?? ijj Q ? 分別是 ijj Q , 21 ??? 。對(duì)于 jG 定義一個(gè)方向和一個(gè)平面，以 jG 的外部為導(dǎo)向順時(shí)針圈，且包 含 z 。這是特殊情況，更為一般的情況是，圖 G 是一個(gè)廣義 ?? 圖。對(duì)于情況 2 ，因?yàn)?FV 2)( ? ，所以 iH 的總的使用顏色數(shù)至多是： l HVllFVl HVl ii )()1(1)()()1( 1 ?????? ? 。路徑 12?sQ 的最后一條邊和路徑ls ,22 ?? （每一條長(zhǎng)度為 1）染 12 ?? sm 色。總的，使用了 lFV ?)( 種新的顏色。通過(guò)附加一個(gè)細(xì)分的 lK,1 到 1?iH 得到圖 iH ，其中 l 條路徑匯集于頂點(diǎn) iv 。根據(jù)定 理 6 ， iv 發(fā)出 l 路到 1?iH ，這里的每對(duì)路徑僅僅匯集與 iv ，那些 l 路是 lK,1 的一個(gè)細(xì)分。 對(duì)于 )2( 而言，如果 Xu? ，那么其中的一條路徑取自頂點(diǎn) u 。另外，上文有說(shuō)明圖G 是 ?3 連通的，即 3?k ，可以采用改善后的界，即 5 )1(3)( ?? nGrc 。如果圖 G 中任意兩個(gè)頂點(diǎn)之間是連通的，并且由 k 條內(nèi)部頂點(diǎn)不相交的彩虹路連通，那么邊染色圖 G 就是彩虹 ?k 連通的，其中 Nk? 。那么這樣的圖類對(duì)于我們的研究沒(méi)有任何的意義，所以就不是情況 3 所討論的范圍。 另一方面，要使圖 knW? 中，任意兩個(gè)頂點(diǎn)之間至少有一條彩虹路相連， k 種顏 色就已經(jīng)滿足染色需求，不需要多一種的顏色。按照上述的染色方法，能夠保證任意兩個(gè)內(nèi)部頂點(diǎn) ik 和 jk ， ji? ，之間至少存在一條彩虹路相連，圈 上的邊的染色需要的顏色完全可以取自 k 種顏色，并且不需要取全部的 k 種顏色就能使得在圖 knW? 中，任意兩個(gè)頂點(diǎn)之間至少有一條彩虹路相連。 考慮新輪圖 knW? ， 一個(gè) n 階的圈 1121 , vvvvvC nnn ?? ?? ，還有 k 個(gè)頂點(diǎn)kuuu ?, 21 連接圈 nC 的每個(gè)頂點(diǎn)，且這 k 個(gè)頂點(diǎn)之間沒(méi)有邊直接相連，這樣構(gòu)成的圖就是新輪圖 knW? ?，F(xiàn)在，做一個(gè)相反的假設(shè)， 2)( ?nWrc ，同樣定義輪圖 nW 的一個(gè)彩虹 ?2 染色 c? ，并假設(shè) 1)( 1 ?? vvc 。 再考慮，當(dāng) 64 ??n 時(shí)，輪圖 nW 不再是一個(gè)完全圖，于是 2)( ?nWrc 。 輪圖 nW 是一個(gè)有 1個(gè)內(nèi)部頂點(diǎn) 1K ， n 個(gè)葉子頂點(diǎn)，且被一個(gè)圈連接的圖，根據(jù) Halin 圖的定義，可知輪圖 nW 是一個(gè)特殊的 Halin 圖，最小度 3?? 。 綜上所述，很容易推出： 5 )1(3)( ?? nGrc 。如果 ts? 是奇數(shù)，那么我們可以使路徑 bvvxvuuau ts ?? 2121的 2