圖論電子科大楊春詳解演示文稿

圖論電子科大楊春詳解演示文稿1目前一頁\總數(shù)三十七頁\編于十三點（優(yōu)選）圖論電子科大楊春2目前二頁\總數(shù)三十七頁\編于十三點跟圖的邊著色問題一樣，生活中的很多問題，可以模型為圖的頂點著色問題來處理。例如課程安排問題。(一)、相關(guān)概念課程安排問題：某大學(xué)數(shù)學(xué)系要為這個夏季安排課程表。要開設(shè)的課程為：圖論(GT),統(tǒng)計學(xué)(S),線性代數(shù)(LA),高等微積分(AC),幾何學(xué)(G),和近世代數(shù)(MA)?，F(xiàn)有10名學(xué)生(如下所示)需要選修這些課程。根據(jù)這些信息，確定開設(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;3目前三頁\總數(shù)三十七頁\編于十三點

A10:GT,S。把課程模型為圖G的頂點，兩頂點連線當(dāng)且僅當(dāng)有某個學(xué)生同時選了這兩門課程。GTMAGACLAS選課狀態(tài)圖4目前四頁\總數(shù)三十七頁\編于十三點如果我們用同一顏色給同一時段的課程頂點染色，那么，問題轉(zhuǎn)化為在狀態(tài)圖中求所謂的點色數(shù)問題。GTMAGACLAS選課狀態(tài)圖5目前五頁\總數(shù)三十七頁\編于十三點定義1設(shè)G是一個圖，對G的每個頂點著色，使得相鄰頂點著不同顏色，稱為對G的正常頂點著色；如果用k種顏色可以對G進行正常頂點著色，稱G可k正常頂點著色；對圖G正常頂點著色需要的最少顏色數(shù)，稱為圖G的點色數(shù)。圖G的點色數(shù)用表示。例1說明下圖的點色數(shù)是4。GTMAGACLASGTMAGACLAS6目前六頁\總數(shù)三十七頁\編于十三點解：一方面，由圖的結(jié)構(gòu)特征容易知道另一方面，通過具體著色，用4種顏色可以得到該圖的一種正常點著色，則：GTMAGACLAS所以，7目前七頁\總數(shù)三十七頁\編于十三點注：對圖的正常頂點著色，帶來的是圖的頂點集合的一種劃分方式。所以，對應(yīng)的實際問題也是分類問題。屬于同一種顏色的頂點集合稱為一個色組，它們彼此不相鄰接，所以又稱為點獨立集。用點色數(shù)種顏色對圖G正常著色，稱為對圖G的最優(yōu)點著色。定義2色數(shù)為k的圖稱為k色圖。(二)、圖的點色數(shù)的幾個結(jié)論定理1對任意的圖G，有：分析：事實上，定理結(jié)論容易想到，因為任意一個頂點度數(shù)至多為Δ，因此，正常著色過程中，其鄰點最多用去Δ種顏色，所以，至少還有一種色可供該點正常著色使用。8目前八頁\總數(shù)三十七頁\編于十三點證明：我們對頂點數(shù)作數(shù)學(xué)歸納證明。當(dāng)n=1時，結(jié)論顯然成立。設(shè)對頂點數(shù)少于n的圖來說，定理結(jié)論成立?？紤]一般的n階圖G。任取v∈V(G),令G1=G-v，由歸納假設(shè)：設(shè)п是G1的一種Δ(G)+1正常點著色方案，因為v的鄰點在п下至多用去Δ(G)種色，所以給v染上其鄰點沒有用過的色，就把п擴充成了G的Δ(G)+1著色方案。對于G來說，可以給出其Δ(G)+1正常點著色算法。9目前九頁\總數(shù)三十七頁\編于十三點G的Δ(G)+1正常點著色算法

設(shè)G=(V,E),V=｛v1,v2,…,vn｝,色集合C=｛1,2,…,Δ+1｝,著色方案為п。(1)令п(v1)=1,i=1;(2)若i=n,則停止；否則令：

設(shè)k為C-C(vi+1)中的最小整數(shù)，令(3)令i=i+1,轉(zhuǎn)(2)。10目前十頁\總數(shù)三十七頁\編于十三點

例2給出下圖的Δ+1正常點著色。v5v4v3v2v1v6

解：色集C=｛1,2,3,4,5｝11目前十一頁\總數(shù)三十七頁\編于十三點v5v4v3v2v1v6v5(2)v4(1)v3(3)v2(2)v1(1)v6(4)12目前十二頁\總數(shù)三十七頁\編于十三點v5v4v3v2v1v6

注:(1)不能通過上面算法求出色數(shù)，例如，根據(jù)上面算法，我們求出了一個4色方案，但G是3色圖：

(2)Welsh—Powell稍微對上面算法做了一個修改，著色時按所謂最大度優(yōu)先策略，即使用上面算法時，按頂點度數(shù)由大到小的次序著色。這樣的著色方案起到了對上面算法的一個改進作用。13目前十三頁\總數(shù)三十七頁\編于十三點

對于簡單圖G來說，數(shù)學(xué)家布魯克斯(Brooks)給出了一個對定理1的色數(shù)改進界。這就是下面著名的布魯克斯定理。

定理2(布魯克斯，1941)若G是連通的單圖，并且它既不是奇圈，又不是完全圖，則：

數(shù)學(xué)家羅瓦斯在1973年給出了如下證明。

證明：不失一般性，我們可以假設(shè)G是正則的，2連通的，最大度Δ≥3的簡單圖。原因如下：(1)容易證明：若G是非正則連通單圖，最大度是Δ，則

事實上，我們可以對G的頂點數(shù)作數(shù)學(xué)歸納證明：14目前十四頁\總數(shù)三十七頁\編于十三點

當(dāng)n=1時，結(jié)論顯然成立；

設(shè)對于階數(shù)小于n的簡單非正則連通單圖來說，結(jié)論成立。下設(shè)G是階數(shù)為n的非正則連通單圖。

設(shè)u是G中頂點，且d(u)=δ<Δ，考慮G1=G-u

若G1是正則單圖，則Δ(G1)=Δ(G)-1。于是G1是可Δ(G)頂點正常著色的，從而，G是可Δ(G)正常頂點著色的；

若G1是非正則單圖，則由數(shù)學(xué)歸納，G1是可Δ(G)頂點正常著色的，從而，G是可Δ(G)正常頂點著色的。(2)容易證明：若G是1連通單圖，最大度是Δ，則15目前十五頁\總數(shù)三十七頁\編于十三點(3)Δ(G)≤2由條件，G只可能為偶圈。所以定理結(jié)論顯然成立。

所以，下面只需證明：假設(shè)G是正則的，2連通的，最大度Δ≥3的簡單圖，且不是完全圖或奇圈，有：

分兩步完成證明。1)在上面條件下，我們證明：G中存在三點x1,x2,xn,使得G-｛x1,x2｝連通，x1與x2不鄰接，但x1,x2與xn均鄰接；x1x2xnG16目前十六頁\總數(shù)三十七頁\編于十三點

情形1設(shè)G是3連通的正則非完全圖。

對于G中點xn,顯然在其鄰點中存在兩個不鄰接頂點x1與x2,使得G-｛x1,x2｝連通。

情形2設(shè)G是連通度為2的正則非完全圖。

此時，存在點xn,使得G-xn連通且有割點v,于是G-xn至少含有兩個塊。vG-xn塊塊塊17目前十七頁\總數(shù)三十七頁\編于十三點

由于G本身2連通，所以G-xn的每個僅含有一個割點的塊中均有點與xn鄰接。設(shè)分屬于H1與H2中的點x1與x2，它們與xn鄰接。由于x1與x2分屬于不同塊，所以x1與x2不鄰接。又顯然G-｛x1,x2｝連通。2)對G中頂點進行如下排序：

令xn-1∈V(G)-｛x1,x2,xn｝且與xn鄰接；xn-2∈V(G)-｛x1,x2,xn，xn-1｝且與xn或xn-1鄰接；xn-3∈V(G)-｛x1,x2,xn，xn-1,xn-2｝且與xn或xn-1或xn-2鄰接；

不斷這樣作下去，可得到G的頂點排序：x1,x2,…,xn18目前十八頁\總數(shù)三十七頁\編于十三點

該頂點序列的特征是，對于1≦i≦n-1,xi與某個xi+k鄰接。

把著色算法用于G，按照上面頂點排序著色，容易知道，用Δ(G)種顏色可以完成G的正常點著色。

對于簡單圖的點色數(shù)，還可以在定理2的基礎(chǔ)上獲得改進。定義3設(shè)G是至少有一條邊的簡單圖，定義：其中N(u)為G中點u的鄰域。稱Δ2(G)為G的次大度。19目前十九頁\總數(shù)三十七頁\編于十三點

如果令：那么，例如：求下面圖的次大度Δ2(G)G1G220目前二十頁\總數(shù)三十七頁\編于十三點

解：(1)G1v5v4v3v2v1G2v5v4v3v2v1v8v7v6v9(2)21目前二十一頁\總數(shù)三十七頁\編于十三點G2v5v4v3v2v1v8v7v6v9

注：由次大度的定義知：Δ2(G)≦Δ(G)

定理3設(shè)G是非空簡單圖，則：

注：定理3是對定理2的一個改進！22目前二十二頁\總數(shù)三十七頁\編于十三點G2v5v4v3v2v1v8v7v6v9

例如：對下面單圖來說，由定理2得：

而由定理3得：

推論：設(shè)G是非空簡單圖，若G中最大度點互不鄰接，則有：23目前二十三頁\總數(shù)三十七頁\編于十三點

1、四色定理(三)、四色與五色定理1852年，剛畢業(yè)于倫敦大學(xué)的格斯里(1831—1899)發(fā)現(xiàn)：給一張平面地圖正常著色，至少需要4種顏色。這就是著名的4色定理。格斯里把他的證明通過他弟弟轉(zhuǎn)交給著名數(shù)學(xué)家摩爾根，引起摩爾根極大興趣并于當(dāng)天給數(shù)學(xué)家哈密爾頓寫了封相關(guān)信件。但沒有引起哈密爾頓的注意。直到1878年，在英國數(shù)學(xué)會議上，數(shù)學(xué)家凱萊才再一次提到4色問題。24目前二十四頁\總數(shù)三十七頁\編于十三點1879年7月，業(yè)余數(shù)學(xué)家肯普(1849---1922）在英國自然雜志上宣稱證明了4色定理?？掀帐莿P萊在劍橋大學(xué)的學(xué)生。

1890年，英國數(shù)學(xué)家希伍德發(fā)表地圖染色定理文章，通過構(gòu)造反例，指出了肯普證明中的缺陷。后來，希伍德一直研究4色問題60年。泰特在此期間也研究4色問題，但其證明被托特否定。希伍德文章之后，4色問題研究進程開始走向停滯。到了20世紀(jì)，美國數(shù)學(xué)家比爾荷夫提出可約性概念，在此基礎(chǔ)上，德國數(shù)學(xué)家Heesch(1906—1995)認(rèn)為，可以通過尋找所謂的不可約構(gòu)形來證明4色定理。25目前二十五頁\總數(shù)三十七頁\編于十三點Heesch估計不可約構(gòu)形集合可能包含10000個元素，手工驗證不太可能。于是他給出了一種可用計算機來驗證的方法。20世紀(jì)70年代，Haken和他的學(xué)生Appel著力用計算機方法證明4色定理，借助于Appel在編程方面的深厚功底。他們于1976年6月終于成功解決了尋找不可約構(gòu)形集合中的元素，宣告4色定理的成功證明。數(shù)學(xué)家托特在圖論頂級刊物《圖論雜志》上寫了一首詩：WolfgangHaken

重重打擊著巨妖

一次！兩次！三次！四次！

他說：“妖怪已經(jīng)不存在了.”26目前二十六頁\總數(shù)三十七頁\編于十三點

2、五色定理

定理4(希伍德)每個平面圖是5可著色的。

根據(jù)平面圖和其對偶圖的關(guān)系，上面定理等價于每個簡單平面圖是5可頂點正常著色的。

證明：我們對圖的頂點作數(shù)學(xué)歸納證明。

當(dāng)n=1時，結(jié)論顯然。

設(shè)n=k時，結(jié)論成立?？紤]n=k+1的平面圖G。

因G是簡單平面圖，所以δ(G)≦5

設(shè)d(u)=δ(G)≦5。27目前二十七頁\總數(shù)三十七頁\編于十三點

令G1=G–u。由歸納假設(shè)，G1是5可頂點正常著色的。設(shè)п是G1的5著色方案。(1)如果d(u)=δ(G)<5,顯然п可以擴充為G的5正常頂點著色；

(2)如果d(u)=δ(G)=5,分兩種情況討論。

情形1在п下，如果u的鄰接點中，至少有兩個頂點著相同顏色，則容易知道，п可以擴充為G的5正常頂點著色；

情形2在п下，設(shè)u的鄰接點中，5個頂點著了5種不同顏色。28目前二十八頁\總數(shù)三十七頁\編于十三點

不失一般性，設(shè)п(xi)=i(1≦i≦5)。x5x4x3x2x1u

設(shè)H(i,j)表示著i和j色的點在G1中的點導(dǎo)出子圖。

如果x1與x3屬于H(1,3)的不同分支。則通過交換含x1的分支中的著色順序，可得到G1的新正常點著色方案，使x1與x3著同色，于是由情形1，可以得到G的5正常頂點著色方案；29目前二十九頁\總數(shù)三十七頁\編于十三點

設(shè)x1與x3屬于H(1,3)的相同分支。x5x4x3x2x1u3131

在上面假設(shè)下，x2與x4必屬于H(2,4)的不同分支。否則，將會得到H(1,3)與H(2,4)的交叉點。因此，п可以擴充為G的5正常頂點著色。30目前三十頁\總數(shù)三十七頁\編于十三點(四)、頂點著色的應(yīng)用

圖的正常頂點著色對應(yīng)的實際問題是“劃分”問題。例1課程安排問題：某大學(xué)數(shù)學(xué)系要為這個夏季安排課程表。所要開設(shè)的課程為：圖論(GT),統(tǒng)計學(xué)(S),線性代數(shù)(LA),高等微積分(AC),幾何學(xué)(G),和近世代數(shù)(MA)。現(xiàn)有10名學(xué)生(如下所示)需要選修這些課程。根據(jù)這些信息，確定開設(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;31目前三十一頁\總數(shù)三十七頁\編于十三點

A10:GT,S。解：把課程模型為圖G的頂點，兩頂點連線當(dāng)且僅當(dāng)有某個學(xué)生同時選了這兩門課程。GTMAGACLAS選課狀態(tài)圖32目前三十二頁\總數(shù)三十七頁\編于十三點如果