【正文】 使用了 l HVlHV )()1()( 00 ??種顏色，定理 4 的 )1( 到 )3( 成立。 最后，我們?cè)谇闆r 1到情況 3 中驗(yàn)證，定理 4 的 )1( 到 )3( 成 立對(duì)于 iH 成立。這就完成了定理 4 的證明 ，因此定理 1也就成立了。定義廣義 ? 圖：令qtqG ,1??? ，它是 2?t 的路徑的集合，路徑的長(zhǎng)度 11 ??? tqq ? ，其中 21??tq ，并且路勁上的 每對(duì)內(nèi)部頂點(diǎn)時(shí)不相交的，而且都有兩個(gè)相同的端點(diǎn)。 x 和 y 一定是一些路徑 jQP? 的末端點(diǎn)， ij??0 ，如果一些路徑 ),1( jlilQl ??? 的末端點(diǎn)是路徑 P 的的內(nèi)部頂點(diǎn)，那么路徑 P 一定包含了路徑 lQ 的兩個(gè)端點(diǎn)。而且，假設(shè)路徑 jQ 是以 1?jG 外部為導(dǎo)向， ij??1 )2(?i 。加入的 iQ 和方向同上面方法一樣。 對(duì)于每個(gè) i 重復(fù)，直到 GGt? 。假設(shè) 1?iG 是染色，使用了 )( 1?iGV 中顏色。所以證明了定理 2 。 首先，因?yàn)?2)( ??? nyGe ，如 果給圖 G 染色，少于 2?n 種顏色，那么對(duì)于某些頂點(diǎn)}{ )(, xyvu ??，在 yG? 中存在唯一的 vu? 路徑 P 不是彩虹路。路徑 iQ 的邊染色映射到端點(diǎn) x 和 y ，分別染色 i 和 1?i ，其中 11 ??? ti 。 廣義θ圖的彩虹頂點(diǎn)連通性 建立一個(gè)廣義θ圖 G ，它由 t 條邊連成 ),( ,...,21 tQ ，如下圖所示。 一類特殊的圖類的彩虹點(diǎn)連通性的研究 圖類的介紹 接下來(lái)我們?cè)賮?lái)研究一類特殊的圖形 G ， G 是由一個(gè)由 n 個(gè)頂點(diǎn)的圈為基礎(chǔ)，把圈上相對(duì)的頂點(diǎn)依次相連，構(gòu)成一類圖，相連的邊的數(shù)量記為 t。 輪圖的彩虹點(diǎn)連通性 輪圖以及它的推廣圖的介紹 我們?cè)賮?lái)研究一類圖 —— 輪圖， 輪圖 nW 可簡(jiǎn)單定義為 1KCn? ， 3?n ，因?yàn)?1K加入到 nC 中，產(chǎn)生了一個(gè)新的頂點(diǎn)與 nC 的每個(gè)頂點(diǎn)相連。 下面我們先介紹一下 Halin 圖的定義：在平面上嵌入一棵樹(shù) T ， T 的每個(gè)內(nèi)部頂點(diǎn)的度數(shù)至少為 2 ，并且至少有一個(gè)內(nèi)部頂點(diǎn)。當(dāng) 然我們所研究的不僅僅是這樣的輪圖，而是圈中加入了 k 個(gè)頂點(diǎn)的輪圖 kn KC? ，并且給出輪圖 knW? 的彩虹連通數(shù)和證明。然后我們也發(fā)現(xiàn)增加輪圖的內(nèi)部頂點(diǎn)，它的 )(Grvc 也是不變的，1)( ?Grvc ，如圖所示： 圖 11 下面我們來(lái)研究一下輪圖的推廣圖，在圈 nC ),......( 2,1 nuuu 的外部在增加一個(gè)圈 39。nC 的連線，他們的連線上只有一個(gè)內(nèi)部頂點(diǎn)，所以也只需要一種顏色足以使它們彩虹頂點(diǎn)連通，則 1)( ?Grvc ； （ 3） 要使 nC 自己內(nèi)部頂點(diǎn)彩虹連通，則需要借助頂點(diǎn) K ，這樣就構(gòu)成了一個(gè)輪圖，所以它也只需一種顏色即可滿足彩虹頂點(diǎn)連通 1)( ?Grvc ； （ 4） 要使 39。 上述研究只是一個(gè)大概的范圍，下面我們來(lái)研究一下，當(dāng)圈上的點(diǎn)數(shù) n 為具體數(shù)值時(shí)的情況。 我所研究的這些圖形只是一些簡(jiǎn)單的圖形，研究起來(lái)相對(duì)容易，對(duì)于一些復(fù)雜的圖形在研究時(shí)需要注意很多的條件，所以在選擇圖形時(shí)我只選取了一些簡(jiǎn)單圖以便研究。 最后由于我個(gè)人能力和知識(shí)水平的有限，還有題目比較新穎所能參閱的資料不足，所以文章中可以會(huì)有一些錯(cuò)誤或者不準(zhǔn)確的地方，還希望看過(guò)這篇文章的讀者能夠提出一些問(wèn)題或改進(jìn)意見(jiàn)，讓這些研究能更接近于正確，而我也能從中更好地學(xué)習(xí)這些知識(shí)。第二種圖類是在圈的基礎(chǔ)上的一種推廣形式，這種圖形也還有一些更復(fù) 雜的變換形式，我在文章中只解出了其中的一種形式。 圖 15 綜上所述，有??????????????11,4107,364,23,12nnnnWn 。nC 上的點(diǎn)彩虹連通，最多需要 3種顏色，所以它的彩虹頂點(diǎn)連通數(shù)有 3)( ?Grvc 。它所有的的頂點(diǎn)集為 },......,......{)( 2,12,1 nn vvvuuuGV ? ，它所有的邊的集合為 )(GE ， }, . . . . . . ., . . . . . ., . . . . . ., . . . . . ., . . . . . .,{)( 12112111121 nnnnnnnn vvvvuuuuvuvuKvKvKuKuKuGE ??? 。研究 輪圖以及它的推廣圖彩虹連通性的研究 在推導(dǎo)新輪圖 knW? 的彩虹連通數(shù)之前， 讓我們先來(lái)看看輪圖 nW 的彩虹點(diǎn)連通數(shù)。這樣的得到的圖被稱作Halin 圖，樹(shù) T 叫做特征樹(shù)，圈 nC 叫做伴隨圈。對(duì)于 3?n 的圈，在圈中加入一個(gè)頂點(diǎn) 1K ，使得 1K 與圈上的每個(gè)頂點(diǎn)連接，那么這樣的圖 1KCn? 就稱作輪圖 nW 。 彩虹點(diǎn)連通性的研究 下面我們先來(lái)討論一下圈上頂點(diǎn)數(shù)為偶數(shù)時(shí)的情況，我們先以頂點(diǎn)數(shù) n為 10為例，如下圖： 圖 8 然后分別給每幅圖染色，不加邊時(shí)染 5 色，加一條染 4色，加兩條染 4色，加三條染 3色，如下圖： 圖 9 可以看出，隨著連接邊數(shù)的增加彩虹連通數(shù)在逐漸的減小，我們接下來(lái)繼續(xù)觀察，加四條邊時(shí)染 3色，加五條邊時(shí)染 2色，如下圖： 圖 10 由上所給出的圖形可以看出，在頂點(diǎn)連線增加的過(guò)程中彩虹頂點(diǎn)連通數(shù)不是嚴(yán)格遞減的。 圖 5 現(xiàn)在我們來(lái)討論一下廣義 ? 圖的彩虹頂點(diǎn)連通性。那么對(duì)于 G 使用了 1?n 種顏色，并且這種染色是一個(gè)彩虹 ?2 連通的，其中 3?t 。因此，2)(2 ??nGrc 。顯然， 2?t時(shí)，圖 G 就是一個(gè)圈。那么 iG是染色的，使用了 )( iGV 種顏色。 接下來(lái)， iG 的邊染色， )( iGV 種顏色。因此，我們能夠重復(fù)加入和重復(fù)導(dǎo)向 11 , ?? ij ? ，按照這樣做法，對(duì)于 iG 達(dá)到一個(gè)外部和一個(gè)導(dǎo)向。另外，如果)( iQVz? ，對(duì)于 iQ 選擇外部和導(dǎo)向使得 z 是 iQ 的末頂點(diǎn)。 構(gòu)造串并聯(lián)圖，設(shè)置 )( 0GVz? ，先確定一個(gè)圈 0G ，以順時(shí)針旋轉(zhuǎn)作為參考。 圖 4 定理 2 證明：首先定義一些子圖 GGGG t ???? ?10 ， 0?t ， 00 Q? 是一個(gè)圈。 我們可以知道，當(dāng) G 時(shí)圈 nC ，有 n 個(gè)頂點(diǎn)時(shí)，彩虹連通數(shù) nCrc n ?)(2 。類似的，對(duì)于 )2( ， )(}{ 1?? iHVXu ? ；對(duì)于)3( ， )(, 1?? iHVYX 。對(duì)于情況 1和情況 3 ，因?yàn)?)( ??lFV ，所以 iH 的 總 的 使 用 顏 色 數(shù) 至 多 是l HVllFVl HVl ii )()1()()()1( 1 ????? ? 。 重復(fù)歸納，可以得到 iH 的一個(gè)染色， ti??0 。對(duì)邊進(jìn)行染色，路徑 12?jQ 的第一條邊和路徑 jQ2 的最后一條邊染 12 ?? jm 色，路徑 12?jQ 的最后一條邊和路徑 jQ2 的第一條邊染 jm2? 色。染 l ,2 ? 使用的所有顏色數(shù)為 1)( ??? lFVm 。就 1)( ??? llFV 而言，l ,2? 的染色使用顏色為 lFVmm ??? )(,1 ? ，采用這樣的染色方法，每種顏色至少出現(xiàn)過(guò) 1次。令lF ???1? ， )( 1?? ij HV? 是路勁 jQ 的另一個(gè)端點(diǎn)，其中 lj??1 。假設(shè) 1?iH 有一個(gè)邊染色，顏色是 色，色， m?1 ，其中 ti??1 。 對(duì)于每個(gè) i ， ti??0 ，歸納證明了，存在一個(gè) iH 的邊染色，至多使用l HVl i)()1( ? 種顏色，使得定理 4 中的 )1( 到 )3( 的性質(zhì)成立，這里使用 iH 代替 G 。現(xiàn)在，假設(shè)找到這樣一些圖 10 , ?iHH ? ， 1?i ，如果 )()( 1 GVHV i ?? ，那么集合 ti HH ??1 ，否則的話，這里存在一個(gè)頂 點(diǎn))( )( 1?? ii HV GVv。 定理 3 )( 定理Fan 令 G 是一個(gè) ?k 連通圖 。 定理 2 如果 G 是一個(gè) ?l 連通圖， 2?l ，頂點(diǎn) 1??ln ，那么存在圖 G 的一個(gè)邊染色，至多是 l nl )1( ? 種顏色滿足以下結(jié)論： )1( 對(duì)于任意兩個(gè)頂點(diǎn) )(, GVvu ? ，這里存在兩條不相交的彩虹 vu? 路； )2( 對(duì)于任意一個(gè)頂點(diǎn) )(GVu? ，任意集合 )(GVX? ，且 2?X ，這里兩條彩虹 Xu? 路，只有頂點(diǎn) u 相同； )3( 對(duì)于任意兩個(gè)集合 )(, GVYX ? ，且 2, ?YX ，這里的兩條彩虹 YX? 路不相交。 首先，了解 ?l 連通 圖： 定理 1 如果 G 是一個(gè) ?l 連通圖， 2?l ，頂點(diǎn) 1??ln ，那么 l nlGrc )1()(2 ??。 我們繼續(xù)說(shuō)明 )(Grck ，對(duì)于 1?k ， Caro 等人證明了，如果圖 G 的階數(shù)為 n ，那么 32)( nGrc ? ，如果圖 G 是 ?2 連通的，即 2?k ，那么 )(2)( nOnGrc ?? 。接下來(lái)，我們給 出彩虹 ?k 連通數(shù))(Grck 的定義：若存在圖 G 的一個(gè)邊染色，使用 t 種顏色就能夠使得圖 G 彩虹 ?k連通，其中 t 是最小的整數(shù)，那么彩虹 ?k 連通數(shù)為： tGrck ?)( 。因此，設(shè)法構(gòu)想一適當(dāng)?shù)捻旤c(diǎn)排序進(jìn) 行貪心著色，往往可能得到一個(gè)較好的著色結(jié)果（如 Brooks 定理之證明）。從而得到推論。 情形 1 在 c下，如果在與 u 相鄰接點(diǎn)中，至少有兩個(gè)頂