【正文】 [8]， to Graph Theory. Boston， 2020； [9]， . The Probabilistic Method. New York， 2020。 XXIX 第三章 結(jié)語(yǔ) 本文是課題是“特殊圖類的彩虹邊染色”，選取三類特殊圖。這類廣義 ?? 圖從最里的一對(duì)路徑 1Q 和 2Q 開(kāi)始染色，直到最外的一對(duì)路徑 2?tQ 和 1?tQ ，這些染色方式按照本文介紹的方法進(jìn)行染色。 圖 9 四條路徑的廣義 ?? 圖 到這一步，我們就完成了這個(gè)只有四條路徑 4321 , 的廣義 ?? 圖的彩虹染色，運(yùn)用這樣的彩色方法，就使得圖中任意兩個(gè)頂點(diǎn)之間至少有一條彩虹路相連，廣義 ?? 圖是彩虹連通的，并且彩虹連通數(shù)是 10)( ??rc 。 圖 8 四條路徑的廣義 ?? 圖 完成了路徑 1Q 和 2Q 的彩虹染色，我們?cè)賮?lái)考慮另外一對(duì)路徑 3Q 和 4Q 的彩虹染色。于是，我們可以得到，邊數(shù)總是比頂點(diǎn)數(shù)多 1，那么假設(shè) 1Q 上有 1k 個(gè)頂點(diǎn)，就有 11?k條邊，類似的， iQ 上有 ik 個(gè)頂點(diǎn)，就有 1?ik 條邊， ti??1 。那么對(duì)于 G 使用了 1?n 種顏色，并且這種染色是一個(gè)彩虹 ?2 連通的，其中 3?t 。顯然，2?t 時(shí)，圖 G 就是一個(gè)圈。 接下來(lái)， iG 的邊染色， )( iGV 種顏色。另外，如果)( iQVz? ，對(duì)于 iQ 選擇外部和導(dǎo)向使得 z 是 iQ 的末頂點(diǎn)。 圖 7 四條路徑的廣義 ?? 圖 定理 7 證明：首先定義一些子圖 GGGG t ???? ?10 ， 0?t ， 00 Q? 是一個(gè)圈。類似的，對(duì)于 )2( ， )(}{ 1?? iHVXu ? ；對(duì)于 )3( ， )(, 1?? iHVYX 。 重復(fù)歸納，可以得到 iH 的一個(gè)染色， ti??0 。染 l ,2? 使用的所有顏色數(shù)為 1)( ??? lFVm 。令lF ???1? ， )( 1?? ij HV? 是路勁 jQ 的另一個(gè)端點(diǎn)，其中 lj??1 。 對(duì)于每個(gè) i ， ti??0 ，歸納證明了，存在一個(gè) iH 的邊染色，至多使用l HVl i)()1( ? 種顏色，使得定理 5 中的 )1( 到 )3( 的性質(zhì)成立，這里使用 iH 代替 G 。 定理 .6 )( 定理Fan 令 G 是一個(gè) ?k 連通圖。 首先，了解 ?l 連通圖： 定理 .4 如果 G 是一個(gè) ?l 連通圖， 2?l ，頂點(diǎn) 1??ln ，那么 l nlGrc )1()(2 ??。本文的概念定 義部分介紹了，一個(gè)圖 G 是 ?k 連通的，當(dāng)且僅當(dāng)任意兩個(gè)頂點(diǎn)之間是連通的，并且由 k 條內(nèi)部頂點(diǎn)不相交的路徑連通。 綜上所述，我們可以確定新輪圖 knW? 的彩虹連通數(shù)。 之前有說(shuō)明 ，頂點(diǎn)數(shù) 8?n 的輪圖 8W 的彩虹連通數(shù)是 3)( 8 ?Wrc ，增加一個(gè)內(nèi)部頂點(diǎn)以后，可以使得彩虹連通數(shù)變?yōu)?2)( 28 ??Wrc 。同情況 1類似，圈 nC 上的邊的染色需要的顏色完全可以取自 k 種顏色，且遠(yuǎn)遠(yuǎn)少于 k 種，就能夠滿足在圖 knW? 中，任意兩個(gè)頂點(diǎn)之間至少有一條彩虹路相連， k 種顏色就已經(jīng)使得圖 knW? 彩虹連通。為了便于觀看，只選取了圈 8C 上的一個(gè)頂點(diǎn) v 與內(nèi)部 8 的頂點(diǎn)相連，同時(shí)省略了 8 個(gè)內(nèi)部頂點(diǎn)與圈 8C 上別的頂點(diǎn)之間的連接邊。這就使得 2)( 3 ?vvc ，反過(guò)來(lái)使得 1)( 1 ??vvc n 。 最后考慮，當(dāng) 7?n 時(shí)。 新輪圖 knW? 是一個(gè)有 k 個(gè)內(nèi)部頂點(diǎn) kvvv , 21 ? ，但 k 個(gè)頂點(diǎn)之間沒(méi)有邊直接 XV 相連接，有 n 個(gè)葉子頂點(diǎn)，且被一個(gè)圈連接的圖，根據(jù) Halin 圖的定義，可知新輪圖 knW? 并不是一個(gè)特殊的 Halin 圖，但是它的特殊性值得研究，那么新輪圖knW? 的最小度 },2m in{ nk ??? 。這樣， )( xGrc 就關(guān)于層數(shù) k 的函數(shù)，423)( 2 ??? ?kkGrc ，而 )(Grc 也可變換為有關(guān)層數(shù) k 的函數(shù)， 5 329)( ??? xGrc 。這就證明了H? 是彩虹連通的。進(jìn)一步，先假設(shè) 3??ts 。令邊 ijf 映射到頂點(diǎn) ix ， 3,2,1?j 。從 Chandran 等人的結(jié)論中，我們能夠容易推出彩虹連通數(shù)的一個(gè)上界： 31)( 3313)( ?????? Gk nnGrc ? 因此，對(duì)于連通度 3)( ?Gk ，彩虹連通數(shù) 343)( ?? nGrc ，連通度 4)( ?Gk ，彩虹連通數(shù) 353)( ?? nGrc 。 并且這個(gè)上界是針對(duì)所有的 ?3 連通圖而言的，而本文驗(yàn)證的是一個(gè)特殊的 ?3 連通圖，它的所有頂點(diǎn)的度為 3 ，即 3?? ， 343)( ?? nGrc 。 因?yàn)橐粋€(gè)子圖中任意一個(gè)頂點(diǎn)有三條邊連接，所以這樣的兩個(gè)頂點(diǎn)之間有許多條路連接，只要確保這條路徑在子圖 iH 和 jH 中邊的顏色不同，那么這條路一定是彩虹路，也就是說(shuō)任意兩點(diǎn)之間至少有一條彩虹路連接。 圖 2?k 的 Halin 圖 情況 3：當(dāng) 3?k 時(shí) 我們的染色方法同 4?k 時(shí)的 Halin 圖的染色方法相同， k 層的 Halin 圖 kG 的頂點(diǎn)數(shù) 223 ??? kn ，圖 kG 中包含了 323 ??k 個(gè)（ nC 與相連的結(jié)點(diǎn)構(gòu)成的七個(gè)頂點(diǎn)）的子圖。相應(yīng)地，其它的五個(gè)子 圖使用相同的染色方法，同樣只需要 }7,6,5,4,3,2,1{ 七種顏色?？梢詮膱D中看出，第一層有 3 個(gè)頂點(diǎn)，第二層有 6 個(gè)頂點(diǎn)，第三層有 12個(gè)頂點(diǎn)，第四層有 24 個(gè)頂點(diǎn)，以此類推，第 k 層有 123 ??k個(gè)頂點(diǎn)。再做一個(gè)圈 nC 連接 T 的所有葉子頂點(diǎn)，即圈 nC 上的頂點(diǎn)是由 T 的所有葉子頂點(diǎn)組成。 圖 2 圖 G ： 4)( ?Grc 通過(guò)這兩個(gè)例子，我們可以得出， 如果圖 G 是一個(gè)大小為 m 的非平凡連通圖，則有： mGrcGdi am ?? )()( 。進(jìn)一步假設(shè)， 1)( 1 ??uuc ， 2)( 11 ?? vuc ， 3)( 1 ?? vvc 。因?yàn)?2)(diam ?G ，所以，圖 P 的任何彩虹染色至少使用了兩種顏色，即 2)( ?Prc 。如果 k 是對(duì)圖 G進(jìn)行彩虹 ?k 邊染色所需的最少顏色數(shù)， 稱為圖 G 的彩虹連通數(shù)，記作 )(Grc 。 ?l 邊連通圖 G 是指一個(gè)圖 G 的任意兩個(gè)不同頂點(diǎn)之間至少有 l 條相互獨(dú)立的路相連。在此，頂點(diǎn) 0x 和 kx 由路 P 連接，并稱它們是路的端點(diǎn)，而 11 , ?kxx ? 稱為 P 的內(nèi)部頂點(diǎn)。 前面有說(shuō)到無(wú)向圖，簡(jiǎn)單說(shuō)就是不具有方向性的圖。可以看出，邊集 E 中的元素是頂點(diǎn)集 V 中元素的 ?2 元子集，并且默認(rèn) V 和 E 的交集為空集。 2020 年， Chartrand, Johns, McKeon 和 Zhang 首次提出了圖的彩虹連通性的概念，這是對(duì)經(jīng)典連通性概念的一種加強(qiáng)。 I 畢業(yè)論文 特殊圖類的彩虹邊染色 II 1 前言 我們都知道，圖論是源于一個(gè)著名的問(wèn)題 —— 哥尼斯堡七橋問(wèn)題。我們都知道，彩虹連通數(shù)是一個(gè)自然的組合概念，除了具有理論上的意義，更重要的是在網(wǎng)絡(luò)問(wèn)題中有著很重要的應(yīng)用。 圖的分類眾多，本文所研究的圖均為有限的簡(jiǎn)單無(wú)向圖。定義在圖 G 的邊的集合中，每個(gè)元素 ),( vu 為一對(duì)頂點(diǎn)構(gòu)成的無(wú)序?qū)?，表示頂點(diǎn) u 和 v 相關(guān)聯(lián)的一條無(wú)向邊，若是無(wú)向圖，那么 ),( vu 和 ),( uv 表示的是同一條邊。一條路上的邊數(shù)稱為路的長(zhǎng)度，記 kxxxP ?10? ，稱 P 是一條 0x 和 kx 之間的路。 IV 邊連通度是指，使得圖 G 是 ?l 邊連通的最大整數(shù) l ，記作 )(G? 。顯然，彩虹連通圖一定是連通的，且將所有邊染不同顏色可以得到連通圖的一個(gè)彩虹染色。假設(shè)，圖 P 有一個(gè)彩虹 ?2 染色 c ，那么對(duì)于圖 P 的相鄰的兩條邊可能染同種顏色，比如說(shuō)，邊uwe? 和邊 wvf? 染相同的顏色。 接下來(lái)，考慮其它邊的染色，首先，如果 x 和 y 是圖 G 的任意兩個(gè)頂點(diǎn)，并且 2),( ?yxd ，那么在圖 G 中僅有一條長(zhǎng)度為 2 的 yx? 路，而其它所有的 yx? 路的長(zhǎng)度是 4 或者更大，因此，這就說(shuō)明在圖 G 中沒(méi)有兩條相鄰的邊染色是相同的。 通過(guò)上述的例子，我們已經(jīng)初步了解到圖的彩虹染色，彩虹連通數(shù)等概念，本文針對(duì)三類特殊的圖進(jìn)行彩虹染色，并且給出了彩虹連通數(shù)的一個(gè)上界。這樣得到的圖被稱作 Halin 圖，樹(shù) T 叫做特征樹(shù)，圈 nC叫做伴隨圈。對(duì)一個(gè)度為 3 ，有 k 層的 Halin 圖 G ，記第 i（ ki??1 ）層為 iG ， ki??1 ，其總的頂點(diǎn)數(shù)為 223 ??? kn 。此時(shí)，伴隨圈 nC 上還有一些邊未染色，我們選取}7,6,5,4,3,2,1{ 中的任意一種顏色對(duì)其進(jìn)行染色，比如說(shuō)，我們選取了顏色 1對(duì)這些邊進(jìn)行染色。將所有這樣的子圖用上述的方法進(jìn)行染色，共使用七種顏色，而伴隨圈nC 上未染色的邊可選取 }7,6,5,4,3,2,1{ 中的任意一種顏色對(duì)其進(jìn)行染色。因此，無(wú)論哪種情況，此種染色方法得到的 Halin 圖都能滿足，圖 xG 中任意兩個(gè)頂點(diǎn)之間至少有一條彩虹路相連。但是，利用這個(gè)上界驗(yàn)證之前，在它的基礎(chǔ)上對(duì)于這個(gè)上界做了一些改善，使得更為緊一些，即 5 )1(3)( ?? nGrc ，再以改善后的這個(gè)上界來(lái)驗(yàn)證本文的結(jié)論。接下來(lái)，我們將對(duì)連通度為 3)( ?Gk 的彩虹連通數(shù)343)( ?? nGrc 的上界做出改善，即 5 )1(3)( ?? nGrc 。我們可以把這四個(gè)頂點(diǎn) 4321 , xxxx加入圖 H 中，從而形成一個(gè)更大的子圖 H? ，它有 4?h 個(gè)頂點(diǎn)。我們可以把頂點(diǎn) ts uuuxvvv ?? , 2121 加入 H 中，從而構(gòu)成一個(gè)更大的子圖 H? ，它有 1??? tsh 個(gè)頂點(diǎn)。于是，我們有： 515 )1(32 151532 1)()( ??????????? ??????????? ????? tshtshtsHrcHrc 這就和 H 的極大性矛盾了。做一個(gè)簡(jiǎn)單的 計(jì)算，可以得到： 5 329)(423)( 2 ??????? ? xkx GrcGrc ，當(dāng) Nkk ?? ,3 時(shí)。 在推導(dǎo)新輪圖 knW? 的彩虹連通數(shù)之前，讓我們先來(lái)看看輪圖 nW 的彩虹連通數(shù)，參考了文獻(xiàn) ]7[ 。定義一個(gè) ?3 邊染色 }3,2,1{)(: ?nWEc 如下：如果 i 是奇數(shù)，則 1)( ?vvc i ；如果 i 是偶數(shù)，則 2)( ?vvc i ；對(duì)于每個(gè) )( nCEe? ，有 3)( ?ec 。類似的， 1)( 1 ??vvc n XVI 使得 2)( 2 ?vvc 。 可以看出， 8 個(gè)內(nèi)部頂點(diǎn)之間存在一條最短的路 ji KvK ?? ， }8,2,1{, ??ji 且ji? ，于是決定將此條路染色成彩虹路，因此邊分別染 色，色，色， 821 ??vK i ，8,2,1 ??i ，這樣的染色方法確保了 8 個(gè)內(nèi)部頂點(diǎn)之間的最短路徑 ji KvK ?? 是一條彩虹路。因此，彩虹連通數(shù) kWrc kn ?? )( 。因此，研究這類的新輪圖knW? 是有一定意義的。 當(dāng) 3?n ， 2?k 時(shí)，新輪圖 knW? 的彩虹連通數(shù)是： kWrc kn ?? )( 。因此，前面定義的 )(Grck 僅僅是針對(duì) ?k 連通圖而言的。 在情況 2?l 中，如果圖 G 是一個(gè) ?2 連通串并聯(lián)圖是一個(gè)簡(jiǎn)單圖，從 三個(gè)頂點(diǎn) 3K 開(kāi)始，反復(fù)運(yùn)用一個(gè)操作序列，這個(gè)序列是一個(gè)分支，由一條邊變換成雙條邊，反復(fù)增加分支邊。對(duì)于任意的頂點(diǎn) )(GVu? 和任意集合 )( uGVX ?? ， kX? ，這里有從 u 到 X 的 k 條路徑，使得對(duì)于其中的任意兩條路，僅僅只有一個(gè)共同頂點(diǎn) u 。那么，集合 ti? 就意味著對(duì)于 G 而言定理 4 成立。分別把 jQ的第一條邊和最后一條邊射入到 i