【正文】 [12]Xueliang Li, Yongtang connection in 3connectedGraphs。[10],et al. On rainbow connection. Electron J Combin 15, R57 (2008)。參考文獻(xiàn)[1]宋慧敏 吳建良. Halin圖的均勻邊染色[J]. 山東大學(xué)學(xué)報(bào)，2003 38:3134；[2]董九英，[J].中國(guó)科學(xué)：數(shù)學(xué)，2013,43:714；[5]萬(wàn)慧敏，史小藝，[J].五邑大學(xué)學(xué)報(bào)，2012 26:78；[6][D].山東大學(xué)博士論文，2000 25:2124；[7],et al. Rainbow connection in graphs. Math Bohem，2008。第三類是：個(gè)頂點(diǎn)的廣義圖，按照本文的染色方法進(jìn)行彩虹染色，使得廣義圖是彩虹連通的，并計(jì)算出了這類圖的彩虹連通數(shù)，而現(xiàn)有的廣義圖的彩虹連通數(shù)是，其中路徑數(shù)，本文染色得出的遠(yuǎn)比現(xiàn)有的優(yōu)異許多。第二類是：圈為，有個(gè)內(nèi)部頂點(diǎn)的新輪圖，按照本文的染色方法進(jìn)行彩虹染色，使得圖是彩虹連通的，并計(jì)算出了這類圖的彩虹連通數(shù)，其中圈上頂點(diǎn)數(shù)，內(nèi)部的頂點(diǎn)數(shù)。第一類是：度為的圖，按照本文的染色方法進(jìn)行彩虹染色，使得圖是彩虹連通的，并計(jì)算出了這類圖的彩虹連通數(shù)，其中是層數(shù)，且。綜上所述，個(gè)頂點(diǎn)的廣義圖的彩虹連通數(shù)是：其中，個(gè)頂點(diǎn)是指不計(jì)算端點(diǎn)和，只是條路徑上頂點(diǎn)的總數(shù)，即。所以，這類的廣義圖的彩虹連通數(shù)。這里的問(wèn)題只是在于還有一條單一的路徑，我們只需要使得這條路徑是一條彩虹路，就能夠保證整個(gè)廣義圖彩虹連通。情況：，且是奇數(shù)。這類廣義圖從最里的一對(duì)路徑和開(kāi)始染色，直到最外的一對(duì)路徑和。接下來(lái)，我們考慮頂點(diǎn)數(shù)是（不計(jì)算端點(diǎn)和），路徑數(shù)的廣義圖。在前面，我們給出了有個(gè)頂點(diǎn)，路徑數(shù)的廣義圖的彩虹連通數(shù)或者，按照這樣的計(jì)算，本文的四條路徑的廣義圖，頂點(diǎn)數(shù)（不計(jì)算端點(diǎn)和），那么彩虹連通數(shù)至少也是。按照上面的推廣，如果的頂點(diǎn)數(shù)變?yōu)椋捻旤c(diǎn)數(shù)變?yōu)?，那么?duì)于圖還是采用上述的方法進(jìn)行彩虹染色，于是彩虹連通數(shù)是：。再選取路徑，選取順時(shí)針的一條，長(zhǎng)度是，只有邊未染色，并且只能染。剩下邊的染色，顏色一定取自這五種顏色，所以我們可以這樣考慮，路徑，也可以分為順時(shí)針的一條，長(zhǎng)度是，和逆時(shí)針的一條，長(zhǎng)度也是，還是對(duì)順時(shí)針的一條進(jìn)行染色，發(fā)現(xiàn)只有邊沒(méi)有染色，并且五種顏色中只可以選取，所以染。采取相同的染色方法，考慮圖，如圖所示，圖上總的有條邊，考慮最遠(yuǎn)的兩個(gè)頂點(diǎn)（端點(diǎn)和不作為首先考慮的頂點(diǎn)），和，形成了兩條路，順時(shí)針的一條，即，長(zhǎng)度為，逆時(shí)針的一條，即，長(zhǎng)度也為?；氐綀D的推廣上，上面的例子中的路徑和上的頂點(diǎn)數(shù)是具體的，如果的頂點(diǎn)數(shù)變?yōu)椋捻旤c(diǎn)數(shù)變?yōu)?，那么?duì)于圖還是采用上述的方法進(jìn)行彩虹染色，于是彩虹連通數(shù)是：。這樣的染色后，只剩下邊和邊未被染色，可以分別取和，就能確保在中，任意兩個(gè)頂點(diǎn)之間至少有一條彩虹路，那么彩虹連通數(shù)。剩下邊的染色，顏色一定取自這五種顏色，我們這么考慮，路徑，也可以分為順時(shí)針的一條，和逆時(shí)針的一條，可以看到的是順時(shí)針的一條長(zhǎng)度是，所以考慮這條路徑的染色，發(fā)現(xiàn)邊沒(méi)有染色，并且中顏色中只剩下，所以染?；氐铰窂胶吐窂降娜旧?，顯然這兩條路徑加上端點(diǎn)和就是一個(gè)圈，總的有條邊，考慮最遠(yuǎn)的兩個(gè)頂點(diǎn)（端點(diǎn)和不作為首先考慮的頂點(diǎn)），和，這樣就形成了兩條路，順時(shí)針的一條，即，長(zhǎng)度為，逆時(shí)針的一條，即，長(zhǎng)度為。路徑上有個(gè)頂點(diǎn)，有條邊；路徑上有個(gè)頂點(diǎn)，有條邊。我們的染色方法是從里面的路徑開(kāi)始，以相對(duì)的兩條路徑為一對(duì)來(lái)進(jìn)行染色。以簡(jiǎn)單的只有條路徑的廣義圖來(lái)說(shuō)明染色方法，然后推理到有條路徑的廣義圖。因此。下一步，對(duì)別的邊染不同的顏色。接下來(lái)，對(duì)染色。但是在中，有唯一的一對(duì)不相交的路，并且是其中的一條路徑。因此，假設(shè)。完成了連通串并聯(lián)圖，最后考慮廣義圖，參考了文獻(xiàn)：定理如果是一個(gè)廣義圖，頂點(diǎn)數(shù)為，那么定理證明：假設(shè)是條路徑，是條路徑的共同的端點(diǎn)。因此，證明了，對(duì)于每個(gè)，是彩虹連通的。加入到的外部。首先，是彩虹染色，使用了中顏色。假設(shè)是的外部圈，使得。最后，重復(fù)標(biāo)簽分別是。注意點(diǎn)，是加入到由造出的外部界，當(dāng)加入的外部。否則，刪除直到第一個(gè)使得加入的在的外部。如果增加的路徑是以外部為導(dǎo)向，那么導(dǎo)向使得，任然在新的外部圈中。對(duì)于定義一個(gè)方向和一個(gè)平面，以的外部為導(dǎo)向順時(shí)針圈，且包含。每個(gè)是一個(gè)連通串并聯(lián)圖。是從附加一條長(zhǎng)度至少為的路徑到得到的，用兩個(gè)不同的頂點(diǎn)來(lái)辨別路徑的末端點(diǎn)。如圖所示的就是一個(gè)有四條路徑的廣義圖。這是特殊情況，更為一般的情況是，圖是一個(gè)廣義圖。完成了連通圖的介紹，接下來(lái)考慮圖是一個(gè)連通的串并聯(lián)圖，參考文獻(xiàn)：定理如果圖是一個(gè)連通的串并聯(lián)圖，頂點(diǎn)，那么。現(xiàn)在，對(duì)于證明了到成立。對(duì)于歸納假設(shè)，如果。對(duì)于情況，因?yàn)?，所以的總的使用顏色?shù)至多是：。現(xiàn)在，假設(shè)對(duì)于的染色，至多使用了種顏色，定理的到成立。歸納證明了，對(duì)于的染色滿足所有的需求?？偟氖褂昧朔N新的顏色。路徑的最后一條邊和路徑（每一條長(zhǎng)度為1）染色。假設(shè)存在最大的整數(shù)，使得?？偟模褂昧朔N新顏色。彩虹染色使用的顏色為?？偟?，使用了種新的顏色。彩虹染色使用的顏色為。分別把的第一條邊和最后一條邊射入到和。對(duì)于的情況，可以假設(shè)。通過(guò)附加一個(gè)細(xì)分的到得到圖，其中條路徑匯集于頂點(diǎn)。顯然，是一個(gè)圈，它是彩虹染色的。那么，集合就意味著對(duì)于而言定理成立。重復(fù)這個(gè)過(guò)程，直到結(jié)束。根據(jù)定理，發(fā)出路到，這里的每對(duì)路徑僅僅匯集與，那些路是的一個(gè)細(xì)分。因?yàn)槿我獾倪B通圖都含有一個(gè)頂點(diǎn)至少是的圈，于是令是圖的一個(gè)頂點(diǎn)至少是的圈。對(duì)于任意的頂點(diǎn)和任意集合，這里有從到的條路徑，使得對(duì)于其中的任意兩條路，僅僅只有一個(gè)共同頂點(diǎn)。顯然，定理是來(lái)自定理，所以先證明定理，證明之前先給出一個(gè)定理。對(duì)于而言，如果，那么其中的一條路徑取自頂點(diǎn)。證明定理，我們是通過(guò)先證明一個(gè)強(qiáng)有力的定理的結(jié)論，然后間接證明定理。在情況中，如果圖是一個(gè)連通串并聯(lián)圖是一個(gè)簡(jiǎn)單圖，從三個(gè)頂點(diǎn)開(kāi)始，反復(fù)運(yùn)用一個(gè)操作序列，這個(gè)序列是一個(gè)分支，由一條邊變換成雙條邊，反復(fù)增加分支邊。本文會(huì)提供一種新的染色方法，使得廣義圖是彩虹連通的，并且彩虹連通數(shù)小于。另外，上文有說(shuō)明圖是連通的，即，可以采用改善后的界，即。等人證明了，如果圖的最小度為，那么，并且證明了對(duì)于所有階數(shù)為，最小度為的連通圖都是適用的。因此，前面定義的僅僅是針對(duì)連通圖而言的。對(duì)于連通圖的彩虹連通數(shù)，記作，即。如果圖中任意兩個(gè)頂點(diǎn)之間是連通的，并且由條內(nèi)部頂點(diǎn)不相交的彩虹路連通，那么邊染色圖就是彩虹連通的，其中。這些定來(lái)自參考文獻(xiàn)。當(dāng)，時(shí)，新輪圖的彩虹連通數(shù)是：。比方說(shuō)，圈中，而內(nèi)部頂點(diǎn)數(shù)，按照本文的染色方法，就需要種顏色才能使得圖彩虹連通，即，對(duì)于這類的圖，雖然可以計(jì)算出彩虹連通數(shù)，但是失去了圖的彩虹染色的意義，在實(shí)際的應(yīng)用中，我們對(duì)于這樣兩方相差懸殊，必定會(huì)對(duì)少的一方做一些補(bǔ)充，否則投入成本過(guò)大，這也就失去了實(shí)際應(yīng)用的意義。那么這樣的圖類對(duì)于我們的研究沒(méi)有任何的意義，所以就不是情況所討論的范圍。比如說(shuō)，圈中，而內(nèi)部頂點(diǎn)數(shù)，像這樣的遠(yuǎn)遠(yuǎn)大于的情況是不屬于情況中所說(shuō)的范圍，我們只