【文章內(nèi)容簡介】 C),近世代數(shù)(MA),圖論(GT)和統(tǒng)計(jì)學(xué)(S)?，F(xiàn)有10名學(xué)生選修了這些課程(如下所示)。依據(jù)這些信息，使這些課程的開設(shè)所需要的最少時(shí)間段數(shù)得以確定，使得學(xué)生不會發(fā)生選課沖突。(學(xué)生用Ai表示）A1: LA, S 。 A2: MA, LA, G 。 A3: MA, G, LA。A4: G, LA, AC 。 A5: AC, LA, S 。 A6: G, AC。A7: GT, MA, LA 。 A8: LA,GT, S 。 A9: AC, S, LA。A10：GT，S。建立如下圖所示的模型，把課程看作為圖的頂點(diǎn)，兩頂點(diǎn)之間的連線當(dāng)且僅當(dāng)有某個學(xué)生同時(shí)選了這兩門課程。圖 2如果我們用相同的顏色給同一時(shí)段進(jìn)行的課程頂點(diǎn)染色，那么，問題轉(zhuǎn)化為在狀態(tài)圖中求所謂的點(diǎn)色數(shù)問題。 儲藏問題一家公司制造種化學(xué)制品，其中某些制品是互不相容的，如果它們互相接觸，則會引起爆炸，作為一種預(yù)防措施，公司希望把它的倉庫分為間隔，以便把不相容的化學(xué)制品儲藏在不同的間隔里，試問：這個倉庫至少應(yīng)該分成幾個間隔？問題處理：構(gòu)造一個圖，其頂點(diǎn)集是兩個頂點(diǎn)和相連當(dāng)且僅黨化學(xué)制品和互不相容，則倉庫的最小間隔數(shù)即為的頂點(diǎn)數(shù)。4 彩虹染色方面的著名定理 四色定理如果在平面上劃出一些鄰接的有限區(qū)域，那么可以用四種顏色來給這些區(qū)域染色，使得每兩個鄰接區(qū)域染的顏色都不相同；另一個通俗的說法是：每個地圖都可以用少于四種的顏色來染色，而且沒有兩個鄰接區(qū)域的顏色相同。鄰接的兩個區(qū)域指的是它們有一段公共的邊界，而不僅僅是一個公共的交點(diǎn)。 1852年，剛畢業(yè)于倫敦大學(xué)的格斯里(1831—1899)發(fā)現(xiàn)：給一張平面地圖正常著色，至少需要4種顏色。這就是著名的4色定理。當(dāng)這個定理被提出后，很多科學(xué)家都希望能對此進(jìn)行證明，但都沒有成功。也有一些證明當(dāng)時(shí)被確立后來又被推翻，經(jīng)過了各種專家學(xué)者的一個多世紀(jì)的研究和證明，直到1976年才由兩位美國數(shù)學(xué)家通過電子計(jì)算機(jī)得以完全的證明。但這個證明一直受到一些數(shù)學(xué)家的質(zhì)疑，因?yàn)橹钡浆F(xiàn)在都沒有數(shù)學(xué)家不借助計(jì)算機(jī)能夠證明。把一個平面分成若干的區(qū)域，給這些區(qū)域進(jìn)行染色，并使任意相鄰的區(qū)域染上不同的染色，滿足這些條件所需的顏色數(shù)最多為五種。五色定理稍弱于比四色定理，但是它證明起來就容易多了。1879年，阿爾弗雷德布雷肯普給出了四色定理的一個證明方法，被當(dāng)時(shí)的人們所接受，但11年后，珀西約翰希伍德卻發(fā)現(xiàn)了這個證明中存在了一些錯誤，他對肯普的證明加以修改，就得到了現(xiàn)在的五色定理。 我們對圖的頂點(diǎn)作數(shù)學(xué)歸納證明。當(dāng)時(shí)，結(jié)論顯然。設(shè)時(shí)，結(jié)論成立?？紤]的平面圖。因是平面圖，所以。設(shè)，令。由歸納假設(shè)，是可用5種顏色正常頂點(diǎn)染色的。設(shè)c是的5著色方案。 (1) 如果, 顯然c可以擴(kuò)充為的5正常頂點(diǎn)染色； (2) 如果, 分兩種情況討論。情形1 在c下，如果在與相鄰接點(diǎn)中，至少有兩個頂點(diǎn)著相同顏色，則容易知道，c可以擴(kuò)充為的5正常頂點(diǎn)著色；情形2在c下，設(shè)在與的相鄰接點(diǎn)中，5個頂點(diǎn)著了5種不同顏色。圖 3 貪心（greedy）著色法 用色1，2，…逐步（按某一頂點(diǎn)排序）對每個頂點(diǎn)進(jìn)行正常著色，每次選用盡可能少的顏色進(jìn)行著色。例如，對任意圖，按任一順序進(jìn)行貪心著色，則每當(dāng)嘗試對某一頂點(diǎn)著色時(shí)，其鄰集中至多出現(xiàn)種色，因此總可從種顏色中挑選一中著在上。整個著色過程至多用種顏色，故為可著色的。從而得到推論。顯然，貪心著色法所用的顏色數(shù)完全取決于著色的順序，即頂點(diǎn)的一個排序。假如我們事先知道圖的一個著色為。按 的順序任作一頂點(diǎn)排序（同一色集內(nèi)隨意排序），按此順序進(jìn)行貪心著色，顯然恰好使用了種顏色。因此，設(shè)法構(gòu)想一適當(dāng)?shù)捻旤c(diǎn)排序進(jìn)行貪心著色，往往可能得到一個較好的著色結(jié)果（如Brooks定理之證明）。5 特殊圖類的彩虹點(diǎn)染色在討論廣義圖之前，我們先來了解幾個定義。首先是彩虹連通，如果一條路的邊分別染不同的顏色，那么這條邊染色路就是一條彩虹路。如果圖中任意兩個頂點(diǎn)之間是連通的，并且由條內(nèi)部頂點(diǎn)不相交的彩虹路連通，那么邊染色圖就是彩虹連通的，其中。接下來，我們給出彩虹連通數(shù)的定義：若存在圖的一個邊染色，使用種顏色就能夠使得圖彩虹連通，其中是最小的整數(shù)，那么彩虹連通數(shù)為：。對于連通圖的彩虹連通數(shù)，記作，即。本文的概念定義部分介紹了，一個圖是連通的，當(dāng)且僅當(dāng)任意兩個頂點(diǎn)之間是連通的，并且由條內(nèi)部頂點(diǎn)不相交的路徑連通。因此，前面定義的僅僅是針對連通圖而言的。我們繼續(xù)說明，對于，等人證明了，如果圖的階數(shù)為，那么，如果圖是連通的，即，那么。等人證明了，如果圖的最小度為，那么，并且證明了對于所有階數(shù)為，最小度為的連通圖都是適用的。因此，如果圖是連通的，那么。另外，上文有說明圖是連通的，即，可以采用改善后的界，即。首先，了解連通圖：定理1 如果是一個連通圖，頂點(diǎn)，那么。在情況中，如果圖是一個連通串并聯(lián)圖是一個簡單圖，從三個頂點(diǎn)開始，反復(fù)運(yùn)用一個操作序列，這個序列是一個分支，由一條邊變換成雙條邊，反復(fù)增加分支邊。那么這樣的連通圖就是一個著名的亞族。證明定理，我們是通過先證明一個強(qiáng)有力的定理的結(jié)論，然后間接證明定理。定理2如果是一個連通圖，頂點(diǎn)，那么存在圖的一個邊染色，至多是種顏色滿足以下結(jié)論： 對于任意兩個頂點(diǎn)，這里存在兩條不相交的彩虹路； 對于任意一個頂點(diǎn)，任意集合，且，這里兩條彩虹路，只有頂點(diǎn)相同； 對于任意兩個集合，且，這里的兩條彩虹路不相交。對于而言，如果，那么其中的一條路徑取自頂點(diǎn)。類似的，對于，如果和相交，那么一條適合的路徑是一個點(diǎn)，這點(diǎn)在中。顯然，定理是來自定理，所以先證明定理，證明之前先給出一個定理。定理3令是一個連通圖。對于任意的頂點(diǎn)和任意集合，這里有從到的條路徑，使得對于其中的任意兩條路，僅僅只有一個共同頂點(diǎn)。定理，證明：首先定義圖的一些子圖，其中。因?yàn)槿我獾倪B通圖都含有一個頂點(diǎn)至少是的圈，于是令是圖的一個頂點(diǎn)至少是的圈。現(xiàn)在，假設(shè)找到這樣一些圖，如果，那么集合，否則的話，這里存在一個頂點(diǎn)。根據(jù)定理3，發(fā)出路到，這里的每對路徑僅僅匯集與，那些路是的一個細(xì)分。令是一些路的集合。重復(fù)這個過程，直到結(jié)束。對于每個，歸納證明了，存在一個的邊染色，至多使用種顏色，使得定理中的到的性