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

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

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

設(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當(dāng)前10頁(yè)，總共37頁(yè)。

例2給出下圖的Δ+1正常點(diǎn)著色。v5v4v3v2v1v6

解：色集C=｛1,2,3,4,5｝11當(dāng)前11頁(yè)，總共37頁(yè)。v5v4v3v2v1v6v5(2)v4(1)v3(3)v2(2)v1(1)v6(4)12當(dāng)前12頁(yè)，總共37頁(yè)。v5v4v3v2v1v6

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

(2)Welsh—Powell稍微對(duì)上面算法做了一個(gè)修改，著色時(shí)按所謂最大度優(yōu)先策略，即使用上面算法時(shí)，按頂點(diǎn)度數(shù)由大到小的次序著色。這樣的著色方案起到了對(duì)上面算法的一個(gè)改進(jìn)作用。13當(dāng)前13頁(yè)，總共37頁(yè)。

對(duì)于簡(jiǎn)單圖G來(lái)說(shuō)，數(shù)學(xué)家布魯克斯(Brooks)給出了一個(gè)對(duì)定理1的色數(shù)改進(jìn)界。這就是下面著名的布魯克斯定理。

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

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

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

事實(shí)上，我們可以對(duì)G的頂點(diǎn)數(shù)作數(shù)學(xué)歸納證明：14當(dāng)前14頁(yè)，總共37頁(yè)。

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

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

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

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

若G1是非正則單圖，則由數(shù)學(xué)歸納，G1是可Δ(G)頂點(diǎn)正常著色的，從而，G是可Δ(G)正常頂點(diǎn)著色的。(2)容易證明：若G是1連通單圖，最大度是Δ，則15當(dāng)前15頁(yè)，總共37頁(yè)。(3)Δ(G)≤2由條件，G只可能為偶圈。所以定理結(jié)論顯然成立。

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

分兩步完成證明。1)在上面條件下，我們證明：G中存在三點(diǎn)x1,x2,xn,使得G-｛x1,x2｝連通，x1與x2不鄰接，但x1,x2與xn均鄰接；x1x2xnG16當(dāng)前16頁(yè)，總共37頁(yè)。

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

對(duì)于G中點(diǎn)xn,顯然在其鄰點(diǎn)中存在兩個(gè)不鄰接頂點(diǎn)x1與x2,使得G-｛x1,x2｝連通。

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

此時(shí)，存在點(diǎn)xn,使得G-xn連通且有割點(diǎn)v,于是G-xn至少含有兩個(gè)塊。vG-xn塊塊塊17當(dāng)前17頁(yè)，總共37頁(yè)。

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

令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的頂點(diǎn)排序：x1,x2,…,xn18當(dāng)前18頁(yè)，總共37頁(yè)。

該頂點(diǎn)序列的特征是，對(duì)于1≦i≦n-1,xi與某個(gè)xi+k鄰接。

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

對(duì)于簡(jiǎn)單圖的點(diǎn)色數(shù)，還可以在定理2的基礎(chǔ)上獲得改進(jìn)。定義3設(shè)G是至少有一條邊的簡(jiǎn)單圖，定義：其中N(u)為G中點(diǎn)u的鄰域。稱Δ2(G)為G的次大度。19當(dāng)前19頁(yè)，總共37頁(yè)。

如果令：那么，例如：求下面圖的次大度Δ2(G)G1G220當(dāng)前20頁(yè)，總共37頁(yè)。

解：(1)G1v5v4v3v2v1G2v5v4v3v2v1v8v7v6v9(2)21當(dāng)前21頁(yè)，總共37頁(yè)。G2v5v4v3v2v1v8v7v6v9

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

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

注：定理3是對(duì)定理2的一個(gè)改進(jìn)！22當(dāng)前22頁(yè)，總共37頁(yè)。G2v5v4v3v2v1v8v7v6v9

例如：對(duì)下面單圖來(lái)說(shuō)，由定理2得：

而由定理3得：

推論：設(shè)G是非空簡(jiǎn)單圖，若G中最大度點(diǎn)互不鄰接，則有：23當(dāng)前23頁(yè)，總共37頁(yè)。

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

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

重重打擊著巨妖

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

他說(shuō)：“妖怪已經(jīng)不存在了.”26當(dāng)前26頁(yè)，總共37頁(yè)。

2、五色定理

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

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

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

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

設(shè)n=k時(shí)，結(jié)論成立。考慮n=k+1的平面圖G。

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

設(shè)d(u)=δ(G)≦5。27當(dāng)前27頁(yè)，總共37頁(yè)。

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

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

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

情形2在п下，設(shè)u的鄰接點(diǎn)中，5個(gè)頂點(diǎn)著了5種不同顏色。28當(dāng)前28頁(yè)，總共37頁(yè)。

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

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

如果x1與x3屬于H(1,3)的不同分支。則通過(guò)交換含x1的分支中的著色順序，可得到G1的新正常點(diǎn)著色方案，使x1與x3著同色，于是由情形1，可以得到G的5正常頂點(diǎn)著色方案；29當(dāng)前29頁(yè)，總共37頁(yè)。

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

在上面假設(shè)下，x2與x4必屬于H(2,4)的不同分支。否則，將會(huì)得到H(1,3)與H(2,4)的交叉點(diǎn)。因此，п可以擴(kuò)充為G的5正常頂點(diǎn)著色。30當(dāng)前30頁(yè)，總共37頁(yè)。(四)、頂點(diǎn)著色的應(yīng)用

圖的正常頂點(diǎn)著色對(duì)應(yīng)的實(shí)際問(wèn)題是“劃分”問(wèn)題。例1課程安排問(wèn)題：某大學(xué)數(shù)學(xué)系要為這個(gè)夏季安排課程表。所要開(kāi)設(shè)的課程為：圖論(GT),統(tǒng)計(jì)學(xué)(S),線性代數(shù)(LA),高等微積分(AC),幾何學(xué)(G),和近世代數(shù)(MA)?，F(xiàn)有10名學(xué)生(如下所示)需要選修這些課程。根據(jù)這些信息，確定開(kāi)設(shè)這些課程所需要的最少時(shí)間段數(shù)，使得學(xué)生選課不會(huì)發(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當(dāng)前31頁(yè)，總共37頁(yè)。

A10:GT,S。解：把課程模型為圖G的頂點(diǎn)，兩頂點(diǎn)連線當(dāng)且僅當(dāng)有某個(gè)學(xué)生同時(shí)選了這兩門課程。GTMAGACLAS選課狀態(tài)圖32當(dāng)前32頁(yè)，總共