【正文】 順序進(jìn)行貪心著色，則每當(dāng)嘗試對某一頂點(diǎn)著色時，其鄰集中至多出現(xiàn)種色，因此總可從種顏色中挑選一中著在上。情形1 在c下，如果在與相鄰接點(diǎn)中，至少有兩個頂點(diǎn)著相同顏色，則容易知道，c可以擴(kuò)充為的5正常頂點(diǎn)著色；情形2在c下，設(shè)在與的相鄰接點(diǎn)中，5個頂點(diǎn)著了5種不同顏色。設(shè)c是的5著色方案。設(shè)，令?？紤]的平面圖。當(dāng)時，結(jié)論顯然。希伍德卻發(fā)現(xiàn)了這個證明中存在了一些錯誤，他對肯普的證明加以修改，就得到了現(xiàn)在的五色定理?？掀战o出了四色定理的一個證明方法，被當(dāng)時的人們所接受，但11年后，珀西1879年，阿爾弗雷德把一個平面分成若干的區(qū)域，給這些區(qū)域進(jìn)行染色，并使任意相鄰的區(qū)域染上不同的染色，滿足這些條件所需的顏色數(shù)最多為五種。也有一些證明當(dāng)時被確立后來又被推翻，經(jīng)過了各種專家學(xué)者的一個多世紀(jì)的研究和證明，直到1976年才由兩位美國數(shù)學(xué)家通過電子計算機(jī)得以完全的證明。這就是著名的4色定理。鄰接的兩個區(qū)域指的是它們有一段公共的邊界，而不僅僅是一個公共的交點(diǎn)。 儲藏問題一家公司制造種化學(xué)制品，其中某些制品是互不相容的，如果它們互相接觸，則會引起爆炸，作為一種預(yù)防措施，公司希望把它的倉庫分為間隔，以便把不相容的化學(xué)制品儲藏在不同的間隔里，試問：這個倉庫至少應(yīng)該分成幾個間隔？問題處理：構(gòu)造一個圖，其頂點(diǎn)集是兩個頂點(diǎn)和相連當(dāng)且僅黨化學(xué)制品和互不相容，則倉庫的最小間隔數(shù)即為的頂點(diǎn)數(shù)。建立如下圖所示的模型，把課程看作為圖的頂點(diǎn)，兩頂點(diǎn)之間的連線當(dāng)且僅當(dāng)有某個學(xué)生同時選了這兩門課程。 A9: AC, S, LA。A7: GT, MA, LA 。 A5: AC, LA, S 。 A3: MA, G, LA。(學(xué)生用Ai表示）A1: LA, S ?，F(xiàn)有10名學(xué)生選修了這些課程(如下所示)。課程安排問題：某大學(xué)數(shù)學(xué)系要為這個夏季安排課程表。3 生活中的一些實(shí)際問題 圖著色問題的應(yīng)用—選課問題類似于圖的邊染色的問題，生活中的許多問題都可以建立模型為圖的頂點(diǎn)著色問題來處理。的頂點(diǎn)不被染色。的頂點(diǎn)各自被染上不同的顏色。 我們也把L劃分成兩個部分和，其中是那些具有在中至少一個鄰點(diǎn)的頂點(diǎn)。我們進(jìn)一步把分成2份和，其中是那些在中至少有個相鄰的點(diǎn)。令和考慮分區(qū)，其中為直接支配的頂點(diǎn)集和是不被支配的點(diǎn)集。我們最多只能添加的頂點(diǎn)和得到這么一個連接和也是一個強(qiáng)2階點(diǎn)集。我們可以假設(shè)有小于條邊。：定理的語句在是不準(zhǔn)確的，所以我們假定。這個生成子圖的每個連接的部分都有至少有個頂點(diǎn)。 若是有最小度的連通圖，然后它有一個連通的生成子圖最小度為并有少于條邊。顯然，這個過程持續(xù)了至多為步。證明：初始化，然后只要，取一個頂點(diǎn)在的最小度至少為，將它添加到并通過刪除和它相鄰點(diǎn)集更新。我們所說的2階點(diǎn)集k強(qiáng)如果每一個并非由它支配的頂點(diǎn)有至少存在這是由它支配相鄰的。，存在一個連通圖使得。（1）當(dāng)且僅當(dāng)是一個完全圖；（2）當(dāng)且僅當(dāng)；（3）當(dāng)且僅當(dāng)是一條n階的路。 令，是連通圖的兩個頂點(diǎn)，如果距離，那么不存在包含和作為內(nèi)部定點(diǎn)的測地線。 令是一個階的非平凡連通圖，則有：（1） 當(dāng)且僅當(dāng)是一個完全圖；（2） 當(dāng)且僅當(dāng)。彩虹頂點(diǎn)連通數(shù)，強(qiáng)彩虹頂點(diǎn)連通數(shù)（簡單有限無向圖），對于任意非平凡連通圖有。顯然有：，這里和分別表示圖的直徑和邊數(shù)。這種情況下，染色稱為的強(qiáng)彩虹染色。對的任何兩個頂點(diǎn)和，中的一條彩虹測地線是一條長度為的彩虹路，則圖稱為強(qiáng)彩虹連通。我們不得不采用路徑最少的渠道，彩虹連通性就可以解決這個問題。事實(shí)上，這個新概念形成于政府機(jī)構(gòu)之間的信息傳遞。由于自然組合的概念，彩虹邊連通和彩虹點(diǎn)連通吸引了許多學(xué)者的興趣。只要給條邊染色，比如說，顏色1和三角形的其它邊的顏色2,3,4。事實(shí)上，的著色只要求每個切點(diǎn)有不同的顏色。取個頂點(diǎn)不相交的三角形，并給它們中的每一個指定一個頂點(diǎn)，在指定點(diǎn)上添加一個完全圖。例如，而。對于彩虹邊連通和彩虹點(diǎn)聯(lián)通，一些例子表明它們的彩虹連通路并不相同。一個簡單的發(fā)現(xiàn)是如果一個圖有個頂點(diǎn)，則有；當(dāng)且僅當(dāng)它是一個完全圖時有。一個點(diǎn)染色圖的任意兩點(diǎn)之間有一條內(nèi)部頂點(diǎn)染不同顏色的路相連，則稱它是彩虹點(diǎn)連通的。彩虹邊連通數(shù)就是一個連通圖使它構(gòu)成彩虹邊連通所需要的最小的顏色數(shù)，稱為記做。 彩虹連通基本知識Chartrand，Johns等人首次提出了圖的彩虹連通性的概念。 若把圖的一個邊染色看作是一個映射，并令它的任意兩條相鄰的邊和，滿足。通常，我們都會去試著去找出一個最小的整數(shù)，使得有一個染色，即一個頂點(diǎn)染色，這個就成為圖的頂點(diǎn)所需的色數(shù)，表示作。 若把圖的一個頂點(diǎn)染色看作是一個映射，并令它的任意兩個相鄰的點(diǎn)和都滿足。圖的任意兩個頂點(diǎn)之間的最大距離，稱為是圖的直徑，記作。 為可著色的 222。 為可著色的 219。例： 為1可著色的 219。如果有一個（頂點(diǎn)）著色，則稱是（頂點(diǎn)）可染色。圖的種顏色的正常（頂點(diǎn)）染色稱為（頂點(diǎn)）染色色。其中使得圖是邊連通的最大整數(shù)稱為的邊連通度，記為。其中使得圖是連通時的最大整數(shù)稱作的連通度，記作。如果無向圖中的任一對頂點(diǎn)之間都是連通的，則稱圖是連通圖，反之，如果一個無向圖不是連通的，則稱作非連通圖。一條路上的邊數(shù)稱為路的長度，記，稱是一條和之間的一條路。圖是一條路，如果其頂點(diǎn)集和邊集分別為，這里的均互不相同。不與其它的任何頂點(diǎn)鄰接的頂點(diǎn)，即度為0的頂點(diǎn)稱為孤立頂點(diǎn)。 假設(shè)有兩個圖和，如果兩個圖的頂點(diǎn)集有這樣的關(guān)系，是的一個子集，邊集是的一個子集，那么就稱圖是圖的子圖。若是圖中所有的邊都是無向邊，這類圖稱為無向圖。自環(huán)是兩端連接著同一頂點(diǎn)的邊，既不含平行邊也不含自環(huán)的圖稱為簡單圖。此外，僅有一個頂點(diǎn)的圖稱為平凡圖，即平凡圖的階，相反，階的圖稱為非平凡圖。一個圖的階就是圖的頂點(diǎn)個數(shù)，記作。并且認(rèn)為和的交集為空集。顯然，我們希望使用不同渠道的數(shù)量降至最低，用彩虹染色的方法就可以解決這個問題。在生產(chǎn)管理、軍事、交通運(yùn)輸、計算機(jī)網(wǎng)絡(luò)等許多的領(lǐng)域圖論的知識在其中都有著重要的應(yīng)用，彩虹連接數(shù)在網(wǎng)絡(luò)領(lǐng)域也有很多的應(yīng)用。幾百年來，很多的數(shù)學(xué)家們都為此花費(fèi)了大量的心血去研究。1852年，格里斯注意到可以用4種顏色來為美國地圖進(jìn)行染