【正文】 的頂點(diǎn)之間的路由都分配了一個(gè)不同的渠道(如不同的頻率)。圖 1 研究該課題的意義在日常生活中，還有許多問(wèn)題可以用彩虹頂點(diǎn)染色加以解決，比如電視頻道分配問(wèn)題，變址寄存器等，可以運(yùn)用彩虹染色方法輕松解決，圖的染色理論是圖論中的重要內(nèi)容，也是圖論的起源之一。例如，在圖1中，把不同的區(qū)域用城市的名字來(lái)表示，所染的顏色用不同的數(shù)字來(lái)表示，則在圖中表示了不同的地區(qū)用不同的染色來(lái)染色的問(wèn)題。問(wèn)題處理：如果把每一個(gè)地區(qū)看作一個(gè)頂點(diǎn)，把相鄰兩個(gè)地區(qū)用一條邊連接起來(lái)，就能夠把一個(gè)區(qū)域圖看作一個(gè)平面圖。這樣的問(wèn)題可以看做給圖的每一個(gè)頂點(diǎn)染色，并要求相鄰的兩個(gè)頂點(diǎn)染不同的顏色，求最少要進(jìn)行幾場(chǎng)考試，就是最少能用多少種顏色使得圖的相鄰頂點(diǎn)都有不同顏色。試問(wèn)這次考試最少要進(jìn)行幾場(chǎng)? 顯然，不可以在同一個(gè)時(shí)間進(jìn)行同一個(gè)學(xué)生所選修的兩門課程的考試。彩虹點(diǎn)連通的概念是由Krivelevich，Yuster首次提出的，是彩虹連通性的一種重要推廣。假如我們需要在一個(gè)蜂窩網(wǎng)絡(luò)中進(jìn)行信息的傳輸。對(duì)不同圖類的染色問(wèn)題的研究，已經(jīng)有了比較豐富的成果，并且這些結(jié)論還在不斷的完善之中。染色問(wèn)題是圖論的一類重要的題目，具有重要的實(shí)際意義和理論意義。早在1736年歐拉的著作中就出現(xiàn)了關(guān)于圖論的文字記載，最初他所思考的圖論問(wèn)題都有很強(qiáng)的現(xiàn)實(shí)背景。1 前言圖論是數(shù)學(xué)中的一個(gè)重要的分支。著名的柯尼斯堡七橋問(wèn)題就是圖論的起源。不同類型的圖的染色問(wèn)題一直是圖論中的熱點(diǎn)題目，而連通圖的染色問(wèn)題又是其中一種很重要的分支。連通性是圖論中最重要的性質(zhì)之一，2008年，Chartrand，Johns等人首次提出了圖的彩虹連通性的概念，是經(jīng)典連通性概念的一種加強(qiáng)。在網(wǎng)絡(luò)中的任意兩點(diǎn)在之間都要有一條路相連接，而且在該路徑上的每段都被分配一個(gè)獨(dú)特的頻道（例如，不同的頻率）。它也有著很多實(shí)際的應(yīng)用，也同樣是研究的熱點(diǎn)問(wèn)題之一。當(dāng)然，不會(huì)出現(xiàn)同一個(gè)學(xué)生的不同課程在同一個(gè)時(shí)間所進(jìn)行的考試。這樣的問(wèn)題就是頂點(diǎn)染色問(wèn)題。例如，圖1（a）所示的區(qū)域圖可看作為圖1（b）所表示的平面圖。跟圖的邊著色問(wèn)題一樣，生活中的很多問(wèn)題，也可以給它們建立一個(gè)模型并看作為圖的頂點(diǎn)染色問(wèn)題來(lái)處理。幾百年來(lái)，很多的數(shù)學(xué)家們都為此花費(fèi)了大量的心血去研究。顯然，我們希望使用不同渠道的數(shù)量降至最低，用彩虹染色的方法就可以解決這個(gè)問(wèn)題。一個(gè)圖的階就是圖的頂點(diǎn)個(gè)數(shù)，記作。自環(huán)是兩端連接著同一頂點(diǎn)的邊，既不含平行邊也不含自環(huán)的圖稱為簡(jiǎn)單圖。 假設(shè)有兩個(gè)圖和，如果兩個(gè)圖的頂點(diǎn)集有這樣的關(guān)系，是的一個(gè)子集，邊集是的一個(gè)子集，那么就稱圖是圖的子圖。圖是一條路，如果其頂點(diǎn)集和邊集分別為，這里的均互不相同。如果無(wú)向圖中的任一對(duì)頂點(diǎn)之間都是連通的，則稱圖是連通圖，反之，如果一個(gè)無(wú)向圖不是連通的，則稱作非連通圖。其中使得圖是邊連通的最大整數(shù)稱為的邊連通度，記為。如果有一個(gè)（頂點(diǎn)）著色，則稱是（頂點(diǎn)）可染色。 為可著色的 219。圖的任意兩個(gè)頂點(diǎn)之間的最大距離，稱為是圖的直徑，記作。通常，我們都會(huì)去試著去找出一個(gè)最小的整數(shù)，使得有一個(gè)染色，即一個(gè)頂點(diǎn)染色，這個(gè)就成為圖的頂點(diǎn)所需的色數(shù)，表示作。 彩虹連通基本知識(shí)Chartrand，Johns等人首次提出了圖的彩虹連通性的概念。一個(gè)點(diǎn)染色圖的任意兩點(diǎn)之間有一條內(nèi)部頂點(diǎn)染不同顏色的路相連，則稱它是彩虹點(diǎn)連通的。對(duì)于彩虹邊連通和彩虹點(diǎn)聯(lián)通，一些例子表明它們的彩虹連通路并不相同。取個(gè)頂點(diǎn)不相交的三角形，并給它們中的每一個(gè)指定一個(gè)頂點(diǎn)，在指定點(diǎn)上添加一個(gè)完全圖。只要給條邊染色，比如說(shuō)，顏色1和三角形的其它邊的顏色2,3,4。事實(shí)上，這個(gè)新概念形成于政府機(jī)構(gòu)之間的信息傳遞。對(duì)的任何兩個(gè)頂點(diǎn)和，中的一條彩虹測(cè)地線是一條長(zhǎng)度為的彩虹路，則圖稱為強(qiáng)彩虹連通。顯然有：，這里和分別表示圖的直徑和邊數(shù)。 令是一個(gè)階的非平凡連通圖，則有：（1） 當(dāng)且僅當(dāng)是一個(gè)完全圖；（2） 當(dāng)且僅當(dāng)。（1）當(dāng)且僅當(dāng)是一個(gè)完全圖；（2）當(dāng)且僅當(dāng)；（3）當(dāng)且僅當(dāng)是一條n階的路。證明：初始化，然后只要，取一個(gè)頂點(diǎn)在的最小度至少為，將它添加到并通過(guò)刪除和它相鄰點(diǎn)集更新。 若是有最小度的連通圖，然后它有一個(gè)連通的生成子圖最小度為并有少于條邊。：定理的語(yǔ)句在是不準(zhǔn)確的，所以我們假定。我們最多只能添加的頂點(diǎn)和得到這么一個(gè)連接和也是一個(gè)強(qiáng)2階點(diǎn)集。我們進(jìn)一步把分成2份和，其中是那些在中至少有個(gè)相鄰的點(diǎn)。的頂點(diǎn)各自被染上不同的顏色。3 生活中的一些實(shí)際問(wèn)題 圖著色問(wèn)題的應(yīng)用—選課問(wèn)題類似于圖的邊染色的問(wèn)題，生活中的許多問(wèn)題都可以建立模型為圖的頂點(diǎn)著色問(wèn)題來(lái)處理?，F(xiàn)有10名學(xué)生選修了這些課程(如下所示)。 A3: MA, G, LA。A7: GT, MA, LA 。建立如下圖所示的模型，把課程看作為圖的頂點(diǎn)，兩頂點(diǎn)之間的連線當(dāng)且僅當(dāng)有某個(gè)學(xué)生同時(shí)選了這兩門課程。鄰接的兩個(gè)區(qū)域指的是它們有一段公共的邊界，而不僅僅是一個(gè)公共的交點(diǎn)。也有一些證明當(dāng)時(shí)被確立后來(lái)又被推翻，經(jīng)過(guò)了各種專家學(xué)者的一個(gè)多世紀(jì)的研究和證明，直到1976年才由兩位美國(guó)數(shù)學(xué)家通過(guò)電子計(jì)算機(jī)得以完全的證明。1879年，阿爾弗雷德希伍德卻發(fā)現(xiàn)了這個(gè)證明中存在了一些錯(cuò)誤，他對(duì)肯普的證明加以修改，就得到了現(xiàn)在的五色定理?？紤]的平面圖。設(shè)c是的5著色方案。例如，對(duì)任意圖，按任一順序進(jìn)行貪心著色，則每當(dāng)嘗試對(duì)某一頂點(diǎn)著色時(shí)，其鄰集中至多出現(xiàn)種色，因此總可從種顏色中挑選一中著在上。假如我們事先知道圖的一個(gè)著色為。首先是彩虹連通，如果一條路的邊分別染不同的顏色，那么這條邊染色路就是一條彩虹路。本文的概念定義部分介紹了，一個(gè)圖是連通的，當(dāng)且僅當(dāng)任意兩個(gè)頂點(diǎn)之間是連通的，并且由條內(nèi)部頂點(diǎn)不相交的路徑連通。因此，如果圖是連通的，那么。那么這樣的連通圖就是一個(gè)著名的亞族。類似的，對(duì)于，如果和相交，那么一條適合的路徑是一個(gè)點(diǎn)，這點(diǎn)在中。定理，證明：首先定義圖的一些子圖，其中。令是一些路的集合。接下來(lái)，先對(duì)每個(gè)定義一個(gè)邊染色。假設(shè)路徑是。情況：。情況：。情況：。的其余的邊染不同的新的顏色。顯然，對(duì)于，我們使用了種顏色，定理的到成立。最后，我們?cè)谇闆r到情況中驗(yàn)證，定理的到成立對(duì)于成立。這就完成了定理的證明，因此定理也就成