【正文】 點(diǎn)著相同顏色，則容易知道， c 可以擴(kuò)充為 G 的 5 正常頂點(diǎn)著色； 情形 2 在 c 下，設(shè)在與 u 的相鄰接點(diǎn)中， 5個(gè)頂點(diǎn)著了 5種不同顏色。設(shè) 5)()( ?? Gud ? ，令 uGG ??1 。當(dāng) 1?n 時(shí)，結(jié)論顯然。肯普給出了四色定理的一個(gè)證明 方法 ， 被當(dāng)時(shí)的人們所接受 ，但 11 年后，珀西 五色定理 把一個(gè)平面分成若干的區(qū)域，給這些區(qū)域進(jìn)行染色，并使任意相鄰的區(qū)域染上不同的染色，滿足這些條件所需的顏色數(shù)最多為五種 。這就是著名的 4色定理。 儲(chǔ)藏問(wèn)題 一家公司制造 n 種化學(xué)制品 nCCC ,......, 21 ，其中某些制品是互不相容的，如果它們互相接觸，則會(huì) 引起爆炸，作為一種預(yù)防措施，公司希望把它的倉(cāng)庫(kù)分為間隔，以便把不相容的化學(xué)制品儲(chǔ)藏在不同的間隔里，試問(wèn)：這個(gè)倉(cāng)庫(kù)至少應(yīng)該分成幾個(gè)間隔？ 問(wèn)題處理：構(gòu)造一個(gè)圖 G ，其頂點(diǎn)集是 },......,{ 21 nvvv 兩個(gè)頂點(diǎn) iv 和 jv 相連當(dāng)且僅黨化學(xué)制品 iC 和 jC 互不相容，則倉(cāng)庫(kù)的最小間隔數(shù)即為 G 的頂點(diǎn)數(shù)。 A9: AC, S, LA。 A5: AC, LA, S 。 (學(xué)生用 Ai 表示） A1: LA, S 。 課程安排問(wèn)題：某大學(xué)數(shù)學(xué)系要為這個(gè)夏季安排課程表。 L 的頂點(diǎn)不 被染色 。 我們也 把 L 劃分成兩個(gè)部 分 1L 和 2L ，其中 1L 是那些具有在 D 中至少一個(gè)鄰 點(diǎn) 的頂點(diǎn)。S 支配的點(diǎn)集 。 令 39。SG 和 39。由引理 ，我們可以假設(shè) G 有小于))1(1( ?? ??n 條 邊。這個(gè)生成子圖的每個(gè)連接 的部分 都有至少 有1?? 個(gè)頂點(diǎn)。顯然，這個(gè)過(guò)程持續(xù)了至多為 ))1(1( ?? ??n步 。我們所說(shuō)的 2階點(diǎn) 集 k強(qiáng)如果每一個(gè)并非由它 支配 的頂點(diǎn)有至少存在 k 這是由它 支配相鄰的 。 定理 對(duì)于每對(duì)整數(shù) )5 87,5(, ??? ababa ，存在一個(gè)連通圖 G 使得 )(,)( bGsrv caGrv c ?? 。 引理 令 u ， v 是連通圖 G 的兩個(gè)頂點(diǎn)，如果距離 1)(),( ?? Gdiamd vuG ，那么不存在包含 u 和 v 作為內(nèi)部定點(diǎn)的測(cè)地線。 彩虹頂點(diǎn)連通數(shù)， )(Grvc 強(qiáng)彩虹頂點(diǎn)連通數(shù) )(Gsrvc （簡(jiǎn)單有限無(wú)向圖），對(duì)于任意非平凡連通圖 G 有 )()( GsrvcGrvc ? 。這種情況下，染色 c 稱為 G 的強(qiáng)彩虹染色。我們不得不采用路徑最少的渠道，彩虹連通性就可以解決這個(gè)問(wèn)題。 由于自然組合的概念，彩虹邊連通和彩虹點(diǎn)連通吸引了許多學(xué)者的興趣。事實(shí)上， nGrvc ?)( 的著色只要求每個(gè)切 點(diǎn) 有 不同的顏色 。例如， ? ? 11,1 ??nKrvc 而? ? 11,1 ??? nnKrc 。一個(gè)簡(jiǎn)單的發(fā)現(xiàn)是如果一個(gè)圖 G 有 n 個(gè)頂點(diǎn)，則有 2)( ??nGrvc ；當(dāng)且僅當(dāng)它是一個(gè)完全圖時(shí)有 0)( ?Grvc 。 彩虹邊連通數(shù)就是 一個(gè)連通圖 G 使它構(gòu)成彩虹邊連通所需要的最小的顏色數(shù)，稱為記做 )(Grc 。邊染色 },...,1{: kEc ? 稱為圖 G 的一個(gè) ?k 邊染色，所使用的最小整數(shù) k 稱為 G 的邊色數(shù)，也成為色指數(shù)，記做 )(39。我們稱 S 里的顏色為可用顏色，并且主要研究的是 S 的基數(shù)。 G 為 ?k 可著色的 G 為 ?k 可著色的（ k=j） 最簡(jiǎn)單的 ?2 連通圖是圈，并且其它的圖都可以由一個(gè)圈通過(guò)不斷添加路而 得到。如果 G 有一個(gè) ?k （頂點(diǎn)）著色，則稱 G 是 ?k （頂點(diǎn)）可染色。其中使得圖 G 是 ?l 邊連通的最大整數(shù)稱為 G 的邊連通度，記為)(G? 。 如果無(wú)向圖 G 中的任一對(duì)頂點(diǎn)之間都是連通的，則稱圖 G 是連通圖，反之，如果一個(gè)無(wú)向圖不是連通的，則稱作非連通圖。 圖 ),( EVP? 是一條路，如果其頂點(diǎn)集和邊集分別為 },{ 10 kxxxV ?? ，},{ 12110 kk xxxxxxE ?? ?，這里的 ix 均互不相同。 假設(shè)有兩個(gè)圖 G 和 H ，如果兩個(gè)圖的頂點(diǎn)集有這樣的關(guān)系， )(HV 是 )(GV 的一個(gè)子集，邊集 )(HE 是 )(GE 的一個(gè)子集，那么就稱圖 H 是圖 G 的子圖。自環(huán)是兩端連接著同一頂點(diǎn)的邊，既不含平行邊也不含自環(huán)的圖稱為簡(jiǎn)單圖。 一個(gè)圖的階就是圖的頂點(diǎn)個(gè)數(shù)，記作 G 。顯然，我們希望使用不同渠道的數(shù)量降至最低，用彩虹染色的方法就可以解決這個(gè)問(wèn)題。幾百年來(lái)，很多的數(shù)學(xué)家們都為此花費(fèi)了大量的心血去研究。跟圖的邊著色問(wèn)題一樣，生活中的很多問(wèn)題，也可以給它們建立一個(gè)模型并看作為圖的頂點(diǎn)染色問(wèn)題來(lái)處理。例 如，圖 1（ a）所示的區(qū)域圖可看作為圖 1（ b）所表示的平面圖。這樣的問(wèn)題就是頂點(diǎn)染色問(wèn)題。當(dāng)然，不會(huì)出現(xiàn)同一個(gè)學(xué)生的不同課程在同一個(gè)時(shí)間所進(jìn)行的考試。它也有著很多實(shí)際的應(yīng)用， 也 同樣 是研究的熱點(diǎn)問(wèn)題之一。在網(wǎng)絡(luò)中的任意兩點(diǎn)在之間都 要 有一條路 相 連接，而且在該路徑上的每段都被分配一個(gè)獨(dú)特的頻道（例如，不同的頻率）。 連通性是圖論中最重要的性質(zhì)之一， 2020 年， Chartrand， Johns 等人首次提出了圖的彩虹連通性的概念， 是 經(jīng)典連通性概念的一種加強(qiáng)。不同類型的圖的 染色 問(wèn) 題一直是圖論中的熱點(diǎn)題目，而連通圖的染色問(wèn)題又是其中一種很重要的分支。著名的柯尼斯堡七橋問(wèn)題就是圖論的起源。 1 前言 課題背景 圖論是數(shù)學(xué)中的一個(gè) 重 要的分支。早在1736 年歐拉的著作中 就出現(xiàn)了 關(guān)于圖論的文字記 載， 最 初 他所思考的 圖論問(wèn)題都 有很強(qiáng)的現(xiàn)實(shí)背景。 染色問(wèn)題是圖論的一類重要的題目，具有重要的實(shí)際意義和 理論意義 。對(duì)不同圖類的染色問(wèn)題的研究，已經(jīng)有了比較豐富的成果，并且這些結(jié)論還在不斷的完善之中。假如我們需要在一個(gè)蜂窩網(wǎng)絡(luò)中進(jìn)行信息的傳輸。彩虹點(diǎn)連通的概念是由 Krivelevich， Yuster 首次提出的，是彩虹連通性的一種重要推廣 。試問(wèn)這次考試最少要進(jìn)行幾場(chǎng) ? 顯然，不可以在同一個(gè)時(shí)間進(jìn)行同一個(gè)學(xué)生所選修的兩門(mén)課程的考試。這樣的問(wèn)題可以看做給圖 G 的每一個(gè)頂點(diǎn)染色，并要求相鄰的兩個(gè)頂點(diǎn)染不同的顏色，求最少要進(jìn)行幾場(chǎng)考試，就是最少能用多少種顏色使得圖 G 的相鄰頂點(diǎn)都有不同顏色。 問(wèn)題處理：如果把每一個(gè)地區(qū)看作一個(gè)頂點(diǎn)，把相鄰兩個(gè)地區(qū)用一條邊連接起來(lái)，就能夠把一個(gè)區(qū)域圖看作一個(gè)平面圖。例如，在圖 1中，把不同的區(qū)域用城市的名字來(lái)表示，所染的顏色用不同的數(shù)字來(lái)表示，則在圖中表示了不同的地區(qū)用不同的染色來(lái)染色的問(wèn)題。 圖 1 研究該課題的意義 在日常生活中，還有許多問(wèn)題可以用彩虹頂點(diǎn)染色加以解決，比如電視頻道分配問(wèn)題，變址寄存器等，可以運(yùn)用彩虹染色方法輕松解決，圖的染色理論是圖論中的重要內(nèi)容，也是圖論的起源之一。假設(shè) G代表一個(gè)一個(gè)細(xì)胞網(wǎng)絡(luò)，我們希望在管道的任意兩個(gè)頂點(diǎn)之間能夠傳遞消息，這要求每個(gè)鏈接上的頂點(diǎn)之間的路由都分配了一個(gè)不同的渠道 (如不同的頻率 )。圖 G 的頂點(diǎn)集合是 V 中的各個(gè)元素，頂點(diǎn)的集合記作 )(GV ；而圖 G 的邊的集合為 E 中的元素，邊的集合記作 )(GE 。 在無(wú)向圖 G 中，如果與頂點(diǎn) u 和 v 相連接的無(wú)向邊多于一條，則把這些邊稱作平行邊，而平行邊的條數(shù)我們稱之為重?cái)?shù)。本文所研究用到的圖均為有限的簡(jiǎn)單無(wú)向圖。圖形 G 的最小度指的是所有頂點(diǎn)之間的最小度， 記為 )(G? ；而圖 G 最大度：指的是所有頂點(diǎn)之間的最大度數(shù)，記為 )(G? 。 在無(wú)向圖 G 中，若從頂點(diǎn) u 到 v 有一條路相連，則稱 u 和 v 之間是連通的。 如果圖 G 的任意兩個(gè)不同頂點(diǎn)之間都有 l 條邊不相交的路相連，則稱圖 G 是?l 邊連通的。這樣的一個(gè)頂點(diǎn)染色給出了 )(GV 的一個(gè) ?k 劃分（ kVVV , 21 ? ）使每個(gè) )1( kiVi ?? 都是G 的一個(gè)獨(dú)立集。 G 為 ?k 可著色的 G 為 ?k 部圖。 若把圖 ),( EVG? 的一個(gè)頂點(diǎn)染色看作是一個(gè)映射 SVc ?: ，并令它的任意兩個(gè)相鄰的點(diǎn) v 和 w 都滿足 )()( wcvc ? 。 若把圖 ),( EVG? 的一個(gè)邊染色看作是一個(gè)映射 SEc ?: ，并令它的任意兩條相鄰的邊 e 和 f ，滿足 )()( fcec ? 。 如果一個(gè)邊染色圖的任意兩個(gè)不同頂點(diǎn)之間有一條邊染不同染色的路徑相連，那么就稱它是彩虹連通的。彩虹點(diǎn)連通數(shù)就是一個(gè)連通圖 G 它構(gòu)成彩虹點(diǎn)連通圖所需的最少的顏色數(shù)，記做 )(Grvc 。 在某些情況下 )(Grvc 可以比 )(Grc 要小得多。此圖有 n 個(gè) 切點(diǎn)，因此 nGrvc ?)( 。 這些例子 表明彩虹邊染色的證明與彩虹點(diǎn)染色的不同 。假設(shè)我們要在蜂窩網(wǎng)絡(luò)的兩個(gè)頂點(diǎn)之間傳遞信息，每個(gè)連接在網(wǎng)絡(luò)上都會(huì)有不同的渠道。如果對(duì) G 中的每對(duì)不同頂點(diǎn) u 和 v 都存在一條彩虹 vu? 測(cè)地線。同樣的，連通圖 G 的強(qiáng)彩虹點(diǎn)連通數(shù)是使圖 G 強(qiáng)彩虹點(diǎn)連通所需要的最少的顏色數(shù)，記作 )(Gsrvc 。 如果 H 是非平凡連通圖 G 的一個(gè)聯(lián)通生成子圖，那么 )()( HrvcGrvc ? ，)()( HsrvcGsrvc 與 無(wú)單調(diào)性。 引理 令 G 是一個(gè) n 階（ 3?n ）的連通圖，如果 G 不只有 一條路，那么有 3)( ??nGsrvc 。然而，我們需要從它的額外 的 重要要求。觀察到，當(dāng)過(guò)程已經(jīng)停止，其余的每個(gè)頂點(diǎn)已經(jīng)失去了超過(guò) 2? 的度，因此有超過(guò) 2?的與它相 鄰 在被 刪除 的 頂點(diǎn)集合 中 。 證明 :刪除從 G 中度數(shù)大 于 ? 的邊連