【導(dǎo)讀】圖論是數(shù)學(xué)中的一個(gè)重要的分支。它以圖為研究的對(duì)象。圖論原本是應(yīng)用數(shù)。學(xué)的一個(gè)重要的分支，為此，歷史上曾有許多位數(shù)學(xué)家獨(dú)自地建立過(guò)圖論。都有很強(qiáng)的現(xiàn)實(shí)背景。著名的柯尼斯堡七橋問(wèn)題就是圖論的起源。方法走遍的判定規(guī)則。這項(xiàng)研究所取得的成果奠定了歐拉圖論〔及拓?fù)鋵W(xué)〕創(chuàng)始。染色問(wèn)題是圖論的一類重要的題目，具有重要的實(shí)際意義和理論意義。種很重要的分支。染色問(wèn)題就是給定一個(gè)圖，把它所有頂點(diǎn)或所有的邊染上顏色，對(duì)不同圖類的染色問(wèn)題的研究，已經(jīng)有了比較豐富的成果，并且這些結(jié)論。還在不斷的完善之中。事實(shí)上，它產(chǎn)生于政府機(jī)構(gòu)之間機(jī)密信息的安全傳輸，在網(wǎng)絡(luò)安全等實(shí)。彩虹點(diǎn)連通的概念是由Krivelevich，Yuster首次提出的，是。由學(xué)生來(lái)選修，學(xué)期結(jié)束后要對(duì)學(xué)生進(jìn)行考試。顯然，每個(gè)考生每場(chǎng)只能參加一。頂點(diǎn)nvvv,...,21分別來(lái)表示這n門(mén)課程。的頂點(diǎn)，即度為0的頂點(diǎn)稱為孤立頂點(diǎn)。，稱P是一條0x和kx之間的一條路。

　　

【正文】 ,: 21 ? ， ni??1 ，邊為 ie 。對(duì)于 3?n 的圈，在圈中加入一個(gè)頂點(diǎn) 1K ，使得 1K 與圈上的每個(gè)頂點(diǎn)連接，那么這樣的圖 1KCn? 就稱作輪圖 nW 。 輪圖 nW 是一個(gè)有 1個(gè)內(nèi)部頂點(diǎn) 1K ， n 個(gè)葉子頂點(diǎn)，且被一個(gè)圈連接的圖，根據(jù) Halin 圖的定義，可知輪圖 nW 是一個(gè)特殊的 Halin 圖，最小度 2?? 。 下面我們先介紹一下 Halin 圖的定義：在平面上嵌入一棵樹(shù) T ， T 的每個(gè)內(nèi)部頂點(diǎn)的度數(shù)至少為 2 ，并且至少有一個(gè)內(nèi)部頂點(diǎn)。再做一個(gè)圈 nC 連接 T 的所有葉子頂點(diǎn)，即圈 nC 上的頂點(diǎn)時(shí)由 T 的所有葉子頂點(diǎn)組成。這樣的得到的圖被稱作Halin 圖，樹(shù) T 叫做特征樹(shù)，圈 nC 叫做伴隨圈。 我們已經(jīng)在前面說(shuō)明了圈 nC 的彩虹點(diǎn)連通數(shù) ??????? 2)( nCrvc n，接下來(lái)也將給出輪圖 nW 的彩虹連通數(shù)，并證明。當(dāng) 然我們所研究的不僅僅是這樣的輪圖，而是圈中加入了 k 個(gè)頂點(diǎn)的輪圖 kn KC? ，并且給出輪圖 knW? 的彩虹連通數(shù)和證明。 新輪圖 knW? 是一個(gè)有 k 個(gè)內(nèi)部頂點(diǎn) kK ，但 k 個(gè)頂點(diǎn)之間沒(méi)有邊直接相連接，有 n個(gè)葉子頂點(diǎn)，且被一個(gè)圈連接的圖，根據(jù) Halin 圖的定義，可知新輪圖 knW? 并不是一個(gè)特殊的 Halin 圖，但是它的特殊性值得研究，那么新輪圖 knW? 的最小度},2m in{ nk ??? 。研究 輪圖以及它的推廣圖彩虹連通性的研究 在推導(dǎo)新輪圖 knW? 的彩虹連通數(shù)之前， 讓我們先來(lái)看看輪圖 nW 的彩虹點(diǎn)連通數(shù)。經(jīng)過(guò)圖例的觀察內(nèi)部頂點(diǎn)為一個(gè)時(shí)的輪圖，發(fā)現(xiàn)當(dāng) 3?n 時(shí)輪圖是一個(gè)完全圖， 0)( ?Grvc ；當(dāng) 4?n 時(shí)，無(wú)論怎樣的去增加圈上的頂點(diǎn)它的 )(Grvc 始終不變， 1)( ?Grvc 。然后我們也發(fā)現(xiàn)增加輪圖的內(nèi)部頂點(diǎn)，它的 )(Grvc 也是不變的，1)( ?Grvc ，如圖所示： 圖 11 下面我們來(lái)研究一下輪圖的推廣圖，在圈 nC ),......( 2,1 nuuu 的外部在增加一個(gè)圈 39。nC ),......( 2,1 nvvv ，兩個(gè)圈上的頂點(diǎn)都與內(nèi)部頂點(diǎn) K 相連，稱為二層輪圖 2nW 。它所有的的頂點(diǎn)集為 },......,......{)( 2,12,1 nn vvvuuuGV ? ，它所有的邊的集合為 )(GE ， }, . . . . . . ., . . . . . ., . . . . . ., . . . . . ., . . . . . .,{)( 12112111121 nnnnnnnn vvvvuuuuvuvuKvKvKuKuKuGE ??? 。如下圖所示： 圖 12 研究這類圖形，我們分為幾個(gè)方面來(lái)討論，當(dāng) 3?n 時(shí)： （ 1） 我們先來(lái)研究頂點(diǎn) K 和圈 nC 的連線，它們之間并沒(méi)有內(nèi)部頂點(diǎn)虹頂點(diǎn)，所以彩虹連通數(shù) 0)( ?Grvc ； （ 2） 在看 K 與 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。nC 自己內(nèi)部頂點(diǎn)彩虹連通，可如圖所示，它所需的最小顏色數(shù)是4，則有 4)( ?Grvc ； 圖 13 （ 5） 使圈 nC 與 39。nC 上的點(diǎn)彩虹連通，最多需要 3種顏色，所以它的彩虹頂點(diǎn)連通數(shù)有 3)( ?Grvc 。 綜上所述，這 類二層輪圖的彩虹頂點(diǎn)連通數(shù)有一個(gè)上界 4)( ?Grvc 。 上述研究只是一個(gè)大概的范圍，下面我們來(lái)研究一下，當(dāng)圈上的點(diǎn)數(shù) n 為具體數(shù)值時(shí)的情況。 我們先來(lái)看一下 3?n 時(shí)，顯然 1)( ?Grvc ； 當(dāng) 64 ??n 時(shí)， 2)( ?Grvc ； 當(dāng) 107 ??n 時(shí)， 3)( ?Grvc ； 圖 14 當(dāng) 11?n 時(shí)， 4)( ?Grvc 。 圖 15 綜上所述，有??????????????11,4107,364,23,12nnnnWn 。 6 結(jié)束語(yǔ) 在本文中我們主要談到了圖論中的一個(gè)并不為大家所熟知的一個(gè)領(lǐng)域，其主要討論了彩虹連通性相關(guān)的一些相關(guān)的知識(shí)，讓大家對(duì)這些知識(shí) 有一些初步的了解，同時(shí)也對(duì)彩虹連通性的研究在一些實(shí)際生活中的應(yīng)用有了一些認(rèn)識(shí)。 我所研究的這些圖形只是一些簡(jiǎn)單的圖形，研究起來(lái)相對(duì)容易，對(duì)于一些復(fù)雜的圖形在研究時(shí)需要注意很多的條件，所以在選擇圖形時(shí)我只選取了一些簡(jiǎn)單圖以便研究。我所研究的第一個(gè)圖類是廣義 ? 圖，這類圖形的變化形式很多，要考慮的條件也有很多我在文章中所求出的彩虹連通數(shù)是有意義的但是否為最佳的還有待考證。第二種圖類是在圈的基礎(chǔ)上的一種推廣形式，這種圖形也還有一些更復(fù) 雜的變換形式，我在文章中只解出了其中的一種形式。第三種圖類是在輪圖的基礎(chǔ)上進(jìn)行的推廣，這類圖也還可以有很多種變換，我所研究的都是這些圖雷中相對(duì)簡(jiǎn)單的，所以還需要更多時(shí)間和努力才能把這些圖類研究透徹。 最后由于我個(gè)人能力和知識(shí)水平的有限，還有題目比較新穎所能參閱的資料不足，所以文章中可以會(huì)有一些錯(cuò)誤或者不準(zhǔn)確的地方，還希望看過(guò)這篇文章的讀者能夠提出一些問(wèn)題或改進(jìn)意見(jiàn)，讓這些研究能更接近于正確，而我也能從中更好地學(xué)習(xí)這些知識(shí)。 參考文獻(xiàn) [1] 王維凡 ,李超 .非 負(fù)特征圖的線性染色 [M]中國(guó)科學(xué) A 輯 ,2020,38:13211334. [2] 黃丹君 , 王維凡 . 高度平面的鄰點(diǎn)可區(qū)別全染色 [J] 中國(guó)科學(xué) : 數(shù) 學(xué) ,2020,42:151164. [3] 萬(wàn)慧敏 ,史小藝 ,王艷麗 .幾種特殊圖的邊染色 [J]五邑大學(xué)學(xué)報(bào) ,2020. [4] 李學(xué)良 ,董英九 .圖的彩虹連通數(shù)與最小度和 [J]中國(guó)科學(xué) ,數(shù)學(xué) ,2020年 01 期 :815. [5] 王淑棟 , 李崇明 , 許進(jìn) , 龐善臣 [J] 若干圖類的鄰強(qiáng)邊染色 , 數(shù)學(xué) 研 究 .2020(04)412417. [6] 馬德 ,劉林忠 ,張忠輔 .樹(shù)的 鄰強(qiáng)邊染色 [J]數(shù)學(xué)研究與評(píng)論 .2020(02):299305. [7] 林全文 ,輪圖和多輪圖的生成樹(shù)的計(jì)數(shù) [J]數(shù)學(xué)的實(shí)踐與認(rèn)識(shí) .2020(03)450454. [8] Rehinhard Diestel 著 ,于青林 ,王濤 ,王光輝 ,圖論第四版 (M)高等教育出版 社 ,2020,108115. [9] 孫惠泉 ,圖論及其應(yīng)用 [M]科學(xué)出版社 ,2020,100108. [10] ， ， ， ， R. Yuster， On rainbow connection.[J]Electron J Combon 15（ 2020）， R57. [11] Chandran L, Das A, Rajendraprasad D, et al. Rainbow connection number and connected dominating sets [J] Graph Theory, 2020, 71: 206218. [12] C. Nomikos, A. Pagourtzis and S. Zachos. Routing and path multicoloring.[J] Information Processing Letters, 80(2020) 249256. [13] D. de Werra, Lausanne, Heuristics for graph coloring.[J]Computing Supplementum, 7(1990)191208. [14] I. Holyer. The NPCompleteness of edgecoloring. SIAM J. Computing, 10: 4(1981) 718720. [15].. Borodin and . Kostochka. List edge and list total colorings of multigraphs.[J]Journal of Combinatorial Theory, (Ser. B), 71(1997), 184204. [16] Xiao Zhou, H. Suzuki and T. Nishizeki. An NC parallel algorithm for edgecoloring seriesparallel multigraphs.[J] Journal of Algorithms, 23(1997) 359374. [17] Krivelevich M, Yuster R. The rainbow connection of a graph is (at most) reciprocal to its minimum degree. [J] Graph Theory, 2020, 63: 18519.