特殊圖類的彩虹點染色畢業(yè)論文-閱讀頁
2025-07-07 17:10本頁面
【正文】 圖，頂點數(shù)為，那么定理證明：假設是條路徑，是條路徑的共同的端點。因此，假設。但是在中，有唯一的一對不相交的路，并且是其中的一條路徑。接下來，對染色。下一步，對別的邊染不同的顏色。因此。其中t為圖所包含的邊數(shù)，為它所有的頂點數(shù)，為每條邊上的頂點數(shù)不包含兩個公共的頂點。討論的過程主要分為幾個步驟來研究，首先來由兩條邊所圍成的一個圈來討論，為一個圈時它的彩虹點連通數(shù)有上界，設彩虹頂點連通所使用的顏色數(shù)為S，即，染色情況如下圖所示：圖 6然后在增加一條邊來看，令彩虹頂點連通所使用的顏色數(shù)為S，當為偶數(shù)時取中間的兩個頂點染上所用過的顏色，其余點分別進行染色；當為奇數(shù)時取中間的一個點染所使用的顏色，其余點分別進行染色，如下圖所示圖 7從而有的彩虹點連通數(shù)，按照這個方法對圖的剩下的邊進行研究，最后得出圖的彩虹頂點連通數(shù)的一個上界：。我們把這類圖分為兩種情況去研究，第一種為圈上的頂點為偶數(shù)，第二種圈上的頂點為奇數(shù)，奇數(shù)頂點時圈上總會有一個頂點是獨立的，不與其他點相連的。通過對大量圖形的研究與總結(jié)這類圖形的的彩虹點連通數(shù)隨著所連接的邊數(shù)的增多而減少。接下來我們對輪圖進一步說明，首先定義圈，邊為。輪圖是一個有個內(nèi)部頂點，個葉子頂點，且被一個圈連接的圖，根據(jù)Halin圖的定義，可知輪圖是一個特殊的圖，最小度。再做一個圈連接的所有葉子頂點，即圈上的頂點時由的所有葉子頂點組成。我們已經(jīng)在前面說明了圈的彩虹點連通數(shù)，接下來也將給出輪圖的彩虹連通數(shù)，并證明。新輪圖是一個有個內(nèi)部頂點，但個頂點之間沒有邊直接相連接，有個葉子頂點，且被一個圈連接的圖，根據(jù)圖的定義，可知新輪圖并不是一個特殊的圖，但是它的特殊性值得研究，那么新輪圖的最小度。經(jīng)過圖例的觀察內(nèi)部頂點為一個時的輪圖，發(fā)現(xiàn)當時輪圖是一個完全圖，；當時，無論怎樣的去增加圈上的頂點它的始終不變。它所有的的頂點集為，它所有的邊的集合為。綜上所述，這類二層輪圖的彩虹頂點連通數(shù)有一個上界。我們先來看一下時，顯然；當時，；當時，；圖 14當時。6 結(jié)束語 在本文中我們主要談到了圖論中的一個并不為大家所熟知的一個領(lǐng)域，其主要討論了彩虹連通性相關(guān)的一些相關(guān)的知識，讓大家對這些知識有一些初步的了解，同時也對彩虹連通性的研究在一些實際生活中的應用有了一些認識。我所研究的第一個圖類是廣義圖，這類圖形的變化形式很多，要考慮的條件也有很多我在文章中所求出的彩虹連通數(shù)是有意義的但是否為最佳的還有待考證。第三種圖類是在輪圖的基礎上進行的推廣，這類圖也還可以有很多種變換，我所研究的都是這些圖雷中相對簡單的，所以還需要更多時間和努力才能把這些圖類研究透徹。參考文獻[1] 王維凡,[M]中國科學A 輯,2008,38:13211334.[2] 黃丹君,[J]中國科學:數(shù) 學,2012,42:151164.[3] 萬慧敏,史小藝,[J]五邑大學學報,2012.[4] 李學良,[J]中國科學,數(shù)學,2013年01 期:815.[5]王淑棟,李崇明,許進,龐善臣[J]若干圖類的鄰強邊染色,數(shù)學研 (04)412417.[6] 馬德,劉林忠,[J](02):299305.[7] 林全文,輪圖和多輪圖的生成樹的計數(shù)[J](03)450454.[8] Rehinhard Diestel著,于青林,王濤,王光輝,圖論第四版(M)高等教育出版 社,2012,108115.[9] 孫惠泉,圖論及其應用[M]科學出版社,2004,100108.[10] ，R. Yuster，On rainbow connection.[J]Electron J Combon 15（2008），R57.[11] Chandran L, Das A, Rajendraprasad D, et al. Rainbow connection number andconnected dominating sets [J] Graph Theory, 2012, 71: 206218.[12] C. Nomikos, A. Pagourtzis and S. Zachos. Routing and path multicoloring.[J]Information Processing Letters, 80(2001) 249256.[13] D. de Werra, Lausanne, Heuristics for graph coloring.[J]ComputingSupplementum, 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, 2010, 63: 18519.
公司管理相關(guān)推薦
鄂ICP備17016276號-1