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

　　

【正文】 ,: 21 ? ， ni??1 ，邊為 ie 。對于 3?n 的圈，在圈中加入一個頂點 1K ，使得 1K 與圈上的每個頂點連接，那么這樣的圖 1KCn? 就稱作輪圖 nW 。 輪圖 nW 是一個有 1個內(nèi)部頂點 1K ， n 個葉子頂點，且被一個圈連接的圖，根據(jù) Halin 圖的定義，可知輪圖 nW 是一個特殊的 Halin 圖，最小度 2?? 。 下面我們先介紹一下 Halin 圖的定義：在平面上嵌入一棵樹 T ， T 的每個內(nèi)部頂點的度數(shù)至少為 2 ，并且至少有一個內(nèi)部頂點。再做一個圈 nC 連接 T 的所有葉子頂點，即圈 nC 上的頂點時由 T 的所有葉子頂點組成。這樣的得到的圖被稱作Halin 圖，樹 T 叫做特征樹，圈 nC 叫做伴隨圈。 我們已經(jīng)在前面說明了圈 nC 的彩虹點連通數(shù) ??????? 2)( nCrvc n，接下來也將給出輪圖 nW 的彩虹連通數(shù)，并證明。當 然我們所研究的不僅僅是這樣的輪圖，而是圈中加入了 k 個頂點的輪圖 kn KC? ，并且給出輪圖 knW? 的彩虹連通數(shù)和證明。 新輪圖 knW? 是一個有 k 個內(nèi)部頂點 kK ，但 k 個頂點之間沒有邊直接相連接，有 n個葉子頂點，且被一個圈連接的圖，根據(jù) Halin 圖的定義，可知新輪圖 knW? 并不是一個特殊的 Halin 圖，但是它的特殊性值得研究，那么新輪圖 knW? 的最小度},2m in{ nk ??? 。研究 輪圖以及它的推廣圖彩虹連通性的研究 在推導新輪圖 knW? 的彩虹連通數(shù)之前， 讓我們先來看看輪圖 nW 的彩虹點連通數(shù)。經(jīng)過圖例的觀察內(nèi)部頂點為一個時的輪圖，發(fā)現(xiàn)當 3?n 時輪圖是一個完全圖， 0)( ?Grvc ；當 4?n 時，無論怎樣的去增加圈上的頂點它的 )(Grvc 始終不變， 1)( ?Grvc 。然后我們也發(fā)現(xiàn)增加輪圖的內(nèi)部頂點，它的 )(Grvc 也是不變的，1)( ?Grvc ，如圖所示： 圖 11 下面我們來研究一下輪圖的推廣圖，在圈 nC ),......( 2,1 nuuu 的外部在增加一個圈 39。nC ),......( 2,1 nvvv ，兩個圈上的頂點都與內(nèi)部頂點 K 相連，稱為二層輪圖 2nW 。它所有的的頂點集為 },......,......{)( 2,12,1 nn vvvuuuGV ? ，它所有的邊的集合為 )(GE ， }, . . . . . . ., . . . . . ., . . . . . ., . . . . . ., . . . . . .,{)( 12112111121 nnnnnnnn vvvvuuuuvuvuKvKvKuKuKuGE ??? 。如下圖所示： 圖 12 研究這類圖形，我們分為幾個方面來討論，當 3?n 時： （ 1） 我們先來研究頂點 K 和圈 nC 的連線，它們之間并沒有內(nèi)部頂點虹頂點，所以彩虹連通數(shù) 0)( ?Grvc ； （ 2） 在看 K 與 39。nC 的連線，他們的連線上只有一個內(nèi)部頂點，所以也只需要一種顏色足以使它們彩虹頂點連通，則 1)( ?Grvc ； （ 3） 要使 nC 自己內(nèi)部頂點彩虹連通，則需要借助頂點 K ，這樣就構(gòu)成了一個輪圖，所以它也只需一種顏色即可滿足彩虹頂點連通 1)( ?Grvc ； （ 4） 要使 39。nC 自己內(nèi)部頂點彩虹連通，可如圖所示，它所需的最小顏色數(shù)是4，則有 4)( ?Grvc ； 圖 13 （ 5） 使圈 nC 與 39。nC 上的點彩虹連通，最多需要 3種顏色，所以它的彩虹頂點連通數(shù)有 3)( ?Grvc 。 綜上所述，這 類二層輪圖的彩虹頂點連通數(shù)有一個上界 4)( ?Grvc 。 上述研究只是一個大概的范圍，下面我們來研究一下，當圈上的點數(shù) n 為具體數(shù)值時的情況。 我們先來看一下 3?n 時，顯然 1)( ?Grvc ； 當 64 ??n 時， 2)( ?Grvc ； 當 107 ??n 時， 3)( ?Grvc ； 圖 14 當 11?n 時， 4)( ?Grvc 。 圖 15 綜上所述，有??????????????11,4107,364,23,12nnnnWn 。 6 結(jié)束語 在本文中我們主要談到了圖論中的一個并不為大家所熟知的一個領(lǐng)域，其主要討論了彩虹連通性相關(guān)的一些相關(guān)的知識，讓大家對這些知識 有一些初步的了解，同時也對彩虹連通性的研究在一些實際生活中的應用有了一些認識。 我所研究的這些圖形只是一些簡單的圖形，研究起來相對容易，對于一些復雜的圖形在研究時需要注意很多的條件，所以在選擇圖形時我只選取了一些簡單圖以便研究。我所研究的第一個圖類是廣義 ? 圖，這類圖形的變化形式很多，要考慮的條件也有很多我在文章中所求出的彩虹連通數(shù)是有意義的但是否為最佳的還有待考證。第二種圖類是在圈的基礎(chǔ)上的一種推廣形式，這種圖形也還有一些更復 雜的變換形式，我在文章中只解出了其中的一種形式。第三種圖類是在輪圖的基礎(chǔ)上進行的推廣，這類圖也還可以有很多種變換，我所研究的都是這些圖雷中相對簡單的，所以還需要更多時間和努力才能把這些圖類研究透徹。 最后由于我個人能力和知識水平的有限，還有題目比較新穎所能參閱的資料不足，所以文章中可以會有一些錯誤或者不準確的地方，還希望看過這篇文章的讀者能夠提出一些問題或改進意見，讓這些研究能更接近于正確，而我也能從中更好地學習這些知識。 參考文獻 [1] 王維凡 ,李超 .非 負特征圖的線性染色 [M]中國科學 A 輯 ,2020,38:13211334. [2] 黃丹君 , 王維凡 . 高度平面的鄰點可區(qū)別全染色 [J] 中國科學 : 數(shù) 學 ,2020,42:151164. [3] 萬慧敏 ,史小藝 ,王艷麗 .幾種特殊圖的邊染色 [J]五邑大學學報 ,2020. [4] 李學良 ,董英九 .圖的彩虹連通數(shù)與最小度和 [J]中國科學 ,數(shù)學 ,2020年 01 期 :815. [5] 王淑棟 , 李崇明 , 許進 , 龐善臣 [J] 若干圖類的鄰強邊染色 , 數(shù)學 研 究 .2020(04)412417. [6] 馬德 ,劉林忠 ,張忠輔 .樹的 鄰強邊染色 [J]數(shù)學研究與評論 .2020(02):299305. [7] 林全文 ,輪圖和多輪圖的生成樹的計數(shù) [J]數(shù)學的實踐與認識 .2020(03)450454. [8] Rehinhard Diestel 著 ,于青林 ,王濤 ,王光輝 ,圖論第四版 (M)高等教育出版 社 ,2020,108115. [9] 孫惠泉 ,圖論及其應用 [M]科學出版社 ,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.