圖論復(fù)習(xí)題課件

第一章圖和子圖圖的基本概念；常見的特殊圖類；二部圖及其性質(zhì)；圖的同構(gòu)；關(guān)聯(lián)矩陣與鄰接矩陣；路、圈與連通圖；最短路問題。K-方體圖是其頂點為0與1的有序k元組,當(dāng)且僅當(dāng)它們的一個坐標不相同時,此兩個頂點相連以邊。證明k-方體圖是有2k個頂點k2k-1條邊的2-部圖。導(dǎo)出子圖和圖的運算G2G1G2G1由定理1.2可知圖(a)所示的圖不是二分圖，因為它包含一個長為3的圈,圖(b)所示的圖是一個二分圖，它不含長為奇數(shù)的圈.定理一個圖是二部圖當(dāng)且僅當(dāng)它不含奇圈。證明：設(shè)P=v0v1…v

k是G的最長路。因為d(v0)≥3，所以存在兩個與v1相異的頂點v′,v"與v0相鄰。v′,v"必都在路P上，否則會得到比P更長的路。無妨設(shè)v′

=vi

,v"=vj,(i<j)。若i,j中有奇數(shù)，比如i是奇數(shù)，則路P上v0到vi的一段與邊v0v

i構(gòu)成一個偶圈；若i,j都是偶數(shù)，則路P上vi到vj的一段與邊v0

vi

及v0vj構(gòu)成一個偶圈。證畢。例設(shè)G是簡單圖，若δ(G)≥3,則G必有偶圈。圖中兩點的連通：如果在圖G中u，v兩點有路相通，則稱頂點u，v在圖G中連通。連通圖：圖G中任二頂點都連通。圖的連通分支：若圖G的頂點集V(G)可劃分為若干非空子集V1,V

2,…,Vω

，使得兩頂點屬于同一子集當(dāng)且僅當(dāng)它們在G中連通，則稱每個子圖G[Vi]為圖G的一個連通分支（i=1,2,…,ω）。V1112921865129734136971V1V2V3V4V5V6V7V8V9V10240∞∞∞∞∞∞∞∞∞∞應(yīng)用：最短路問題算法實現(xiàn)－標號法課后習(xí)題（a）G是單圖且證明G連通.（b）v>1時，找一個不連通的單圖G使得證：（a）若G不連通，可分為兩個頂點數(shù)分別為v1，v2的互不連通子圖G1，G2。易知于是這與矛盾！（b）G=Kv-1+K1即為所求的單圖。用反證法，設(shè)G中各點的度均不相等。必有最大度△≥v-1。若△=v-1，必有δ≥1，從而△-δ+1<v,這與各點度均不等矛盾!若△>v-1,又與G是單圖矛盾。樹及其基本性質(zhì)；最小生成樹。第二章定理下列命題等價：（1）G是樹；（2）G中無環(huán)邊且任二頂點之間有且僅有一條路；（3）G中無圈且ε=ν?1；（4）G連通且ε=ν?1;（5）G連通且對任何e∈E(G)，G?e不連通；（6）G無圈且對任何e∈E(G)，G+e恰有一個圈。證明：（1）?（2）G是樹?G連通??u,v∈V(G)，存在路P(u,v)。逆定理的成立見習(xí)題2.1.1若還存在一條路P′(u,v)≠P(u,v)，則必存在w，w是路P與P′除了v之外最后一個公共頂點。P的(w,v)段與P′的(w,v)段構(gòu)成圈，這與G是樹矛盾。故只存在唯一的(u,v)路。連通且只有兩個連通分支，設(shè)為G1,G2

。注意到G1,G2分別都連通且任二頂點間只有一條路，由歸納法假設(shè)，因此歸納法完成。（3）?（4）用反證法。若G不連通，設(shè)G1,G2,…,Gw是其連通分支（w≥2），則（因Gi是連通無圈圖，由已證明的(1)和(2)知，對每個Gi

，(3)成立）。這樣，，這與矛盾。（4）?（5）ε(G?e)=ε(G)?1=ν?2，但每個連通圖必滿足ε≥ν?1（見下列命題），故圖G?e不連通。ν=1,2時，ε≥ν?1顯然成立。假設(shè)ν≤k的連通圖都ε≥ν?1。對于ν=k+1的連通圖H，任取v∈V(H)，考慮H?v。若H?v連通，則由歸納假設(shè)，ε(H?v)≥ν(H?v)?1=k?1，而命題若圖H連通，則ε(H)≥ν(H)?1。證明：對ν做數(shù)學(xué)歸納法。（5）?（6）先證G中無圈：若G中有圈，刪去圈上任一邊仍連通，矛盾。再證G+e恰含一個圈：因G連通且已證G無圈，故G是樹。由（2），任二頂點間僅有一條路相連，故G+e中必有一個含有e的圈；另一方面，若G+e中有兩個圈含有e，則G+e?e=G中仍含有一個圈，矛盾。（6）?（1）只需證G連通。任取u,v∈V(G)，若u、v相鄰，則u與v連通。否則，G+uv恰含一個圈，故u與v在G中連通。由u、v的任意性，圖G連通。定理證畢。證明：設(shè)T是一個非平凡樹。因T連通，故對每個頂點vi，都有。若對所有vi都有，則另一方面，這兩方面矛盾。故T至少有一個1度頂點，設(shè)為u。除此之外，其余ν?1個頂點的度數(shù)之和為2ν?3。若這些點的度都大于或等于2，則其度數(shù)之和≥2(ν?1)推論2.2非平凡樹至少含兩個1度頂點（葉子）。定義

對圖G，若V(G)的子集使得，則稱為圖G的一個頂點割集。含有k個頂點的頂點割集稱為k-頂點割集。注：（1）割點是1－頂點割集。（2）完全圖沒有頂點割集。第三章圖的連通性；割點、割邊和塊；邊連通與點連通；連通度。完全圖的連通度定義為κ(Kν)=ν?1?？請D的連通度定義為0。連通度：

κ(G)=min{|||是G的頂點割集}。注：(1)使得的頂點割集

稱為G的最小頂點割集。(2)若κ(G)≥k，則稱G為k連通的。

(3)若G不連通，則κ(G)=0。

(4)若G是平凡圖，則κ(G)=0。

(5)所有非平凡連通圖都是1連通的。在§2.2中為圖G的一個邊割集。含有k條邊的邊割集稱為k-邊割集。注：(1)對非平凡圖G，若是一個邊割集，則G\E′不連通。使得是G的一個邊割集，其中。(2)一條割邊構(gòu)成一個1－邊割集。對圖G的每個邊割集，必存在非空的S?V(G)，(3)邊連通度：完全圖的連通度定義為?？請D的連通度定義為0。注：(1)對平凡圖或不連通圖G，。(2)若圖G是含有割邊的連通圖，則。(3)若

，則稱G為k－邊連通的。(4)所有非平凡連通圖都是1－邊連通的。(5)使得的邊割集

稱為G的最小邊割集。確定下列給定圖類的點連通度和邊連通度.由定義我們可以確定對于圖的任一點和任意一條邊，有下列性質(zhì)成立定理3.1證明：先證。若G不連通，則。若G是完全圖，則。下設(shè)G連通但不是完全圖。則G有邊割集含有條邊。設(shè)這個邊割集為

。對中每條邊，選取一個端點，去掉這些端點（至多個）后，G便成為不連通圖，故這些端點構(gòu)成一個點割集

，。因此。再證。設(shè)d(v)=δ。刪去與v關(guān)聯(lián)的δ條邊后，G變成不連通圖，故這δ條邊構(gòu)成G的一個邊割集。因此。證畢。v2G1v1v3v4v5v6v7v9v8G2v2v1v3v4v5v8v6v7例1、分別找G1和G2兩個邊割；2、給出它們的邊連通度。G234例3.2塊（block）定義：

無割點的連通圖稱為塊。圖的塊：若滿足下列三條：（1）H是圖G的子圖；（2）H本身是一個塊；（3）H是具有此性質(zhì)的極大子圖。則稱H是圖G的一個塊。例注：至少有三個頂點的圖是塊當(dāng)且僅當(dāng)它是2－連通圖。

若只有兩個頂點，則有反例，例如K2是個塊，但不是2連通的。定理3.2(Whitney,1932)ν≥3的圖G是2－連通圖（塊）當(dāng)且僅當(dāng)G中任二頂點共圈。課后習(xí)題（a）證明：若G是單圖，且則(b)找一個單圖G,滿足解：（a）證：當(dāng)時，若不相鄰，則對任意第三點都有這時，對任意v-3個頂點的子集V′,均有G-V′仍連通。故當(dāng)時，故（b）對作易知：v=4時，v>4時，Kv-4中的v-4個頂點構(gòu)成G的頂點割集，故再由定理3.1即得課后習(xí)題證明：若G為滿足的單圖，證：在G中除去任意的k－1個頂點，所得之圖記為G1。則由練習(xí)15知，G1連通，從而知G是k-連通。則G是k-連通的。注:按定義從而對k=v時，的情況，即G是Kv的情況，要相應(yīng)地把結(jié)論中的v-連通換成(v-1)連通。課后習(xí)題若G是3-正則單圖，則證：①若從而至少存在一個分支僅一條邊和v相則不連通，故所以②若則存在不連通，由于所以③設(shè)不連通。關(guān)聯(lián)。顯然這邊為G的割邊，故故G-e2連通。由于故v1是G-e2的割點,且另一方面由定理3.1G1=G-v1連通。則v2是G1的割點且類似與②知在G1中存在一割邊e2(關(guān)聯(lián)于v2)使G1-e2不連通。于是類似于②知，在G-e2中存在一割邊e1,即不連通,故所以④由定理3.1知，由于我們已窮舉了的一切可能情況，故綜合上述,(注：值得注意，在證明過程中僅用到△≤3這條件，從而對于△≤3的單圖成立結(jié)論成立。第四章歐拉圖與哈密爾頓圖。歐拉圖；中國郵遞員問題；哈密爾頓圖；旅行商問題。定理4.1一個非空連通圖是Euler圖當(dāng)且僅當(dāng)它沒有奇度頂點。Euler圖的判定推論4.1一個連通圖有Euler跡當(dāng)且僅當(dāng)它最多有兩個奇度頂點。給定一個由16條線段構(gòu)成的圖形(見圖)。證明：不能引一條折線與每一線段恰好相交一次。(折線可以是不封閉的和自由相交的，但它的頂點不在給定的線段上，而邊也不通過線段的公共端點，即不允許折線從圖的缺口處穿過。)例證明：我們先來建立一個圖G。圖G中的頂點xi代表這個圖形的區(qū)域Xi(i=1,2,3,4,5,6)。頂點xi與xj之間連接的邊數(shù)等于區(qū)域Xi與Xj公共線段的數(shù)目(如圖所示)這樣建立的圖G中的每一條邊對應(yīng)這個圖形的一條線段。存在滿足條件的折線當(dāng)且僅當(dāng)G中存在一條Euler環(huán)游或Euler通路。由于G中有四個奇點，故G不存在Euler環(huán)游及Euler通路，也即證明了在圖形中不能引一條滿足要求的折線。*經(jīng)過圖G的每個頂點恰一次的路稱為G的Hamilton路。*經(jīng)過圖G的每個頂點恰一次的圈稱為G的Hamilton圈。Hamilton圖的研究起源于十二面體的游戲（1856）與Euler圖不同，目前為止尚沒有找到判別一個圖是否是Hamilton圖的有效充要條件。這是圖論中未解決的重要難題之一。

給出一些經(jīng)典的充分條件和必要條件。定理4.3若G是H圖，則對V(G)的每個非空真子集S，均有w(G－S)≤|S|。證明：設(shè)C是G的H圈，則對V(G)的每個非空真子集S，均有w(C－S)≤|S|由于C－S是G－S的生成子圖，故w(G－S)≤W(C－S)≤|S|。證畢。利用定理4.3可判斷下圖不是H圖。但定理4.3不能來判斷下列Petersen圖不是H圖。Petersen圖（1）度型條件定理4.4(Dirac,1952)若G是簡單圖，且ν≥3，δ≥v/2，則G是Hamilton圖。令A(yù)={G|G的頂點數(shù)為ν≥3，δ≥ν/2，且G是非Hamilton圖}。取A中邊最多的一個G。因ν≥3，故不是完全圖（否則G是Hamilton圖）。設(shè)u和v是G的不相鄰頂點。充分條件證明:用反證法：假定定理不真。于是G中存在以u為起點v為終點的Hamilton路v1v2…vν。這里v1=u，vν=v，令和由于故,并且由G的選擇，G＋uv是Hamilton圖。因G是非Hamilton圖，故G＋uv的H圈必經(jīng)過e=uv。（因為若，則G將包含H圈，矛盾）。故d(u)+d(v)=|S|+|T|=|S∪T|+|S∩T|<ν，這與δ≥ν/2的前提矛盾。證畢。引理4.5（Bondy&Chvátal,1974）設(shè)G是簡單圖，u和v是G中不相鄰的頂點，且d(u)+d(v)≥ν，則G是Hamilton圖當(dāng)且僅當(dāng)G＋uv是Hamilton圖。(2)閉包型條件定理4.7一個簡單圖是Hamilton圖當(dāng)且僅當(dāng)它的閉包是Hamilton圖。證明：在構(gòu)作閉包過程中，反復(fù)運用引理4.5即可。推論4.8設(shè)G是ν≥3的簡單圖。若C(G)是完全圖，則G是Hamilton圖。

例

有一個n人的團體(n≥3)，這n個人中互相認識的對數(shù)(兩個人認識就算作一對)至少是1/2(n-1)(n-2)+2.證明這n個人可以圍桌而坐，使每個人與他相鄰座位上的2個人認識。證明：以頂點代表人，兩頂點相鄰當(dāng)且僅當(dāng)2個人互相認識，則G是至少有條邊的簡單圖?，F(xiàn)在證明G是Hamilton圖。假若不然，則G無Hamilton回路，由Lemma4.5知，G中存在兩個不相鄰的頂點u與v。使因而G中至多有n－1條邊關(guān)聯(lián)

Hamilton回路C。現(xiàn)在只需按C的順序安排人員圍桌而坐，就能使每個人與相鄰座位的兩個人認識。于u和v。作G1=G-{u,v}，由于u和v不相鄰，故這與相矛盾。所以G有定理4.9設(shè)G是度序列為（d1,d2,…,dν

）的簡單圖，這里d1≤d2≤…≤dν，并且ν≥3。若不存在小于ν／2的m，使得dm

≤m和dν?m

<ν?m，則G是Hamilton圖。(3)度序列條件例求下圖的最優(yōu)投遞路線，A為郵局。解：只有兩個奇點，V′={B,E}。B到E的最短路為BAFE，權(quán)為13。完全賦權(quán)圖K2及相應(yīng)的Euler圖G*為易求得其Euler環(huán)游，并得到最優(yōu)回路。應(yīng)用：中國郵遞員問題課后習(xí)題證明：若(a)G不是2-連通的，或(b)G是二部圈，且它的二部劃分(X,Y)有|X|

≠|(zhì)Y|，則G是非Hamilton圖。證：(a)若G不是2-連通的，則G不連通或存在割點v有由定理4.3知G是非Hamilton圖。且|X|<|Y|，(b)設(shè)G是2-部圖，其劃分為(X，Y)，則有由定理4.3知G是非Hamilton圖。證：設(shè)P(u,v)是G中最長路，其長度為l<2δ,路P(u,v)中的頂點依次為故和u,v相鄰的頂點均在路上．由于G是單圖，從而若令課后習(xí)題若G是連通單圖，且v>2δ,則G中有一條長度至少為2δ的路。按定義故所以有設(shè)于是我們得到G中的一個長度為l+1的圈C如下：，則顯然P″的長度大于l，但這又與P(u,v)是G中最長路相矛盾。故一條路P″:P′加上路，由于故在C外恒存在一點由于G是連通的，所以有一條C外的路P′和C相連，相連，不失一般性，不妨假定和v1于是我們在G

中找到第五章匹配問題匹配與最大匹配；完美匹配；二部圖的最大匹配。定義

設(shè)G是一個圖,M?E(G),滿足:對?ei,ej∈M,ei與ej在G中不相鄰,則稱M是G的一個匹配。對匹配M中每條邊e=uv,其兩端點u和v稱為被匹配M所匹配,而u和v都稱為是M

飽和的(saturatedvertex)。注:每個頂點要么未被M飽和,要么僅被M中一條邊飽和。定義設(shè)M是G的一個匹配，若G中無匹配M'

，使得|M'

|>|M|,則稱M是G的一個最大匹配；如果G中每個點都是M飽和的,則稱M是G的完美匹配(Perfectmatching).

213456MatchingM261345MatchingM'顯然,完美匹配必是最大匹配。定義設(shè)M是G的一個匹配,G的M交錯路是指其邊M和E(G)\M中交替出現(xiàn)的路。如果G的一條M交錯路(alternatingpath)的起點和終點都是M非飽和的,則稱其為一條M可擴展路或M增廣路(augmentingpath)。P:v5v4v2v1v3是M-alternating。v1v2v3v4v5v6v7v8定理5.1(Berge,1957)圖G的匹配M是最大匹配的充要條件是G中不存在M可擴展路。偶圖的對集和覆蓋定義

圖G的鄰集。定理5.2(Hall,1935)設(shè)G是具有二劃分(X,Y)的二部圖，則G有飽和X的匹配當(dāng)且僅當(dāng)對?S?X，|N(S)|≥|S|，其中N(S)表示S的所有鄰點之集。推論5.5設(shè)G=(X，Y)是二部圖，且X=Y=n。若δ(G)≥n/2，則G有完美匹配。證明(用反證法)：若G沒有完美匹配，則由推論5.2，存在S?X,S≠φ，使|N(S)|<|S|。因G是二部圖且δ(G)≥n/2，故|S|>|N(S)|≥δ(G)≥n/2，且Y\N(S)≠φ（因|N(S)|<|S|≤|X|=|Y|）。令u∈Y\N(S)，則N(u)?X\S，因此，這與條件矛盾。故G有完美匹配。證畢。例下圖所示的是14個大小相同的正方形組成的圖形。試證明：不論如何用剪刀沿著圖形中所畫的直線對它進行裁剪，總剪不出7個由相鄰的兩個小正方形組成的矩形來。證明：將圖形中方格從1到14編號。以方格為頂點集作簡單圖G=(V,E)，邊ij∈E(G)當(dāng)且僅當(dāng)i、j所在的方格在圖形中相鄰（有公共邊）。注意G中每條邊對應(yīng)于原圖形中由相鄰兩個小正方形組成的矩形，故剪出7個矩形相當(dāng)于在G中求由7條邊組成的匹配。由于有14個頂點，故所求的是完美匹配。但這樣的匹配是不存在的。事實上，G是一個二部圖，其二劃分為X={1,3,4,6,9,11,12,14}，Y={2,5,7,8,10,13}。|X|=8>6=|Y|。由推論5.2，不存在完美匹配。引理5.3

設(shè)M是對集，K是覆蓋，適合|M

|=|K|，則M是最大對集，且K是最小覆蓋。證明：若M*是最大對集，且K'是最小覆蓋，則由(5.5)由于|M

|=|K|，所以。定理5.3

在偶圖中，最大對集的邊數(shù)等于最小覆蓋的頂點數(shù)。推論1（k?1）邊連通偶數(shù)階k正則圖有完美匹配。證明：設(shè)G是命題中所述的k正則圖。當(dāng)k=1時，結(jié)論顯然。以下假定k≥2。設(shè)S是G的任一個非空頂點集，G1,G2,…,Gn

是G\S的奇分支。令νi

=V(G),mi=|{e|e是Gi

與S之間的連邊}|。由于κ′≥k?1，故mi≥k?1,(i=1,2,…,m)。完美匹配定理5.4(Tutte,1947)圖G有完美匹配的充分必要條件是對?S?V(G)，O(G\S)≤|S|。若存在i，使得m

i=k?1

，則因從而因此，但因νi?1是偶數(shù)（每個Gi是奇分支），上式兩端不可能相等。這個矛盾說明mi≥k（i=1,2,…,n)，于是由Tutte定理，G有完美匹配。證畢。(1)證明：設(shè)G是沒有割邊的3-正則圖，S是V的真子集，用

G1,G2,…,Gn表示G-S的奇分支，并設(shè)mi

是一個端點在S中的那些邊的條數(shù)。由于G是3正則的，所以并且(2)推論5.4(Peterson,1891)２－邊連通（無割邊）的３正則圖有完美匹配。由(3)和(2)可得所以由定理5.4，G有完美匹配。由(1)是奇數(shù)。又由于G沒有割邊，所以mi≠1。因此mi≥3for1≤i≤n(3)注：有割邊的３正則圖未必有完美匹配，例如：因O(G?v)=3,故無完美匹配。應(yīng)用：二部圖最大匹配第6、7、8章染色定理6.1設(shè)G是二部圖，則。定理6.2(Vizing定理，1964)設(shè)G是無環(huán)非空簡單圖，則獨立集、覆蓋集與團點獨立集、點覆蓋集、邊覆蓋集與團的概念。圖的著色問題點著色；邊著色；平面圖；四色猜想。從而Petersen圖的邊色數(shù)如圖所示它是Petersen圖的一種4–邊另一方面證明Petersen圖是4–邊色的。證：由練習(xí)5.1.5，Petersen圖不是可1–因子化的，正常著色，故有課后習(xí)題證明：若G是非空正則單圖，且v為奇數(shù)，則證：因為v=奇數(shù)，故G的任一正常的邊著色的每一色類最多是條邊，從而又由于G是正則圖，從而故另一方面由Vizing故定理知例支配集、點獨立集、點覆蓋集與團定理7.1.4若I是獨立集，則它是極大獨立集當(dāng)且僅當(dāng)它是支配集。證明：必要性由定理7.1.3顯然。充分性：設(shè)I是獨立集又是支配集，則對?v∈V(G)\I，因I是支配集，v必與I中某頂點相鄰。故I∪{v}不是獨立集?？梢奍是極大獨立集。定理7.1.7頂點子集C是圖G的點覆蓋集當(dāng)且僅當(dāng)

V(G)\C是G的點獨立集。證明：C是圖G的點覆蓋集?G的每條邊至少有一端在C中?沒有兩端都在V(G)\C中的邊?V(G)\C是點獨立集。證畢。推論7.1.3

C是圖G的極小點覆蓋集當(dāng)且僅當(dāng)V(G)\C是G的極大點獨立集。點覆蓋與點獨立集的關(guān)系：推論7.1.4

α(G)+β(G)=ν.證明：利用定義，可得-=V\K,和

-=V\S即可證明。邊獨立集與邊覆蓋集定義圖G的一個匹配M稱為G的一個邊獨立集。G的最大匹配所含的邊數(shù)稱為G的邊獨立數(shù)或匹配數(shù)，記為。邊獨立數(shù)與點覆蓋的關(guān)系：例是邊覆蓋，但不是極小邊覆蓋。也是極小邊覆蓋，還是最小邊覆蓋；都是邊覆蓋，推論7.2.3設(shè)G是二部圖且，則。證明：由于，而由Konig定理，(定理5.3)得故。證畢。定理5.3

在偶圖中，最大對集的邊數(shù)等于最小覆蓋的頂點數(shù)。易證：χ(G)=1?G=

；χ(G)=2?G是非空二部圖；χ(G)=ν(G)?G?Kν（3）χ(C2n+1)=3。（4）χ(G)≥3?G含有奇圈。（5）四色定理：對任何平面圖G，χ(G)≤4。點染色理論的基本問題：給定圖G，確定χ(G)的值。頂點著色定義8.1.4設(shè)χ(G)=k,(k≥1)。若對G的任何真子圖H，均有χ(H)<k，則稱G是臨界k色圖。圖的頂點染色問題可以歸結(jié)為求圖的獨立集，它的頂點集至少能劃分成多少個點不交的獨立集？（2）Grótzsch圖是臨界4色圖；（1）G是臨界1色圖?G?K1

；G是臨界2色圖?G?K2

；G是臨界3色圖?G是奇圈；Gr?tzschgraphis4-critical(1958)（3）任何k色圖都包含一個臨界k色子圖；（4）每個色臨界圖都是連通的。定理8.1.1色臨界圖的頂點割集不是團。推論8.1.1

每個色臨界圖都是塊（即不含割點，亦即2連通）。推論8.1.2若臨界k色圖G有2頂點割集{u,v}，則u與v不相鄰。定理8.1.2(Dirac,1952)設(shè)G是臨界k色圖（k≥2），則邊連通度κ′(G)≥k-1。推論8.1.3設(shè)G是臨界k-色圖，則δ(G)≥k?1。推論8.1.4任何k色圖至少有k個頂點的度≥k?1。推論8.1.5對任何簡單圖G，χ(G)≤Δ(G)+1。定理8.1.3(Brooks，1941)設(shè)G是連通的簡單圖，且G既不是奇圈又不是完全圖，則χ(G)≤Δ(G)。解：因Peterson圖G含有奇圈，故不是二部圖，因而χ(G)≥3；另一方面，G既不是奇圈又不是完全圖，且Δ(G)=3,故χ(G)≤Δ(G)=3。因此，χ(G)=3。例：求Peterson圖的色數(shù)。8.1.9(a)證明：若u,v是臨界圖G的兩個頂點，則N(u)不是N(v)的子集；(b)證明：不存在k+1個頂點的k–臨界圖G。證：(a)若，由于，故，所以u,v不相鄰。又因G是k–臨界

圖,故對G-u存在(k-1)—正常著色。若在此基礎(chǔ)上令u和v著同色，則最后得到G課后習(xí)題上的一個(k-1)—正常著色，于是，這和G是k–色圖相矛盾，故(b)若這樣G存在，由定理8.1知，。另一方面顯然故在G中存在兩個不N(u)不是N(v)的子集.相鄰的頂點v1,v2,由于及，故但這與(a)相矛盾，故結(jié)論成立。8.2.1證明：Brooks定理等價于下述命題：若G是k–臨界(k≥4)，且不是完全圖，則。證：＝＞：由于k≥4，故G不可能是奇圈，由假設(shè)G不是完全圖，故△>δ,且令d1＝△，于是由Brooks定理△≥k，

再由定理1.1和定理8.1有課后習(xí)題＜＝：設(shè)G的-臨界子圖記為H，下面我們分三種情況討論：(1)H是奇圈。由于G是連通的非奇圈圖，故在G

中存在H外的邊與H相連，所以△(G)≥3。另一方面，故(2)H是完全圖。由于G的連通性及G不是完全圖故在G中存在H外的邊與H相連，所以

(3)H既不是奇圈又不是完全圖，由練習(xí)8.1.7知,，所以此時H滿足命題的條件。于是有。即。所以有綜合上述情況，命題成立。v1*v2*v3*v4*bacdefgh設(shè)平面圖G有n個頂點，m條邊，d個面，分別為S1，S2，…，Sd，在每個Si面放置一個頂點vi*，如果Si和Sj面相鄰，則用(vi*,vj*)連接(vi*點和vj*點，使(vi*,vj*)與面Si和Sj的公共邊只相交一次，且G的其它邊界無交點。這樣得到的圖G*稱為G的對偶圖。平面圖證明假定K3,3是平面的，令G是K3,3的平面嵌入因為K3,3不具有長小于4的圈，G的每個面的度必然至少是4。因此由定理9.4,有即于是由定理9.5可以得到導(dǎo)致謬誤。推論9.3

K3,3是非平面的.例說明彼得森圖不是平面圖。刪去圖(a)彼得森圖的結(jié)點b，得到它的一個子圖為圖(b)所示H。而H同胚于K3,3，故彼得森圖不是平面圖。顯然，庫拉斯基給出了平面圖的充要條件，但用它并不能得出判別一個圖是否平面圖的有效算法。圖所示G和H的色數(shù)是多少？圖G的色數(shù)至少為3，因為頂點a,b和c必須指定為不同的顏色。為檢驗是否可以用三種顏色來對G著色，指定a為紅色，b為藍色，c為綠色；從而d必為紅色；e為綠色，f為藍色；最后，確定g為紅色。因此G的色數(shù)(G)=3。H的色數(shù)(H)=4。12345678G723456?1{12,13,14,15},(26}{48,58,68,78},{37}762345?2{12,13,14,15}{48,58,68,78},{37}例2345?3{12,13,14,15}{48,58,68,78}672345?4{14},{15}{48,58,68,78}6712345?5{15},{48,58,68,78}6712345?6{48,58,68,78}6712345?7{68},{78}67182345?8{78}67182345?96718第十一章網(wǎng)絡(luò)有向圖；網(wǎng)絡(luò)與網(wǎng)絡(luò)流的基本概念；最大流最小割定理；求最大流的標號算法；網(wǎng)絡(luò)流理論的應(yīng)用。(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2網(wǎng)絡(luò)D及其一個流vs為發(fā)點(源)，vt為收點(匯)，其余點為中間點。對每條弧(vi

,vj)，有弧的容量cij

，弧的流量fij，常記做(fij

,cij

).

定義3設(shè)F是網(wǎng)絡(luò)G的一個流，其源為a，匯為z，稱值為流F的值，記作val(F)。

定義4設(shè)f是網(wǎng)絡(luò)N的最大流，如果不存在流f′使得valf′>valf

。

網(wǎng)絡(luò)的割集有多個，其中割集容量最小者稱為網(wǎng)絡(luò)的最小割集容量(簡稱最小割)。(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2割集(S,S)中所有始點在S，終點在S的弧容量之和稱為(S,S)的割集容量(割量)。記作因此，若能找到一個可行流f，一個割集(S,S)，使得成立則f必是最大流，而(S,S)是最小割。推論11.1顯然，對于網(wǎng)絡(luò)的任意一個可行流f和割(S,S)，成立定理11.2一個可行流f={fij}，稱fij=

cij的弧為飽和弧，稱fij<cij的弧為不飽和弧.

fij=

0的弧為零流弧，fij>

0的弧為非零流弧.(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2飽和弧零流弧不飽和弧設(shè)P是網(wǎng)絡(luò)D的一條連接源點vs和匯點vt的鏈，定義鏈P的方向是從vs到vt，前向弧—弧的方向與P的方向一致；全體記為P

+.后向弧—弧的方向與P的方向相反；全體記為P

-.則P中的弧可分為兩類：f是一個可行流，P是從vs到vt的一條鏈，如果(1)P的每一前向弧都是不飽和?。ǎ?(2)P的每一后向弧都是非零流弧（）；則稱P是網(wǎng)絡(luò)D的關(guān)于可行流f的一條增廣鏈。簡稱增廣鏈。(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2增廣鏈P：

定理11.3：設(shè)f是網(wǎng)絡(luò)D上的一個可行流，則f是一個最大流當(dāng)且僅當(dāng)網(wǎng)絡(luò)D不存在f的增廣鏈。(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2增廣鏈P：8528796653vsv1vtv4v3v2算例：求下面網(wǎng)絡(luò)的最大流.(0,8)(0,5)(0,2)(0,8)(0,7)(0,9)(0,6)(0,6)(0,5)(0,3)vsv1vtv4v3v2(1)給網(wǎng)絡(luò)賦一個初始0流f0；給vs標號(-,∞);(-,∞)(a)對弧(vi,vk),若,則給vk

標號(+vi,l(vk)),其中(b)對弧(vk,vi),若,則給vk

標號(-vi,l(vk)),其中標號過程1(+vs,8)(+vs,2)(+v1,5)(+v3,2)(+v2,5)找到流f0的增廣鏈P0