《離散數(shù)學(xué)》第七章-圖論-第3-4節(jié)

除用圖形表示圖外，還可用矩陣表示圖，它的優(yōu)點(diǎn)：(1)將圖的問題變?yōu)閿?shù)學(xué)計(jì)算問題，從而可借助計(jì)算機(jī)來研究圖，進(jìn)行相關(guān)的計(jì)算。

(2)表示更清楚。知識點(diǎn)：1.鄰接矩陣

鄰接矩陣求兩點(diǎn)間不同長度的路的條數(shù)2.可達(dá)性矩陣3.完全關(guān)聯(lián)矩陣由于矩陣的行和列有固定的次序，因此在用矩陣表示圖時(shí)，先要將圖的結(jié)點(diǎn)進(jìn)行排序，若不具體說明排序，則默認(rèn)為書寫集合V時(shí)結(jié)點(diǎn)的順序。7-3圖的矩陣表示1.預(yù)備知識2.預(yù)備知識3.一、圖的鄰接矩陣或者i=jadjacent(鄰接)以結(jié)點(diǎn)與結(jié)點(diǎn)之間的鄰接關(guān)系確定的矩陣。定義7-3.1

設(shè)簡單圖G=<V,E>，其中V={v1,v2,…,vn}，則n階方陣A(G)=(aij)n

n

，稱為圖G的鄰接矩陣。其中第i行j列的元素。4.圖的鄰接矩陣?yán)?-3.1(1)寫出下面無向圖的鄰接矩陣0110010100110000000100010A(G)=v1v2v3v4v5v1v2v3v4v55.例7-3.1(2)：寫出下面有向圖的鄰接矩陣圖的鄰接矩陣?yán)齰2v1v3v40100001111011000A(G)=6.(1)鄰接矩陣的主對角線元素aii=0。(2)主對角線以外的元素aijaij=1(i<>j)，說明圖G是完全圖；aij=0(i<>j)，說明圖G是零圖。(3)無向圖的鄰接矩陣是對稱的；而有向圖的鄰接矩陣不一定對稱；因?yàn)樵跓o向圖中一條無向邊應(yīng)看成方向相反的兩條有向邊，因此無向圖的鄰接矩陣關(guān)于主對角線對稱。圖的鄰接矩陣說明：A(G)=0100001111011000v2v1v3v40110010100110000000100010A(G)=7.(4)結(jié)點(diǎn)的度數(shù)無向圖：每行1的個(gè)數(shù)=每列1的個(gè)數(shù)=對應(yīng)結(jié)點(diǎn)的度有向圖:每行1的個(gè)數(shù)=對應(yīng)結(jié)點(diǎn)的出度每列1的個(gè)數(shù)=對應(yīng)結(jié)點(diǎn)的入度圖的鄰接矩陣說明：v2v1v3v4A(G)=010000111101100001100101000000111000000108.圖的鄰接矩陣的應(yīng)用(1)由鄰接矩陣可計(jì)算出從vi到vj的長度為L的路的數(shù)目，也可計(jì)算從vi出發(fā)的長度為L的回路數(shù)。(2)計(jì)算結(jié)點(diǎn)vi與vj之間的距離。(3)判斷G是否是連通圖，及G中任意兩個(gè)結(jié)點(diǎn)是否連通。9.圖G的鄰接矩陣為A2中：G中從結(jié)點(diǎn)v2到結(jié)點(diǎn)v3長度為2路數(shù)目為0。A3中：G中從結(jié)點(diǎn)v2到結(jié)點(diǎn)v3長度為3的路數(shù)目為2。A2中：G中長度為2的路(含回路)總數(shù)為8，其中6條為回路。A3中：G中長度為3的路(含回路)總數(shù)為10，其中0條為回路。v4v1v3v2v5aij(2)=ai1?a1j+ai2?a2j+ai3?a3j++ain?anjaij(L+1)=ai1?a1j(L)+ai2?a2j(L)+ai3?a3j(L)++ain?anj(L)10.圖的鄰接矩陣的應(yīng)用(1)由鄰接矩陣可計(jì)算出從vi到vj的長度為L的路的數(shù)目，可計(jì)算從vi出發(fā)的長度為L的回路數(shù)。定理7-3.1

設(shè)G是具有結(jié)點(diǎn)集{v1，v2，…，vn}和鄰接矩陣A的圖，則矩陣AL（l=1，2，…）的第i行第j列的元素aij(L)=m，表示圖G中從結(jié)點(diǎn)vi到vj長度為L的路有m條（即路的數(shù)目）。aij(2)=ai1?a1j+ai2?a2j+ai3?a3j++ain?anjaij(L+1)=ai1?a1j(L)+ai2?a2j(L)+ai3?a3j(L)++ain?anj(L)11.定理7-3.1設(shè)G是具有結(jié)點(diǎn)集{v1，v2，…，vn}和鄰接矩陣A的圖，則矩陣AL（l=1，2，…）的第i行第j列的元素aij(L)=m，表示圖G中從結(jié)點(diǎn)vi到vj長度為L的路有m條（即路的數(shù)目）。證明：（從vi到vj的長度為l的路可看作從vi到vk的長度為1的路，再聯(lián)結(jié)vk到vj的長度為l-1的路。）用數(shù)學(xué)歸納法：

1）當(dāng)l=2時(shí)，成立。2）設(shè)l=p時(shí)命題對l成立，即aij(p)表示圖G中有幾條從結(jié)點(diǎn)vi到vj長度為p的路（即路的數(shù)目）12.3)證明l＝p＋1時(shí)定理成立。由故 而aik是結(jié)點(diǎn)vi到vk長度為1的路的數(shù)目，是結(jié)點(diǎn)vk到vj長度為p的路的數(shù)目，所以上式右邊的每一項(xiàng)表示從vi經(jīng)過一條邊到vk，再由vk經(jīng)過一條長度為p的路到vj的總長度為p+1的路的數(shù)目，對所有k求和，是所有從vi到vj的長度為p+1的路的數(shù)目。所以對l=p+1成立。證畢。定理7-3.1設(shè)G是具有結(jié)點(diǎn)集{v1，v2，…，vn}和鄰接矩陣A的圖，則矩陣AL（l=1，2，…）的第i行第j列的元素aij(L)=m，表示圖G中從結(jié)點(diǎn)vi到vj長度為L的路有m條（即路的數(shù)目）。13.v4v1v3v2v5圖的鄰接矩陣求不同長度的路例例7-3.2：求下圖中圖G的從結(jié)點(diǎn)v2到結(jié)點(diǎn)v3長度為2和3的路數(shù)目及所有長度為2和3的路數(shù)目。分析

利用定理7-3.1

，求圖中長度為m的路數(shù)目，只需要先寫出圖的鄰接矩陣，然后計(jì)算鄰接矩陣的m次方即可。14.圖G的鄰接矩陣為G中從結(jié)點(diǎn)v2到結(jié)點(diǎn)v3長度為2通路數(shù)目為0，G中長度為2的路（含回路）總數(shù)為8，其中6條為回路。G中從結(jié)點(diǎn)v2到結(jié)點(diǎn)v3長度為3的通路數(shù)目為2，G中長度為3的路（含回路）總數(shù)為10，其中0條為回路。v4v1v3v2v515.若中至少有一個(gè)不為0，則可斷定vi與vj相連接，求中不為0的最小的L即為d<vi,vj>。(2)計(jì)算結(jié)點(diǎn)vi與vj之間的距離。圖的鄰接矩陣的應(yīng)用如：d<v1,v2>=1,d<v1,v3>=2，d<v5,v4>=1,d<v1,v4>=∞v4v1v3v2v516.(3)判斷G是否是連通圖，及G中任意兩個(gè)結(jié)點(diǎn)是否連通。計(jì)算B=A1+A2+…+An，bij表示從結(jié)點(diǎn)vi到vj有長度分別為1、2、3…n的不同長度路的總數(shù)。①連通圖的判斷若B的每一個(gè)元素都非0，則為連通圖。②結(jié)點(diǎn)間的連通性若bij為0，那么結(jié)點(diǎn)vi與vj不相連接。若bij不為0，vi與vj有路相連接。圖的鄰接矩陣的應(yīng)用17.在許多問題中需要判斷有向圖的一個(gè)結(jié)點(diǎn)vi到另一個(gè)結(jié)點(diǎn)vj是否存在路的問題。如果利用圖G的鄰接矩陣A，則可計(jì)算A，A2，A3，…，An，…，當(dāng)發(fā)現(xiàn)其中的某個(gè)Al的≥1，就表明結(jié)點(diǎn)vi到vj可達(dá)。二、有向圖的可達(dá)矩陣（1）可達(dá)矩陣的定義（2）可達(dá)矩陣的計(jì)算方法（3）可達(dá)矩陣的應(yīng)用18.可達(dá)性矩陣表明了圖中任意兩個(gè)結(jié)點(diǎn)間是否至少存在一條路以及在任何結(jié)點(diǎn)上是否存在回路。定義7-3.2

設(shè)簡單有向圖G=（V，E），其中V={v1，v2，…，vn}，n階方陣P=（pij）n

n

，稱為圖G的可達(dá)性矩陣，其中第i行j列的元素=從vi到vj沒有路至少有一條路和0vv1pjiij1110011100111000001100011v1v2v3v4v5（一）有向圖的可達(dá)性矩陣19.設(shè)G是n階簡單有向圖，由可達(dá)性矩陣的定義知，當(dāng)i≠j時(shí)，如果vi到vj有路，則pij=1；如果vi到vj無路，則pij=0；又由定理7-2.1知，如果vi到vj有路，則必存在長度小于等于n–1的路。通過對圖G的鄰接矩陣A進(jìn)行運(yùn)算可得到G的可達(dá)性矩陣P。其方法如下：

1．由A計(jì)算A2，A3，…，An。

2．計(jì)算B=A+A2+…+An。

3．將矩陣B中非零元素改為1，所得到的矩陣即為可達(dá)性矩陣P。（二）圖的可達(dá)性矩陣計(jì)算方法（1）20.由鄰接矩陣A求可達(dá)性矩陣P的另一方法：將鄰接矩陣A看作是布爾矩陣，矩陣的乘法運(yùn)算和加法運(yùn)算中，元素之間的加法與乘法采用布爾運(yùn)算布爾乘：只有1∧1=1布爾加：只有0∨0=0計(jì)算過程：1．由A，計(jì)算A2，A3，…，An。2．計(jì)算P=A∨A2

∨…∨AnP便是所要求的可達(dá)性矩陣。圖的可達(dá)性矩陣計(jì)算方法（2）無向圖的可達(dá)性矩陣稱為連通矩陣，也是對稱的。圖的可達(dá)性矩陣計(jì)算方法（3）

Warshall算法21.A(4)=A(2)A(5)=A(3)

解：v1v2v3v4v5例7-3.3求右圖中圖G中的可達(dá)性矩陣。分析：先計(jì)算圖的鄰接矩陣A布爾乘法的的2、3、4、5次冪，然后做布爾加即可。P=A∨A(2)∨A(3)∨A(4)∨A(5)22.圖的可達(dá)性矩陣的應(yīng)用(1)利用可達(dá)性矩陣判斷有向圖的連通性。強(qiáng)連通單側(cè)連通弱連通(2)求強(qiáng)分圖(3)利用可達(dá)性矩陣判斷無向圖的連通性。無向圖G為連通圖的充要條件是圖的可達(dá)性矩陣所有元素均為1。23.（2）利用可達(dá)性矩陣判斷有向圖的連通性有向圖G為強(qiáng)連通的充要條件是圖的可達(dá)性矩陣所有元素均為1。有向圖G為單側(cè)連通的充要條件是圖的可達(dá)性矩陣P及其轉(zhuǎn)置矩陣PT所組成的矩陣P’=P∨PT，在P’中除對角線元素外所有元素均為1。原因：設(shè)PT為Q，即qij=pji，若qij∨pij=1，則結(jié)點(diǎn)vi與vj可達(dá)，或vj與vi可達(dá)；若qij∨pij=0，則結(jié)點(diǎn)vi與vj不可達(dá)。有向圖G為弱連通的充要條件是忽略邊的方向得到矩陣B=A∨AT，求B的可達(dá)性矩陣PB，在PB中除對角線元素外所有元素均為1。24.利用可達(dá)性矩陣判斷有向圖的連通性強(qiáng)連通圖v1v3v225.利用可達(dá)性矩陣判斷有向圖的連通性v1v3v2單側(cè)連通圖26.（3）利用可達(dá)性矩陣P，求強(qiáng)分圖方法：設(shè)PT為P的轉(zhuǎn)置矩陣,由P∧PT求強(qiáng)分圖原因：因?yàn)閷T，PijT=Pji若從vi到vj

可達(dá)，則Pij=1，若從vj到vi可達(dá)，則Pji=1，即PijT=1，于是當(dāng)且僅當(dāng)Vi和Vj相互可達(dá)時(shí)，P∧PT的第(i,j)項(xiàng)Pij∧PijT值為1。步驟如下：計(jì)算可達(dá)性矩陣P；計(jì)算P的轉(zhuǎn)置矩陣PT

；計(jì)算P∧PT

；P∧PT第i行元素為1的在第j1,j2,…,jk列，則結(jié)點(diǎn)vi,vj1,vj2,…,vjk在同一個(gè)強(qiáng)連通分支中，即{vi,vj1,vj2,…,vjk}導(dǎo)出的子圖是G的一個(gè)強(qiáng)連通分支。27.例強(qiáng)分圖為{v1},{v3},{v2,v4,v5}PT=0010011111000001111111111由可達(dá)性矩陣，求強(qiáng)分圖例V1V2V3V4V528.可達(dá)矩陣的應(yīng)用判斷是否存在遞歸調(diào)用，設(shè)P={P1,P2,…,Pn}表示程序中的函數(shù)集合，對應(yīng)為結(jié)點(diǎn)，若一函數(shù)Pi調(diào)用Pj，則在有向圖中用從Pi到Pj的有向邊表示，設(shè)函數(shù)集合P={P1,P2,P3,P4,P5}調(diào)用關(guān)系：P1調(diào)用P2；P2調(diào)用P4；P3調(diào)用P1；P4調(diào)用P5；P5調(diào)用P2；29.可達(dá)矩陣的應(yīng)用P2，P4，P5產(chǎn)生遞歸調(diào)用P1P2P3P4P530.完全關(guān)聯(lián)矩陣表示結(jié)點(diǎn)和邊的關(guān)系無向圖的完全關(guān)聯(lián)矩陣有向圖的完全關(guān)聯(lián)矩陣四、圖的完全關(guān)聯(lián)矩陣（結(jié)點(diǎn)和邊關(guān)系）31.定義7-3.3給定無向圖G=<V,E>，V={v1,v2,……,vp}，E={e1,e2,……eq}，則矩陣M(G)=(mij)p

q，其中稱M(G)為G的完全關(guān)聯(lián)矩陣。=vi不關(guān)聯(lián)ej關(guān)聯(lián)01mejviij無向圖的完全關(guān)聯(lián)矩陣（結(jié)點(diǎn)和邊關(guān)系）32.110011111000001101000110000000v1V2V3V4v5M(G)=e1e2e3e4e5e6e1e2e3e5e6e4v1v2v4v3v5圖的完全關(guān)聯(lián)矩陣?yán)?3.(3)這個(gè)結(jié)果正是握手定理的內(nèi)容，即各結(jié)點(diǎn)的度數(shù)之和等于邊數(shù)的2倍。(4)一行中元素全為0，其對應(yīng)結(jié)點(diǎn)是孤立結(jié)點(diǎn)。(5)若兩列相同，則相應(yīng)的兩邊平行。(2)每行元素的和即是結(jié)點(diǎn)vi的度數(shù)deg(vi)(1)圖中的一邊關(guān)聯(lián)兩個(gè)點(diǎn)，M(G)中每列中只有兩個(gè)1。圖的完全關(guān)聯(lián)矩陣性質(zhì)34.定義7-3.3給定簡單有向圖G=<V,E>，V={v1,v2,……,vp}，E={e1,

e2,……

,eq}，則矩陣M(G)=(mij)p

q，其中稱M(G)為G的完全關(guān)聯(lián)矩陣。=vi是ej的終點(diǎn)是01mejviij的起點(diǎn)-1vi與ej不關(guān)聯(lián)有向圖的完全關(guān)聯(lián)矩陣35.v1V2V3V4v5M(G)=e1e2e3e4e5e6e71000111-11000000-1100-1000-1100-1000-1-100e3e1e2e5e4e6e7v2v1v3v4v5有向圖的完全關(guān)聯(lián)矩陣?yán)?6.（1）圖中的一邊關(guān)聯(lián)兩個(gè)點(diǎn)，M(G)中每列中只有一個(gè)1和一個(gè)-1。（2）每行中1的個(gè)數(shù)和-1的個(gè)數(shù)分別為相應(yīng)結(jié)點(diǎn)的出度、入度。（3）結(jié)點(diǎn)vi的度數(shù)：（4）一行中元素全為0，其對應(yīng)結(jié)點(diǎn)是孤立結(jié)點(diǎn)。qk=1

|mik|有向圖的完全關(guān)聯(lián)矩陣性質(zhì)e3e1e2e5e4e6e7v2v1v3v4v5v1V2V3V4v5M(G)=e1e2e3e4e5e6e71000111-11000000-1100-1000-1100-1000-1-10037.小結(jié)掌握鄰接矩陣（有向圖、無向圖）的求法及性質(zhì)應(yīng)用理解利用鄰接矩陣求兩點(diǎn)間不同長度的路的數(shù)目掌握有向圖可達(dá)性矩陣的求法了解完全關(guān)聯(lián)矩陣的求法及性質(zhì)38.7-4歐拉圖和漢密爾頓圖具有某種特殊路（回路）的圖。知識點(diǎn)：歐拉路（回路）定義、七橋問題、一筆畫問題歐拉路（回路）判別定理有向圖歐拉路（回路）漢密爾頓路（回路）定義、周游世界問題漢密爾頓路（回路）必要條件漢密爾頓路（回路）充分條件圖的閉包39.歐拉圖與漢密爾頓圖總結(jié)歐拉圖與漢密爾頓圖的判別方法全體非空連通圖滿足定理7-4.1的條件不滿足定理7-4.1的條件歐拉圖非歐拉圖全體非空連通圖漢密爾頓圖非漢密爾頓圖滿足必要條件但不滿足任何充分條件至少滿足一個(gè)充分條件不滿足某個(gè)必要條件不能根據(jù)已知的充分條件或已知的必要條件判別是否是漢密爾頓圖。

根據(jù)給定的圖的特點(diǎn)采用特定的方法1.若能找到漢密爾頓回路，則它是漢密爾頓圖。2.(反證法)假設(shè)存在一個(gè)漢密爾頓回路，如果導(dǎo)致發(fā)生矛盾，則它不是漢密爾頓圖。3.暫時(shí)無法判別。40.1.歐拉圖（1）七橋問題，一筆畫，歐拉(回)路，歐拉圖（2）判定歐拉圖的充分必要條件(求歐拉回路的算法)41.七橋問題1736年瑞士數(shù)學(xué)家列昂哈德·歐拉(leonhardEuler)發(fā)表了圖論的第一篇論文“哥尼斯堡七橋問題”。這個(gè)問題是這樣的：哥尼斯堡(K?nigsberg)城市有一條橫貫全城的普雷格爾(PreGel)河，城的各部分用七座橋連接，每逢假日，城中的居民進(jìn)行環(huán)城的逛游，這樣就產(chǎn)生一個(gè)問題，能不能設(shè)計(jì)一次“逛游”，使得從某地出發(fā)對每座跨河橋走一次，而在遍歷了七橋之后卻又能回到原地。ABCD42.七橋問題的圖表示圖中的結(jié)點(diǎn)A，B，C，D表示四塊地，而邊表示七座橋。哥尼斯堡七橋問題是在圖中找尋經(jīng)過每一條邊且僅一次而回到原地的路。歐拉在1736年的一篇論文中提出了一條簡單的準(zhǔn)則，確定了哥尼斯堡七橋問題是不能解的。

gfabcdeBCADABCD43.一筆畫與七橋問題類似的還有一筆畫的判別問題，要判定一個(gè)圖G是否可一筆畫出，有兩種情況：一是從圖G中某一結(jié)點(diǎn)出發(fā)，經(jīng)過圖G的每一邊一次且僅一次到達(dá)另一結(jié)點(diǎn)。另一種就是從G的某個(gè)結(jié)點(diǎn)出發(fā)，經(jīng)過G的每一邊一次且僅一次回到該結(jié)點(diǎn)。上述兩種情況可以由歐拉路和歐拉回路的判定條件給予解決。44.歐拉圖(Eulerian)定義7-4.1

歐拉路(Eulertrail)：無孤立結(jié)點(diǎn)的圖（無向圖或有向圖），若存在一條路，經(jīng)過圖中所有邊一次且一次，該條路稱為歐拉路。歐拉回路(Eulertour/circuit)：若存在一條回路，經(jīng)過圖中所有邊一次且一次，該回路稱為歐拉回路。歐拉圖(Eulerian)：有歐拉回路的圖。半歐拉圖(semi-Eulerian)：有歐拉路的圖。幾點(diǎn)說明：平凡圖是歐拉圖。環(huán)不影響圖的歐拉性。單向歐拉路（回路）：給定有向圖，通過圖中每個(gè)結(jié)點(diǎn)一次且一次的單向路（回路），稱作單向歐拉路（回路）。45.歐拉圖的判定例7-4.1e1e2e3(2)歐拉圖半歐拉圖非（半）歐拉圖歐拉圖半歐拉圖非（半）歐拉圖46.無向圖的歐拉路及歐拉回路的判斷方法定理7-4.1

無向圖G具有一條歐拉路，當(dāng)且僅當(dāng)G是連通的，且有零個(gè)或兩個(gè)奇數(shù)度數(shù)的結(jié)點(diǎn)。推論：無向圖G具有一條歐拉回路，當(dāng)且僅當(dāng)G是連通的，所有結(jié)點(diǎn)的度數(shù)均為偶數(shù)。有向圖的歐拉路及歐拉回路的判斷方法定理7-4.2

有向圖G具有一條單向歐拉回路，當(dāng)且僅當(dāng)是G是強(qiáng)連通的，且每個(gè)結(jié)點(diǎn)的入度等于出度。推論：一個(gè)有向圖G具有單向歐拉路，當(dāng)且僅當(dāng)是G是單側(cè)連通的，而且除兩個(gè)結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)的入度等于出度，但這兩個(gè)結(jié)點(diǎn)中，一個(gè)結(jié)點(diǎn)的入度比出度大1（終點(diǎn)），另一個(gè)結(jié)點(diǎn)的入度比出度小1（起點(diǎn)）。這個(gè)定理的證明可以看作是定理7-4.1（無向圖的歐拉路）的推廣，因?yàn)閷τ谟邢驁D的任意一個(gè)結(jié)點(diǎn)來說，如果入度與出度相等，則該結(jié)點(diǎn)的總度數(shù)為偶數(shù)，若入度和出度之差為1時(shí)，其總度數(shù)為奇數(shù)。其原理就是每個(gè)結(jié)點(diǎn)都要能進(jìn)去多少次就能出來多少次。47.一筆畫gfabcdeBCAD無向圖G存在歐拉路，當(dāng)且僅當(dāng)()．A．G中所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)B．G中至多有兩個(gè)奇數(shù)度結(jié)點(diǎn)C．G連通且所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)D．G連通且至多有兩個(gè)奇數(shù)度結(jié)點(diǎn)gfabcdeCADB思考題：無向連通圖含G有m個(gè)奇數(shù)度結(jié)點(diǎn)，問（1）至少加入多少條邊才能使圖G變?yōu)闅W拉圖？（2）至少加入多少條邊才能使圖G變?yōu)榘霘W拉圖？48.例7-4.3

歐拉路（回路）判定歐拉路（回路）判定半歐拉圖歐拉圖非（半）歐拉圖歐拉圖半歐拉圖非（半）歐拉圖49.定理7-4.1

無向圖G具有一條歐拉路，當(dāng)且僅當(dāng)G是連通的，且有零個(gè)或兩個(gè)奇數(shù)度數(shù)的結(jié)點(diǎn)。證明：設(shè)無向圖G具有一條歐拉路，則G是連通的，且有零個(gè)或兩個(gè)奇數(shù)度數(shù)的結(jié)點(diǎn)。設(shè)G有歐拉路L，即有點(diǎn)邊序列v0e1v1e2

eiviei+1

envn，其中結(jié)點(diǎn)可能重復(fù)出現(xiàn)，但邊不重復(fù)。(1)證G是連通的，∵歐拉路L經(jīng)過G的所有邊，即經(jīng)過所有結(jié)點(diǎn)，∴G必連通。(2)證有零個(gè)或兩個(gè)奇數(shù)度數(shù)。對任意一個(gè)不是端點(diǎn)的結(jié)點(diǎn)vi

，每當(dāng)沿歐拉路L經(jīng)過vi一次，都經(jīng)過該結(jié)點(diǎn)關(guān)聯(lián)的兩條邊（一進(jìn)一出），即給結(jié)點(diǎn)的度數(shù)加2，vi可重復(fù)出現(xiàn)，但deg(vi)必是偶數(shù)。對于端點(diǎn)v0，vn，若v0

vn，則deg(v0)必是奇數(shù)，(起點(diǎn)僅有射出邊，若在路中也出現(xiàn)，度數(shù)必為偶數(shù)，∴1+偶數(shù)=奇數(shù))則deg(vn)必是奇數(shù)，(終點(diǎn)僅有射入邊，同上)若v0=vn，則deg(v0)必是偶數(shù)，∴2+偶數(shù)=偶數(shù)，(實(shí)質(zhì)為歐拉回路)50.證明：設(shè)無向圖G是連通的，且有零個(gè)或兩個(gè)奇數(shù)度數(shù)的結(jié)點(diǎn)，則G具有一條歐拉路。方法：構(gòu)造法證明-------思想：圈套圈(1)若有兩個(gè)奇數(shù)度數(shù)結(jié)點(diǎn)，則從其中一個(gè)結(jié)點(diǎn)出發(fā)，開始構(gòu)造一條邊不同的路(即跡)。方法：從v0出發(fā)，經(jīng)關(guān)聯(lián)邊e1進(jìn)入v1，若deg(v1)為偶數(shù)，則必可由v1再關(guān)聯(lián)邊e2進(jìn)入v2，如此下去，每邊僅取一次，由于G連通，必可到達(dá)另一奇數(shù)度數(shù)結(jié)點(diǎn)停下來，得到一條跡L1。(2)若L1通過了G的所有邊，則L1為歐拉路。(3)若G去掉L1(已通過的邊)后得到的子圖為G’(由剩余的邊組成)

，則G’中每個(gè)結(jié)點(diǎn)的度數(shù)為偶數(shù)，因?yàn)樵璆為連通的，則L1與G’至少有一個(gè)結(jié)點(diǎn)vi是重合的，在G’中從vi出發(fā)，重復(fù)(1)方法，得到另一跡L2，L1，L2合并在一起為新的L1，如果恰為G，即得歐拉路，否則重復(fù)(3)可得到另一跡L3，以此類推直到得到一條經(jīng)過G中所有邊的歐拉路。定理7-4.1

無向圖G具有一條歐拉路，當(dāng)且僅當(dāng)G是連通的，且有零個(gè)或兩個(gè)奇數(shù)度數(shù)的結(jié)點(diǎn)。51.逐步插入回路算法舉例走法一走法二52.找出穆罕默德短彎刀的歐拉回路。例題jhk53.解在圖中，僅有兩個(gè)度數(shù)為奇數(shù)的結(jié)點(diǎn)b，c，因而存在從b到c的歐拉路，螞蟻乙走到c只要走一條歐拉路，邊數(shù)為9條。而螞蟻甲要想走完所有的邊到達(dá)c，至少要先走一條邊到達(dá)b，再走一條歐拉路，因而它至少要走10條邊才能到達(dá)c，所以乙必勝。歐拉圖應(yīng)用1---(螞蟻比賽問題)例

甲、乙兩只螞蟻分別位于右圖中的結(jié)點(diǎn)a，b處，并設(shè)圖中的邊長度是相等的。甲、乙進(jìn)行比賽：從它們所在的結(jié)點(diǎn)出發(fā)，走過圖中的所有邊最后到達(dá)結(jié)點(diǎn)c處。如果它們的速度相同，問誰先到達(dá)目的地？cb(乙)a(甲)54.例

設(shè)G為n(n≥2)階無向歐拉圖，證明G中無橋（割邊）即λ(G)≥2。方法一：直接證法，從橋與歐拉圖定義考慮。利用閉跡的一個(gè)性質(zhì)（記為*）：刪除任意閉跡上的一條邊，仍連通。因?yàn)镚為歐拉圖，所以存在歐拉回路，設(shè)C為其中的一條歐拉回路，則G中任何邊均在C上。于是，對于任意的e∈E(G)，刪除e后的圖記為G’=G-e=C-e。由*可知，G’仍連通，故由橋的定義可知，e不是G中的橋。由e的任意性得證，G中無橋。即λ(G)≥2。歐拉圖應(yīng)用255.方法二：反證法：利用歐拉圖的性質(zhì)及握手定理的推論假設(shè)G中存在橋e=(u,v)，由于G為歐拉圖，所以e的兩個(gè)端點(diǎn)在G中的度數(shù)deg(u),deg(v)均為偶數(shù)。因?yàn)閑為G中橋，所以G’=G-e，由兩個(gè)連通分支G1和G2組成。不妨設(shè)u∈V(G1)，v∈V(G2)。由于刪除了e，因而在G1和G2中，deg(u)與deg(v)為奇度結(jié)點(diǎn)，而對于任意的w∈V(G1)，w≠u，deg(w)為偶數(shù)，即G1中只有一個(gè)奇度結(jié)點(diǎn)u；類似地，G2中也只有一個(gè)奇度結(jié)點(diǎn)v。這與握手定理的推論矛盾。故G中不可能含橋。即λ(G)≥2。歐拉圖應(yīng)用2（續(xù)）

例

設(shè)G為n(n≥2)階無向歐拉圖，證明G中無橋（割邊）即λ(G)≥2。56.歐拉圖應(yīng)用3例：設(shè)G是恰有2k(k≥1)個(gè)奇度結(jié)點(diǎn)的無向連通圖,證明G中邊能分為k條邊不重的跡，P1,P2,…,Pk。證明：將G中的2k個(gè)奇度結(jié)點(diǎn)分為數(shù)目相同的兩組為{u1,u2,…uk},{v1,v2,…,vk}，對圖G加邊(u1,v1)，(u2,v2),…(uk,vk),共k條得圖G’，則G’中每個(gè)結(jié)點(diǎn)的度數(shù)均為偶數(shù),故存在一條歐拉回路,即有閉跡。若在G中刪去邊(u1,v1)，則得一條歐拉路，兩端點(diǎn)為u1,v1，結(jié)點(diǎn)u2和v2在此路中，再刪去邊(u2,v2)則得兩條不同的跡，有四個(gè)端點(diǎn)分別為u1,u2,v1,v2，而u3,v3在其中一條跡中，再刪除邊(u3，v3)則得3條不同的跡，u4,v4在其一條中，依次繼續(xù)，直到刪去全部加邊可得到k條不同的跡。57.歐拉圖主要內(nèi)容1.歐拉路、歐拉回路、歐拉圖、半歐拉圖的定義。

2.判別定理（有向與無向）。

3.求歐拉圖中歐拉回路的算法。歐拉圖是若干個(gè)邊不重的圈之并。

58.2.漢密爾頓回路1859年威廉·漢密爾頓爵士在給他的朋友的一封信中，問題1：在一個(gè)十二面體中能否找到一條回路，使它含有這個(gè)圖的所有結(jié)點(diǎn)？問題2：把每個(gè)結(jié)點(diǎn)看成一個(gè)城市，聯(lián)結(jié)兩個(gè)結(jié)點(diǎn)的邊看成是交通線，能否找到旅行路線，沿著交通線經(jīng)過每個(gè)城市恰好一次，再回到原來的出發(fā)地？他把這個(gè)問題稱為周游世界問題。59.周游世界SirWilliamRowanHamilton,1859,Icosiangame：60.漢密爾頓圖定義定義7-4.3

給定圖G，若存在一條路經(jīng)過圖中的每一個(gè)結(jié)點(diǎn)恰好一次，這條路稱作漢密爾頓路。若存在一條回路，經(jīng)過圖中的每一個(gè)結(jié)點(diǎn)恰好一次，這個(gè)回路稱作漢密爾頓回路。具有漢密爾頓回路的圖稱為漢密爾頓圖。具有漢密爾頓路的圖稱為半漢密爾頓圖。幾點(diǎn)說明：1.平凡圖是漢密爾頓圖.2.環(huán)與平行邊不影響圖的漢密爾頓性.61.例(a)(c)(b)ac(d)既存在漢密爾頓通路，又存在漢密爾頓回路，即為漢密爾頓圖。既不存在漢密爾頓通路，也不存在漢密爾頓回路。既存在漢密爾頓通路，又存在漢密爾頓回路，即為漢密爾頓圖。存在漢密爾頓通路，但不存在漢密爾頓回路。62.例證明Kn(n≥3)是漢密爾頓圖。證明：例用構(gòu)造法來獲得一個(gè)漢密爾頓回路。在Kn中，從任意一個(gè)結(jié)點(diǎn)v1開始前進(jìn)，由于和其它的所有結(jié)點(diǎn)都有邊相連，則可以沿著某條邊到達(dá)另一個(gè)結(jié)點(diǎn)，設(shè)為v2，v2也與其它的所有結(jié)點(diǎn)有邊相連，若除v1和v2外還有結(jié)點(diǎn)沒遍歷到的話，可以經(jīng)過某個(gè)邊到達(dá)一個(gè)新的結(jié)點(diǎn)v3。依次類推，由于每個(gè)結(jié)點(diǎn)都與其他任何結(jié)點(diǎn)相連接，只要有結(jié)點(diǎn)沒遍歷到的話，必然能找到新的邊到達(dá)該結(jié)點(diǎn)，最終可以遍歷所有結(jié)點(diǎn)后回到v2，得到漢密爾頓回路。63.歐拉圖與漢密爾頓圖的關(guān)系歐拉圖不一定是漢密爾頓圖：漢密爾頓圖也不一定是歐拉圖：有的圖既是歐拉圖也是漢密爾頓圖有的圖既不是歐拉圖也不是漢密爾頓圖：Petersen圖64.漢密爾頓圖的相關(guān)定理無向漢密爾頓圖的充分條件滿足P，則漢密爾頓圖。用于漢密爾頓圖的判定及計(jì)算。但是不滿足P，也可能是漢密爾頓圖。無向漢密爾頓圖的必要條件漢密爾頓圖則Q。用于非漢密爾頓圖的判定。即非Q則非漢密爾頓圖。65.無向半漢密爾頓圖的充分條件定理7-4.4：設(shè)G是n階無向簡單圖，若對G中任意結(jié)點(diǎn)u與v有

deg(u)+deg(v)≥n-1則G是半漢密爾頓圖。（圖中存在漢密爾頓路）定理7-4.5：設(shè)G是n(3)階無向簡單圖，若對G中任意結(jié)點(diǎn)u與v有deg(u)+deg(v)≥n則G是漢密爾頓圖。66.無向半漢密爾頓圖的充分條件定理7-4.4：設(shè)G是n階無向簡單圖，若對G中任意結(jié)點(diǎn)u與v有deg(u)+deg(v)≥n-1則G是半漢密爾頓圖。（圖中存在漢密爾頓路）證明思想：

（一）G連通（二）構(gòu)造漢密爾頓路(1)由極大路徑得圈（路徑即為通路）(2)由圈得更長路徑

路徑--極大路徑--圈--更長路徑 ---更長極大路徑--更長圈--更長路徑

--……--漢密爾頓路。只要在G中構(gòu)作出一條長為n－1的漢密爾頓路即可得證。67.定理7-4.4：設(shè)G是n階無向簡單圖,若對G中任意結(jié)點(diǎn)u與v有deg(u)+deg(v)≥n-1。則G是半漢密爾頓圖。證明：（一）G連通：反證法：若G不是連通圖，則G至少有兩個(gè)連通分支，設(shè)為G1,G2，其階數(shù)為分別為n1,n2，設(shè)v1∈V(G1)，v2∈V(G2)，因?yàn)镚是簡單圖，所以degG1(v1)≤n1-1degG2(v2)≤n2-1因此，degG(v1)+degG(v2)=degG1(v1)+degG2(v2)≤n1-1+n2-1≤n-2<n-1與已知條件（deg(u)+deg(v)≥n-1）矛盾。所以G連通。無向半漢密爾頓圖的充分條件68.無向半漢密爾頓圖的充分條件（二）構(gòu)造漢密爾頓路證明漢密爾頓回路存在的過程其實(shí)就是構(gòu)造這條回路的過程，分成以下幾個(gè)步驟：

（1）構(gòu)造極大路徑

任意找兩個(gè)相鄰的結(jié)點(diǎn)S

和T，在它們基礎(chǔ)上擴(kuò)展出一條盡量長的沒有重復(fù)結(jié)點(diǎn)的路。也就是說，如果S與結(jié)點(diǎn)v相鄰，而且v不在路S→T上，則可以把該路變成v→S→T，然后v成為新的S。從S和T分別向兩頭擴(kuò)展，直到無法擴(kuò)為止，即所有與S或T相鄰的結(jié)點(diǎn)都在路S→T上。令P為G中任意一條長為p-1(p≤n)的通路，設(shè)其結(jié)點(diǎn)序列為v1,v2,…,vp。69.（2）構(gòu)造圈由極大路徑得圈：設(shè)極大路徑=v1…vp,pn-1，

反復(fù)應(yīng)用下面方法來擴(kuò)充這一通路，直到P長度為n-1（即包括所有結(jié)點(diǎn)）。若(v1,vp)E（即v1和vp相鄰），則得圈C=v1…vpv1。若(v1,vp)E（即v1和vp不相鄰）,可構(gòu)造出一個(gè)回路?？梢宰C明存在結(jié)點(diǎn)vi，i∈[1,p)，滿足vi

與v1

相鄰，且vi-1

與vp

相鄰。反證法：設(shè)v1與Г上的k個(gè)結(jié)點(diǎn)（記為vi1,vi2,…,vik）相鄰，則vp與vi1-1,…,vik-1之一相鄰，否則（即vp與vi1-1,…,vik-1均不相鄰），則vp至多鄰接于p-2-k結(jié)點(diǎn)，即deg(vp)≤p-2-k，deg(v1)=k,deg(v1)+deg(vp)≤k+(p-2-k)=p-2≤n-3，與題設(shè)矛盾。無向半漢密爾頓圖的充分條件70.定理7-4.4(證明(2))（續(xù)）找到了滿足條件的結(jié)點(diǎn)

vir

以后，于是得圈C=v1…vir-1vpvp-1…virv1.方法：在P中添加邊(v1,vir)、(vP,vir-1)，刪除邊(vir-1,vir)。v1vpvir-1virv1vpvirvir-171.定理7-4.4(證明(3))(3)由圈得更長路徑：連通考慮G中這條包含v1，v2，…，vp、長度為p的回路。由于p<n，所以V中還有一些結(jié)點(diǎn)不在C中，即必有回路外結(jié)點(diǎn)v與回路上結(jié)點(diǎn)(例如vk)相鄰，在C中刪除邊(vk-1,vk)而添加邊(v,vk)得到通路P’=vvkvk+1…vir-1vpvp-1r…virv1。顯然，P’比P長1，且P’上有k+1個(gè)不同的結(jié)點(diǎn)。如圖所示，可以得到一條長度為p的、包含v1，v2，…，vp的通路：

vvkvk+1…vir-1vpvp-1r…virv1

。如此繼續(xù)下去，直到得到一個(gè)包含所有結(jié)點(diǎn)的圈為止。72.vir-1定理7-4.4(證明(3))vv1vpvir-1virvk-1vkvv1vpvirvk-1vk73.無向漢密爾頓圖的充分條件定理7-4.5：設(shè)G是n(3)階無向簡單圖，若對G中任意結(jié)點(diǎn)u與v有deg(u)+deg(v)≥n則G是漢密爾頓圖。證明：由定理7-4.4知G連通且有漢密爾頓路=v1v2…vp。(1)若(v1,vp)E,則得漢密爾頓回路C=v1v2…vpv1.

(2)若(v1,vp)E,則與定理7-4.4證明(2b)類似,也存在漢密爾頓回路。#74.

413625極大路徑：6-1-3-4-2-56僅與1、2、3鄰接，5與1、2、4鄰接其中6鄰接于2，5鄰接于4632154漢密爾頓回路：6-1-3-4-5-2-663215475.例題

漢密爾頓圖的判定判定圖是否存在漢密爾頓回路?解：在圖中，有5個(gè)結(jié)點(diǎn)，deg(1)＝3，deg(2)＝3，deg(3)＝4，deg(4)＝3，deg(5)＝3。由于每一對結(jié)點(diǎn)的度數(shù)之和都大于5，所以G中存在一條漢密爾頓回路，如1—3—2—5—4—1。13542利用充分條件判定漢密爾頓圖例76.漢密爾頓圖判定定理給出的是漢密爾頓圖（半漢密爾頓圖）的充分條件，而不是必要條件。即具有n個(gè)結(jié)點(diǎn)的無向圖G=<V,E>，若對任意兩個(gè)不相鄰的結(jié)點(diǎn)u,vE，均有deg(u)+deg(v)<n（或deg(u)+deg(v)≤n，但是G中仍然會存在漢密爾頓路（或漢密爾頓路）。例圖(a)有6個(gè)結(jié)點(diǎn)，任意兩個(gè)結(jié)點(diǎn)度數(shù)的和小于5，但圖中存在一條漢密爾頓路。例如：圖(b)六邊形中，任意兩個(gè)不相鄰的結(jié)點(diǎn)度數(shù)之和都是4，4<6，但是六邊形存在漢密爾頓回路。(a)(b)77.例

考慮在七天內(nèi)安排七門課程的考試，使得同一位教師所任的兩門課程考試不排在接連的兩天中，試證明如果沒有教師擔(dān)任多于四門課程，則符合上述要求的考試安排總是可能的。證明：結(jié)點(diǎn)：每個(gè)結(jié)點(diǎn)對應(yīng)于一門課程考試，共七個(gè)結(jié)點(diǎn)；邊：關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn)對應(yīng)的課程考試是由不同教師擔(dān)任的；構(gòu)成7階無向簡單圖。vi∈V，deg(vi)為與vi不是由同一位教師任課的數(shù)目。因?yàn)槊總€(gè)教師所任課程數(shù)不超過4，故每個(gè)結(jié)點(diǎn)的度數(shù)至少是3，即deg(v)≥3，任兩個(gè)結(jié)點(diǎn)的度數(shù)之和至少是6，故G總是包含一條漢密爾頓路，它對應(yīng)于一個(gè)七門考試課目的一個(gè)適當(dāng)?shù)陌才?。漢密爾頓圖應(yīng)用178.例在某次國際會議的預(yù)備會中，共有8人參加，他們來自不同的國家。已知他們中任何兩個(gè)無共同語言的人中的每一個(gè)，與其余有共同語言的人數(shù)之和大于或等于8，問能否將這8個(gè)人排在圓桌旁，使其任何人都能與兩邊的人交談。證明：結(jié)點(diǎn)：參加會議的人，共8個(gè)；邊：相關(guān)聯(lián)的結(jié)點(diǎn)有共同語言；構(gòu)成8階無向簡單圖，vi∈V，deg(vi)為與vi有共同語言的人數(shù)。由已知條件可知，vi,vj∈V且i≠j，均有deg(vi)+deg(vj)≥8。由定理7-4.5可知，G中存在漢密爾頓回路，設(shè)C為G中一條漢密爾頓回路，按這條回路的順序安排座次即可。漢密爾頓圖應(yīng)用279.漢密爾頓圖應(yīng)用2的具體例子例設(shè)已知下列事實(shí)：a會講英語，b會講英語和漢語，c會講英語、意大利語和俄語，d會講日語和漢語，e會講德語和意大利語，f會講法語、日語和俄語，g會講法語、德語。問這7個(gè)人應(yīng)如何排座位，才能使每個(gè)人和他身邊的人交談？解：設(shè)無向圖G=<V，E>。其中，V={a,b,c,d,e,f,g}，E={<u,,v>|u,v∈V且u和v有共同語言}，如下圖所示，圖G是連通圖，將這七個(gè)人排座圍圓桌而座，使得每個(gè)人能與兩邊交談，即在圖G中找漢密爾頓回路，經(jīng)觀察，該回路是abdfgeca。acbedfg80.例今有n個(gè)人，已知他們中的任何二人合起來認(rèn)識其余的n-2個(gè)人。證明下列各題：

（1）當(dāng)n≥3時(shí)，這n個(gè)人能排成一列，使得中間的任何人都認(rèn)識兩旁的人，而兩端的人認(rèn)識左邊（或右邊）的人。

（2）當(dāng)n≥4時(shí)，這n個(gè)人能排成一個(gè)圈，使得每個(gè)人都認(rèn)識兩旁的人。漢密爾頓圖應(yīng)用3（自學(xué)）81.證明：作無向圖G=<V,E>，其中V={v|v為此人群的成員}，則|V|=n，并可將V表成V={v1,v2,…,vn}。E={(u,v)|u,v∈V，u≠v，且u與v認(rèn)識}，則G為n階無向簡單圖。由題中給的條件可知，u,v∈V，若u≠v，則deg(u)+deg(v)≥n-2。記為（*）要證明G中存在漢密爾頓路或回路，需要對于vi,vj∈V，i≠j，分vi與vj是否認(rèn)識兩種情況討論：漢密爾頓圖應(yīng)用3（自學(xué)）82.①vi與vj認(rèn)識，則deg(vi)+deg(vj)≥2+(n-2)=n②vi與vj不認(rèn)識，則對于任意vk∈V，且k≠i∧k≠j，vi與vj都認(rèn)識vk。反證法：否則vi或vj不認(rèn)識vk，比如說vi不認(rèn)識vk。此時(shí)，vj與vk都不認(rèn)識vi（認(rèn)識是彼此的），則vj與vk合起來至多認(rèn)識其余的n-3個(gè)人，

這與已知矛盾。于是，vi與vj都認(rèn)識vk，因而由vk的任意性可知deg(vi)+deg(vj)≥2(n-2)

（1）當(dāng)n≥3時(shí)，2(n-2)≥n-1，即deg(vi)+deg(vj)≥n-1，于是，無論vi與vj是否認(rèn)識，都有deg(vi)+deg(vj)≥n-1，由vi，vj的任意性可知，G中存在漢密爾頓路Г，只需按Г上結(jié)點(diǎn)的順序排列就可以達(dá)到要求。（2）當(dāng)n≥4時(shí)，2(n-2)≥n，即deg(vi)+deg(vj)≥n因而，無論vi與vj是否認(rèn)識，都有deg(vi)+deg(vj)≥n，G中存在漢密爾頓回路C，按C中順序排圈即可達(dá)到目的。漢密爾頓圖應(yīng)用3（自學(xué)）83.漢密爾頓圖判定不滿足充分條件，不能由此判斷它是否漢密爾頓圖。事實(shí)上，它不滿足必要條件，故不是漢密爾頓圖。84.無向漢密爾頓圖的必要條件定理7-4.3：若圖G=<V，E>具有漢密爾頓回路（即G是漢密爾頓圖），則對于結(jié)點(diǎn)集V的每一個(gè)非空子集S均有W(G－S)≤|S|成立。其中W(G－S)是G－S中連通分支數(shù)，|S|是結(jié)點(diǎn)子集S中結(jié)點(diǎn)的個(gè)數(shù)。漢密爾頓圖必有W(G－S)≤|S|，但滿足W(G－S)≤|S|的不一定是漢密爾頓圖。用于判定非漢密爾頓圖：W(G－S)>|S|，則為非漢密爾頓圖。85.無向漢密爾頓圖的必要條件W(G－S)≤|S|知識點(diǎn)：①母圖的連通分支數(shù)小于等于生成子圖的連通分支數(shù)。②刪除圈中的結(jié)點(diǎn)產(chǎn)生的連通分支數(shù)≤刪除結(jié)點(diǎn)個(gè)數(shù)證明：設(shè)C是G的一條漢密爾頓回路，則對于V的任何一個(gè)非空子集S，由點(diǎn)不重復(fù)的回路的特性知任意刪去C中|S|個(gè)點(diǎn)，最多將C分為|S|“段”，即W(C－S)≤|S|。若在C中刪去S中任一結(jié)點(diǎn)a1，則C－a1是連通非回路，即W(C－a1)=1；若刪去S中的另一個(gè)結(jié)點(diǎn)a2，則當(dāng)a1、a2鄰接時(shí)，W(C-{a1,a2})=1＜2；而當(dāng)a1、a2不鄰接時(shí)，W(C-{a1,a2})=2，即W(C-{a1,a2})≤2=|{a1，a2}|如此做下去，歸納可證W(C－S)≤|S|因?yàn)镃－S是G－S的一個(gè)生成子圖，且母圖的連通分支數(shù)小于等于生成子圖的連通分支數(shù)；因而W(G－S)≤W(C－S)

所以W(G－S)≤|S|86.例

判斷是否為漢密爾頓圖必要條件的應(yīng)用例在圖中取|S|=5，則W(G-S)＝6＞|S|＝5，因而該圖不存在漢密爾頓回路87.在圖中取S={v1,v4}則G－S中有三個(gè)連通分支，即W(G-S)=3>|S|=2，故G不是漢密爾頓圖。必要條件的應(yīng)用例例判斷下圖是否為漢密爾頓圖？因此選取非空子集S很重要88.通過例子說明定理7-4.3是必要條件，所以并不能作為漢密爾頓圖的判定條件。例7-4.7，著名的彼得森(Petersen)圖，如右圖所示在圖中刪去任一個(gè)結(jié)點(diǎn)或任意兩個(gè)結(jié)點(diǎn)，不能使它不連通；|