離散數(shù)學(xué)：15歐拉圖與哈密頓圖

1、 1第第1515章章 歐拉圖與哈密頓圖歐拉圖與哈密頓圖離散數(shù)學(xué)離散數(shù)學(xué) 2本章內(nèi)容本章內(nèi)容15.1 15.1 歐拉圖歐拉圖15.2 15.2 哈密頓圖哈密頓圖15.3 15.3 帶權(quán)圖與貨郎擔(dān)問題帶權(quán)圖與貨郎擔(dān)問題基本要求基本要求作業(yè)作業(yè) 315.1 15.1 歐拉圖歐拉圖q 歷史背景哥尼斯堡七橋問題歷史背景哥尼斯堡七橋問題q 歐拉圖是一筆畫出的邊不重復(fù)的回路歐拉圖是一筆畫出的邊不重復(fù)的回路。 4歐拉圖歐拉圖定義定義15.115.1 通過圖（無向圖或有向圖）中通過圖（無向圖或有向圖）中所有邊一次且僅一次所有邊一次且僅一次行遍圖中所有頂點(diǎn)的行遍圖中所有頂點(diǎn)的通路通路稱為稱為歐拉通路歐拉通路，通過

2、圖中所有邊，通過圖中所有邊一次并且僅一次行遍所有頂點(diǎn)的一次并且僅一次行遍所有頂點(diǎn)的回路回路稱為稱為歐拉回路歐拉回路。具有。具有歐拉回路的圖稱為歐拉回路的圖稱為歐拉圖歐拉圖，具有歐拉通路而無歐拉回路的，具有歐拉通路而無歐拉回路的圖稱為圖稱為半歐拉圖半歐拉圖。 說明說明歐拉通路是圖中經(jīng)過所有邊的簡單的生成通路歐拉通路是圖中經(jīng)過所有邊的簡單的生成通路( (經(jīng)過所經(jīng)過所有頂點(diǎn)的通路稱為生成通路有頂點(diǎn)的通路稱為生成通路) )。歐拉回路是經(jīng)過所有邊的簡單的生成回路。歐拉回路是經(jīng)過所有邊的簡單的生成回路。 規(guī)定平凡圖為歐拉圖規(guī)定平凡圖為歐拉圖 環(huán)不影響圖的歐拉性環(huán)不影響圖的歐拉性 5舉例舉例歐拉圖歐拉圖半歐

3、拉圖半歐拉圖無歐拉通路無歐拉通路歐拉圖歐拉圖無歐拉通路無歐拉通路無歐拉通路無歐拉通路 6無向歐拉圖的判定定理無向歐拉圖的判定定理 定理定理15.115.1 無向圖無向圖G是歐拉圖當(dāng)且僅當(dāng)是歐拉圖當(dāng)且僅當(dāng)G是連通圖，且是連通圖，且G中沒有奇中沒有奇度頂點(diǎn)。度頂點(diǎn)。證明證明 若若G是平凡圖，結(jié)論顯然成立。是平凡圖，結(jié)論顯然成立。下面設(shè)下面設(shè)G為非平凡圖，設(shè)為非平凡圖，設(shè)G是是m條邊的條邊的n n階無向圖，階無向圖，并設(shè)并設(shè)G的頂點(diǎn)集的頂點(diǎn)集V v1 1, ,v2 2, , ,vn 。必要性必要性。因?yàn)?。因?yàn)镚為歐拉圖，所以為歐拉圖，所以G中存在歐拉回路，中存在歐拉回路，設(shè)設(shè)C為為G中任意一條歐拉回

4、路，中任意一條歐拉回路， vi, ,vjV，vi, ,vj都在都在C上，上，因而因而vi, ,vj連通，所以連通，所以G為連通圖。為連通圖。又又 viV，vi在在C上每出現(xiàn)一次獲得上每出現(xiàn)一次獲得2 2度，度，若出現(xiàn)若出現(xiàn)k次就獲得次就獲得2 2k度，即度，即d( (vi) )2 2k，所以所以G中無奇度頂點(diǎn)。中無奇度頂點(diǎn)。 7定理定理15.115.1的證明的證明充分性充分性。由于。由于G為非平凡的連通圖可知，為非平凡的連通圖可知，G中邊數(shù)中邊數(shù)m1 1。對對m作歸納法。作歸納法。 (1)(1)m1 1時(shí)，由時(shí)，由G的連通性及無奇度頂點(diǎn)可知，的連通性及無奇度頂點(diǎn)可知，G只能是一個(gè)環(huán)，因而只能是

5、一個(gè)環(huán)，因而G G為歐拉圖。為歐拉圖。 (2)(2)設(shè)設(shè)mk( (k1)1)時(shí)結(jié)論成立，要證明時(shí)結(jié)論成立，要證明mk+1+1時(shí)，結(jié)論也成立。時(shí)，結(jié)論也成立。由由G的連通性及無奇度頂點(diǎn)可知，的連通性及無奇度頂點(diǎn)可知， ( (G) )2 2。無論無論G是否為簡單圖，都可以是否為簡單圖，都可以用擴(kuò)大路徑法用擴(kuò)大路徑法證明證明G中必含中必含圈圈。 8定理定理15.115.1的證明的證明設(shè)設(shè)C為為G中一個(gè)圈，刪除中一個(gè)圈，刪除C上的全部邊，得上的全部邊，得G的生成子圖的生成子圖G ，設(shè)設(shè)G 有有s個(gè)連通分支個(gè)連通分支G 1 1, ,G 2 2, , ,G s，每個(gè)連通分支至多有每個(gè)連通分支至多有k條邊，

6、且無奇度頂點(diǎn)，條邊，且無奇度頂點(diǎn)，并且設(shè)并且設(shè)G i與與C的公共頂點(diǎn)為的公共頂點(diǎn)為v* *ji，i1,2,1,2, ,s，由歸納假設(shè)可知，由歸納假設(shè)可知，G 1 1, ,G 2 2, , ,G s都是歐拉圖，都是歐拉圖，因而都存在歐拉回路因而都存在歐拉回路C i，i1,2,1,2, ,s。最后將最后將C還原（還原（即將刪除的邊重新加上即將刪除的邊重新加上），），并從并從C上的某頂點(diǎn)上的某頂點(diǎn)vr開始行遍，每遇到開始行遍，每遇到v* *ji，就行遍就行遍G i中的歐拉中的歐拉回路回路C i，i1,2,1,2, ,s，最后回到最后回到vr，得回路得回路vrv* *j1 1v* *j1 1v* *j

7、2 2v* *j2 2v* *jsv* *jsvr，此回路經(jīng)過此回路經(jīng)過G中每條邊一次且僅一次并行遍中每條邊一次且僅一次并行遍G中所有頂點(diǎn)，中所有頂點(diǎn)，因而它是因而它是G中的歐拉回路（中的歐拉回路（演示這條歐拉回路演示這條歐拉回路），），故故G為歐拉圖。為歐拉圖。 9歸納法證明示意圖歸納法證明示意圖 10定理定理15.215.2 無向圖無向圖G是半歐拉圖當(dāng)且僅當(dāng)是半歐拉圖當(dāng)且僅當(dāng)G是連通的，且是連通的，且G中恰有兩中恰有兩個(gè)奇度頂點(diǎn)。個(gè)奇度頂點(diǎn)。證明證明 必要性必要性。設(shè)。設(shè)G是是m條邊的條邊的n階無向圖，因?yàn)殡A無向圖，因?yàn)镚為半歐拉圖，為半歐拉圖，因而因而G中存在歐拉通路中存在歐拉通路( (

8、但不存在歐拉回路但不存在歐拉回路) )，設(shè)設(shè)vi0 0ej1 1vi1 1vim-1-1ejmvim為為G中一條歐拉通路，中一條歐拉通路，vi0 0vim。 vV( (G) )，若若v不在不在的端點(diǎn)出現(xiàn)，顯然的端點(diǎn)出現(xiàn)，顯然d( (v) )為偶數(shù)，為偶數(shù)，若若v在端點(diǎn)出現(xiàn)過，則在端點(diǎn)出現(xiàn)過，則d( (v) )為奇數(shù)，為奇數(shù)，因?yàn)橐驗(yàn)橹挥袃蓚€(gè)端點(diǎn)且不同，因而只有兩個(gè)端點(diǎn)且不同，因而G中只有兩個(gè)奇數(shù)頂點(diǎn)。中只有兩個(gè)奇數(shù)頂點(diǎn)。另外，另外，G的連通性是顯然的。的連通性是顯然的。半歐拉圖的判定定理半歐拉圖的判定定理 11定理定理15.215.2 無向圖無向圖G是半歐拉圖當(dāng)且僅當(dāng)是半歐拉圖當(dāng)且僅當(dāng)G是連通

9、的，且是連通的，且G中恰有兩中恰有兩個(gè)奇度頂點(diǎn)。個(gè)奇度頂點(diǎn)。證明證明 充分性充分性。設(shè)。設(shè)G的兩個(gè)奇度頂點(diǎn)分別為的兩個(gè)奇度頂點(diǎn)分別為u0 0和和v0 0，對對G加新邊（加新邊（u0 0, ,v0 0），），得得G G(u0 0, ,v0 0) )，則則G 是連通且無奇度頂點(diǎn)的圖，是連通且無奇度頂點(diǎn)的圖，由定理由定理15.115.1可知，可知，G 為歐拉圖，為歐拉圖，因而存在歐拉回路因而存在歐拉回路C ，而而CC -(-(u0 0, ,v0 0) )為為G中一條歐拉通路，中一條歐拉通路，所以所以G為半歐拉圖。為半歐拉圖。 半歐拉圖的判定定理半歐拉圖的判定定理 12有向歐拉圖的判定定理有向歐拉圖的

10、判定定理定理定理15.315.3 有向圖有向圖D是歐拉圖當(dāng)且僅當(dāng)是歐拉圖當(dāng)且僅當(dāng)D是強(qiáng)連通的且每個(gè)頂點(diǎn)的是強(qiáng)連通的且每個(gè)頂點(diǎn)的入度都等于出度。入度都等于出度。定理定理15.415.4 有向圖有向圖D是半歐拉圖當(dāng)且僅當(dāng)是半歐拉圖當(dāng)且僅當(dāng)D是是單向連通的，且單向連通的，且D中中恰有兩個(gè)奇度頂點(diǎn)，其中一個(gè)的入度比出度大恰有兩個(gè)奇度頂點(diǎn)，其中一個(gè)的入度比出度大1 1，另一個(gè)的出，另一個(gè)的出度比入度大度比入度大1 1，而其余頂點(diǎn)的入度都等于出度。，而其余頂點(diǎn)的入度都等于出度。( (舉例舉例) )定理定理15.515.5 G是非平凡的歐拉圖當(dāng)且僅當(dāng)是非平凡的歐拉圖當(dāng)且僅當(dāng)G是連通的且為若干個(gè)邊是連通的且為

11、若干個(gè)邊不重的圈的并。不重的圈的并。 13例例15.115.1 例例15.115.1 設(shè)設(shè)G是非平凡的且非環(huán)的歐拉圖，證明：是非平凡的且非環(huán)的歐拉圖，證明：(1)(1) ( (G)2)2。(2)(2)對于對于G中任意兩個(gè)不同頂點(diǎn)中任意兩個(gè)不同頂點(diǎn)u, ,v，都存在簡單回路都存在簡單回路C含含u和和v。證明證明 (1) (1)由定理由定理15.515.5可知，可知， eE( (G) )，存在圈存在圈C，e在在C中，中，因而因而p( (G- -e) )p( (G) )，故故e不是橋。不是橋。由由e的任意性的任意性(G)2)2，即即G是是2 2邊邊- -連通圖。連通圖。(2)(2) u, ,vV(

12、(G) )，uv，由由G的連通性可知，的連通性可知，u, ,v之間必存在路徑之間必存在路徑 1 1，設(shè)設(shè)G G- -E( ( 1 1) )，則在則在G 中中u與與v還必連通，還必連通，否則，否則，u與與v必處于必處于G 的不同的連通分支中，這說明在的不同的連通分支中，這說明在 1 1上存在上存在G中的橋，這與中的橋，這與(1)(1)矛盾。矛盾。于是在于是在G 中存在中存在u到到v的路徑的路徑 2 2，顯然顯然 1 1與與 2 2邊不重，邊不重，這說明這說明u, ,v處于處于 1 1 2 2形成的簡單回路上。形成的簡單回路上。 14求歐拉圖中歐拉回路的算法求歐拉圖中歐拉回路的算法Fleury算法

13、算法，能不走橋就不走橋能不走橋就不走橋 (1) (1) 任取任取v0 0V( (G) )，令令P0 0v0 0。(2) (2) 設(shè)設(shè)Piv0 0e1 1v1 1e2 2eivi已經(jīng)行遍，按下面方法來從已經(jīng)行遍，按下面方法來從 E( (G)-)-e1 1, ,e2 2, , ,ei 中選取中選取ei+1+1： (a) (a) ei+1+1與與vi相關(guān)聯(lián)；相關(guān)聯(lián)； ( (b) b) 除非無別的邊可供行遍，否則除非無別的邊可供行遍，否則ei+1+1不應(yīng)該為不應(yīng)該為 GiG-e1 1, ,e2 2, , ,ei 中的橋。中的橋。(3)(3)當(dāng)當(dāng)(2)(2)不能再進(jìn)行時(shí)，算法停止。不能再進(jìn)行時(shí)，算法停止

14、。 說明說明可以證明，當(dāng)算法停止時(shí)所得簡單回路可以證明，當(dāng)算法停止時(shí)所得簡單回路Pmv0 0e1 1v1 1e2 2emvm( (vmv0 0) )為為G中一條歐拉回路。中一條歐拉回路。 15FleuryFleury算法示例算法示例 16例例15.215.2下圖是給定的歐拉圖下圖是給定的歐拉圖G。某人用某人用Fleury算法求算法求G中的歐拉回路時(shí)中的歐拉回路時(shí)，走了簡單回路，走了簡單回路v2 2e2 2v3 3e3 3v4 4e1414v9 9e1010v2 2e1 1v1 1e8 8v8 8e9 9v2 2之后之后( (觀看他的觀看他的錯(cuò)誤走法錯(cuò)誤走法) )，無法行遍了，試分析在哪步他犯了

15、錯(cuò)誤，無法行遍了，試分析在哪步他犯了錯(cuò)誤? ? 解答解答 此人行遍此人行遍v8 8時(shí)犯了能不走橋就不走橋時(shí)犯了能不走橋就不走橋的錯(cuò)誤，因而他沒行遍出歐拉回路。的錯(cuò)誤，因而他沒行遍出歐拉回路。當(dāng)他走到當(dāng)他走到v8 8時(shí)，時(shí)，G-e2 2, ,e3 3, ,e1414, ,e1010, ,e1 1, ,e8 8 為下圖所示。為下圖所示。此時(shí)此時(shí)e9 9為該圖中的橋，而為該圖中的橋，而e7 7, ,e1111均不是橋，均不是橋，他不應(yīng)該走他不應(yīng)該走e9 9，而應(yīng)該走而應(yīng)該走e7 7或或e1111，他沒他沒有走，所以犯了錯(cuò)誤。注意，此人在行有走，所以犯了錯(cuò)誤。注意，此人在行遍中，在遍中，在v3 3遇到

16、過橋遇到過橋e3 3，v1 1處遇到過橋處遇到過橋e8 8，但當(dāng)時(shí)除橋外他無別的邊可走，所但當(dāng)時(shí)除橋外他無別的邊可走，所以當(dāng)時(shí)均走了橋，這是不會(huì)犯錯(cuò)誤的。以當(dāng)時(shí)均走了橋，這是不會(huì)犯錯(cuò)誤的。 17q 例例 在下圖中，恰有兩個(gè)奇結(jié)點(diǎn)在下圖中，恰有兩個(gè)奇結(jié)點(diǎn)4 4和和9 9，故存在，故存在EulerEuler路，按路，按照照FleuryFleury算法可得其中一條算法可得其中一條EulerEuler路為路為: :q ( (9,7,8,9,10,11,12,10,3,2,1,3,4,5,6,4)9,7,8,9,10,11,12,10,3,2,1,3,4,5,6,4)。127893456111210 1

17、8q HamiltonHamilton爵士（爵士（1805180518651865）在）在18591859年發(fā)明了一種游戲，年發(fā)明了一種游戲，用一個(gè)正實(shí)心的十二面體，它的二十個(gè)頂點(diǎn)標(biāo)有二十個(gè)城用一個(gè)正實(shí)心的十二面體，它的二十個(gè)頂點(diǎn)標(biāo)有二十個(gè)城市的名字，要求游戲者找一條沿著各邊通過每個(gè)頂點(diǎn)一次市的名字，要求游戲者找一條沿著各邊通過每個(gè)頂點(diǎn)一次且僅一次的閉合回路，即繞行世界問題。且僅一次的閉合回路，即繞行世界問題。HamiltonHamilton以以2525個(gè)個(gè)金幣的代價(jià)將他的設(shè)計(jì)賣給了一個(gè)玩具商。金幣的代價(jià)將他的設(shè)計(jì)賣給了一個(gè)玩具商。q 由于正十二面體是由由于正十二面體是由1212個(gè)相同的正五邊

18、形組成，且有個(gè)相同的正五邊形組成，且有2020個(gè)個(gè)頂點(diǎn)，該問題為怎樣才能沿著頂點(diǎn)，該問題為怎樣才能沿著1212面體的棱旅行，經(jīng)過每個(gè)面體的棱旅行，經(jīng)過每個(gè)城市恰好一次，然后回到家中。城市恰好一次，然后回到家中。HamiltonHamilton給出了這個(gè)問題給出了這個(gè)問題的肯定的答復(fù)。的肯定的答復(fù)。15.2 15.2 哈密頓圖哈密頓圖 19 (1) (2) 圖圖5 20哈密頓圖哈密頓圖 定義定義15.215.2 經(jīng)過圖（有向圖或無向圖）中經(jīng)過圖（有向圖或無向圖）中所有頂點(diǎn)一次且僅一所有頂點(diǎn)一次且僅一次的通路次的通路稱為稱為哈密頓通路哈密頓通路。經(jīng)過圖中。經(jīng)過圖中所有頂點(diǎn)一次且僅一所有頂點(diǎn)一次且僅

19、一次的回路次的回路稱為稱為哈密頓回路哈密頓回路。具有哈密頓回路的圖稱為。具有哈密頓回路的圖稱為哈密哈密頓圖頓圖，具有哈密頓通路但不具有哈密頓回路的圖稱為，具有哈密頓通路但不具有哈密頓回路的圖稱為半哈半哈密頓圖密頓圖。平凡圖是哈密頓圖。平凡圖是哈密頓圖。說明說明哈密頓通路是圖中生成的初級通路，哈密頓通路是圖中生成的初級通路，哈密頓回路是生成的初級回路。哈密頓回路是生成的初級回路。判斷一個(gè)圖是否為哈密頓圖，就是判斷能否將圖中所有頂判斷一個(gè)圖是否為哈密頓圖，就是判斷能否將圖中所有頂點(diǎn)都放置在一個(gè)初級回路點(diǎn)都放置在一個(gè)初級回路( (圈圈) )上，但這不是一件易事。上，但這不是一件易事。與判斷一個(gè)圖是否

20、為歐拉圖不一樣，到目前為止，人們還與判斷一個(gè)圖是否為歐拉圖不一樣，到目前為止，人們還沒有找到哈密頓圖簡單的充分必要條件。沒有找到哈密頓圖簡單的充分必要條件。 21例題例題(1)(2)(1)(2)是哈密頓圖。是哈密頓圖。(3)(3)是半哈密頓圖。是半哈密頓圖。(4)(4)既不是哈密頓圖，也不是半哈密頓圖。既不是哈密頓圖，也不是半哈密頓圖。 22定理定理15.6 15.6 定理定理15.615.6 設(shè)無向圖設(shè)無向圖G 是哈密頓圖，對于任意是哈密頓圖，對于任意V1 1 V，且且V1 1，均有均有p( (G- -V1 1)|)|V1 1| | 其中，其中，p( (G- -V1 1) )為為G- -V1

21、 1的連通分支數(shù)。的連通分支數(shù)。 證明證明 設(shè)設(shè)C為為G中任意一條哈密頓回路，中任意一條哈密頓回路，易知，當(dāng)易知，當(dāng)V1 1中頂點(diǎn)在中頂點(diǎn)在C上均不相鄰時(shí)，上均不相鄰時(shí)，p( (C- -V1 1) )達(dá)到最大值達(dá)到最大值| |V1 1| |，而當(dāng)而當(dāng)V1 1中頂點(diǎn)在中頂點(diǎn)在C上有彼此相鄰的情況時(shí)，上有彼此相鄰的情況時(shí)，均有均有p( (C- -V1 1) )| |V1 1| |，所以有所以有 p( (C- -V1 1) )| |V1 1| |。而而C是是G的的生成子圖，所以，有生成子圖，所以，有p( (G- -V1 1) )p( (C- -V1 1) )| |V1 1| |。說明說明本定理的條件

22、本定理的條件是哈密頓圖的必要條件，但不是充分條件。是哈密頓圖的必要條件，但不是充分條件?？梢则?yàn)證彼得松圖滿足定理中的條件，但不是哈密頓圖?？梢则?yàn)證彼得松圖滿足定理中的條件，但不是哈密頓圖。若一個(gè)圖不滿足定理中的條件，它一定不是哈密頓圖。若一個(gè)圖不滿足定理中的條件，它一定不是哈密頓圖。 23推論推論 推論推論 設(shè)無向圖設(shè)無向圖G 是半哈密頓圖，對于任意的是半哈密頓圖，對于任意的V1 1 V且且V1 1，均有均有 p( (G- -V1 1)|)|V1 1|+1 |+1 證明證明 設(shè)設(shè)P是是G中起于中起于u終于終于v的哈密頓通路，的哈密頓通路，令令G G(u, ,v)()(在在G的頂點(diǎn)的頂點(diǎn)u, ,

23、v之間加新邊之間加新邊) )，易知易知G 為哈密頓圖，為哈密頓圖，由定理由定理15.615.6可知，可知，p( (G - -V1 1)|)|V1 1| |。因此，因此，p( (G- -V1 1) ) p( (G - -V1 1-(-(u, ,v) p( (G - -V1 1)+1)+1 | |V1 1|+1 |+1 24例例15.315.3例例15.315.3 在下圖中給出的三個(gè)圖都是二部圖。它們中的哪些是在下圖中給出的三個(gè)圖都是二部圖。它們中的哪些是哈密頓圖？哪些是半哈密頓圖？為什么？哈密頓圖？哪些是半哈密頓圖？為什么？易知互補(bǔ)頂點(diǎn)子集易知互補(bǔ)頂點(diǎn)子集V1 1 a, ,f V2 2 b, ,

24、c, ,d, ,e 設(shè)此二部圖為設(shè)此二部圖為G1 1，則則G1 1 。p( (G1 1- -V1 1) )4|4|V1 1| |2 2，由由定理定理15.615.6及其推論可知，及其推論可知，G1 1不是哈密不是哈密頓圖，也不是半哈密頓圖。頓圖，也不是半哈密頓圖。 25例例15.315.3設(shè)圖為設(shè)圖為G2 2，則則G2 2 ，其中其中V1 1 a, ,g, ,h, ,i, ,c ，V2 2 b, ,e, ,f, ,j, ,k, ,d ，易知，易知，p( (G2 2- -V1 1) )| |V2 2| |6|6|V1 1| |5 5，由定理由定理15.615.6可知，可知，G2 2不是哈密頓圖，

25、不是哈密頓圖，但但G2 2是半哈密頓圖。是半哈密頓圖。baegjckhfid為為G2 2中一條哈密頓通路。中一條哈密頓通路。設(shè)圖為設(shè)圖為G3 3。G3 3 ，其中其中V1 1 a, ,c, ,g, ,h, ,e ，V2 2 b, ,d, ,i, ,j, ,f ，G3 3中存在哈密頓回路。中存在哈密頓回路。如如 abcdgihjefa，所以所以G3 3是哈密頓圖。是哈密頓圖。 26例例15.315.3的說明的說明q 哈密頓通路是經(jīng)過圖中所有頂點(diǎn)的一條初級通路。哈密頓通路是經(jīng)過圖中所有頂點(diǎn)的一條初級通路。q 哈密頓回路是經(jīng)過圖中所有頂點(diǎn)的初級回路。哈密頓回路是經(jīng)過圖中所有頂點(diǎn)的初級回路。 q 對于

26、二部圖還能得出下面結(jié)論：對于二部圖還能得出下面結(jié)論： 一般情況下，設(shè)二部圖一般情況下，設(shè)二部圖G ，| |V1 1| | |V2 2| |，且且| |V1 1| |2 2，| |V2 2| |2 2，由定理由定理15.615.6及其推論可以得出下面結(jié)論：及其推論可以得出下面結(jié)論：( (1) 1) 若若G是哈密頓圖，則是哈密頓圖，則| |V1 1| | |V2 2| |。( (2) 2) 若若G是半哈密頓圖，則是半哈密頓圖，則| |V2 2| | | |V1 1|+1|+1。( (3) 3) 若若| |V2 2| | |V1 1|+2|+2，則則G G不是哈密頓圖，也不是半哈密頓圖。不是哈密頓圖

27、，也不是半哈密頓圖。 例例15.415.4 設(shè)設(shè)G是是n階無向連通圖。證明：階無向連通圖。證明：若若G中有割點(diǎn)或橋，則中有割點(diǎn)或橋，則G不是不是哈密頓圖。哈密頓圖。證明證明 可可用定理用定理15.615.6證明。證明。 27例例15.415.4例例15.415.4 設(shè)設(shè)G是是n階無向連通圖。證明：若階無向連通圖。證明：若G中有割點(diǎn)或橋，則中有割點(diǎn)或橋，則G不不是哈密頓圖。是哈密頓圖。證明證明(1)(1)證明證明若若G中有割點(diǎn)，則中有割點(diǎn)，則G不是哈密頓圖。不是哈密頓圖。設(shè)設(shè)v為連通圖為連通圖G中一個(gè)割點(diǎn)，則中一個(gè)割點(diǎn)，則V v 為為G中的點(diǎn)割集，而中的點(diǎn)割集，而p( (G- -V )2)21

28、1| |V | |由定理由定理15.615.6可知可知G不是哈密頓圖。不是哈密頓圖。(2)(2)證明證明若若G中有橋，則中有橋，則G不是哈密頓圖。不是哈密頓圖。設(shè)設(shè)G中有橋，中有橋，e( (u, ,v) )為其中的一個(gè)橋。為其中的一個(gè)橋。若若u, ,v都是懸掛點(diǎn)，則都是懸掛點(diǎn)，則G為為K2 2，K2 2不是哈密頓圖。不是哈密頓圖。若若u, ,v中至少有一個(gè)，比如中至少有一個(gè)，比如u，d( (u)2)2，由于由于e與與u關(guān)聯(lián)，關(guān)聯(lián)，e為橋?yàn)闃?，所以，所以G- -u至少產(chǎn)生兩個(gè)連通分支，于是至少產(chǎn)生兩個(gè)連通分支，于是u為為G中割點(diǎn)。中割點(diǎn)。由由(1)(1)的討論可知，的討論可知，G不是哈密頓圖。不

29、是哈密頓圖。 28定理定理15.715.7定理定理15.715.7 設(shè)設(shè)G是是n階無向簡單圖，若對于階無向簡單圖，若對于G中任意不相鄰的頂中任意不相鄰的頂點(diǎn)點(diǎn)vi, ,vj，均有均有d( (vi)+)+d( (vj)n-1-1(15.1)(15.1)則則G中存在哈密頓通路。中存在哈密頓通路。 證明證明 首先證明首先證明G是連通圖。是連通圖。否則否則G至少有兩個(gè)連通分支，至少有兩個(gè)連通分支，設(shè)設(shè)G1 1, ,G2 2是階數(shù)為是階數(shù)為n1 1, ,n2 2的兩個(gè)連通分支，的兩個(gè)連通分支，設(shè)設(shè)v1 1V( (G1 1) )，v2 2V( (G2 2) )，因?yàn)橐驗(yàn)镚是簡單圖，所以是簡單圖，所以dG(

30、 (v1 1)+)+dG( (v2 2) )dG1 1( (v1 1)+)+dG2 2( (v2 2)n1 1-1+-1+n2 2-1-1n-2-2這與這與(15.1)(15.1)矛盾，所以矛盾，所以G必為連通圖。必為連通圖。 29定理定理15.715.7下面證下面證G中存在哈密頓通路。中存在哈密頓通路。設(shè)設(shè) v1 1v2 2vl為為G中用中用“擴(kuò)大路徑法擴(kuò)大路徑法”得到的得到的“極大路徑極大路徑”，即即 的始點(diǎn)的始點(diǎn)v1 1與終點(diǎn)與終點(diǎn)vl不與不與 外的頂點(diǎn)相鄰。顯然有外的頂點(diǎn)相鄰。顯然有l(wèi)n。 (1)(1)若若ln，則則 為為G中哈密頓通路。中哈密頓通路。(2)(2)若若ln，這說明這說明

31、 不是哈密頓通路，不是哈密頓通路，即即G中還存在著中還存在著 外的頂點(diǎn)。外的頂點(diǎn)。但可以證明但可以證明G中存在經(jīng)過中存在經(jīng)過 上所有頂點(diǎn)的圈上所有頂點(diǎn)的圈。( (a)a) 若若v1 1與與vl相鄰，即相鄰，即( (v1 1, ,vl) )E( (G) )，則則 ( (v1 1, ,vl) )為滿足要求的圈。為滿足要求的圈。 30定理定理15.715.7( (b)b)若若v1 1與與vl不相鄰，設(shè)不相鄰，設(shè)v1 1與與 上的上的vi1 1v2 2, ,vi2 2, , ,vik相鄰相鄰( (k2)2)( (否則否則 d( (v1 1)+)+d( (vl) )1+1+l-2=-2=l-1-1n-1

32、-1，這與這與( (15.1)15.1)矛盾矛盾) )此時(shí)，此時(shí)，vl至少與至少與vi2 2, , ,vik相鄰的頂點(diǎn)相鄰的頂點(diǎn)vi2-12-1, , ,vik-1-1之一相鄰之一相鄰( (否則否則 d( (v1 1)+)+d( (vl) )k+ +l-2-(-2-(k-1)-1)l-1-1n-1-1) )設(shè)設(shè)vl與與vir -1-1相鄰（相鄰（2 2rk），），見下圖所示。見下圖所示。于是，回路于是，回路Cv1 1v2 2vir -1-1vlvlr -1-1vivirv1 1過過上的所有頂點(diǎn)。上的所有頂點(diǎn)。 31定理定理15.715.7( (c)c)下面證明存在比下面證明存在比 更長的路徑。

33、更長的路徑。因?yàn)橐驗(yàn)閘 n，所以所以C外還有頂點(diǎn)，由外還有頂點(diǎn)，由G的連通性可知，的連通性可知，存在存在vl+1+1V( (G)-)-V( (C) )與與C上某頂點(diǎn)上某頂點(diǎn)vt相鄰，見下圖所示。相鄰，見下圖所示。刪除邊刪除邊(vt-1,vt)得路徑得路徑vt-1v1virvlvir-1vtvl+1比比 長度大長度大1，對對上的頂點(diǎn)重新排序，使其成為上的頂點(diǎn)重新排序，使其成為 v1v2vlvl+1，對對重復(fù)重復(fù)(a)(c)，在有限步內(nèi)一定得到在有限步內(nèi)一定得到G的哈密頓通路。的哈密頓通路。 32q幾點(diǎn)說明：幾點(diǎn)說明： 定理定理15.7是半哈密頓圖的充分條件是半哈密頓圖的充分條件, 但不是必要但不

34、是必要條件條件. 長度為長度為n 1(n 4)的路徑構(gòu)成的圖不滿足的路徑構(gòu)成的圖不滿足( )條件條件, 但它顯然是半哈密頓圖但它顯然是半哈密頓圖. 定理定理15.7的推論同樣不是哈密頓圖的必要條件的推論同樣不是哈密頓圖的必要條件, G為長為為長為n的圈的圈, 不滿足不滿足()條件條件, 但它當(dāng)然是哈但它當(dāng)然是哈密頓圖密頓圖. 由定理由定理15.7的推論可知的推論可知, Kn(n 3)均為哈密頓圖均為哈密頓圖. 33定理定理15.715.7的推論的推論推論推論 設(shè)設(shè)G為為n( (n3)3)階無向簡單圖，若對于階無向簡單圖，若對于G中任意兩個(gè)不相鄰的中任意兩個(gè)不相鄰的頂點(diǎn)頂點(diǎn)vi, ,vj，均有均

35、有 d( (vi)+)+d( (vj) )n(15.2)(15.2)則則G中存在哈密頓回路，從而中存在哈密頓回路，從而G為哈密頓圖。為哈密頓圖。 證明證明 由定理由定理15.715.7可知，可知，G中存在哈密頓通路，中存在哈密頓通路，設(shè)設(shè)v1 1v2 2vn為為G中一條哈密頓通路，中一條哈密頓通路，若若v1 1與與vn相鄰，設(shè)邊相鄰，設(shè)邊e( (v1 1, ,vn) )，則則 e 為為G中哈密頓回路。中哈密頓回路。若若v1 1與與vn不相鄰，應(yīng)用不相鄰，應(yīng)用( (15.2)15.2)，同定理，同定理15.715.7證明中的證明中的( (2)2)類似，可類似，可證明存在過證明存在過上各頂點(diǎn)的圈，

36、上各頂點(diǎn)的圈，此圈即為此圈即為G中的哈密頓回路。中的哈密頓回路。 34定理定理15.815.8定理定理15.815.8 設(shè)設(shè)u, ,v為為n階無向圖階無向圖G中兩個(gè)不相鄰的頂點(diǎn)，且中兩個(gè)不相鄰的頂點(diǎn)，且d( (u)+)+d( (v) )n，則則G為哈密頓圖當(dāng)且僅當(dāng)為哈密頓圖當(dāng)且僅當(dāng)G( (u, ,v) )為哈密為哈密頓圖頓圖( ( (u, ,v) )是加的新邊是加的新邊) )。 證明證明 必要性：若必要性：若G為哈密頓圖，則顯然為哈密頓圖，則顯然G( (u, ,v) )為哈密頓圖；為哈密頓圖； 充分性：設(shè)充分性：設(shè)G( (u, ,v) )為哈密頓圖，并設(shè)為哈密頓圖，并設(shè)C C為為G( (u,

37、,v) )的的一一個(gè)哈密頓回路，若邊個(gè)哈密頓回路，若邊( (u, ,v) )不在不在C C中，則中，則C C也是也是G G的哈密頓回的哈密頓回路。若邊路。若邊( (u, ,v) )在在C C中，不妨設(shè)中，不妨設(shè)C=vC=v1 1v v2 2v vn nv v1 1( (其中其中v v1 1=u,v=u,v2 2=v) =v) 下面分兩種情況討論：下面分兩種情況討論： 1: 1: 若存在若存在i(2in)i(2in)，使得，使得u u與與v vi i相鄰接，相鄰接，v v與與v vi+1i+1相鄰接，則相鄰接，則G G必有哈密頓回路必有哈密頓回路C=uvC=uvi iv vi-1i-1vvvvi

38、+1i+1v vn nu u 35定理定理15.815.8證明證明 2: 2: 若不存在這樣的若不存在這樣的i i，則因?yàn)椋瑒t因?yàn)関 v3 3v v4 4v vn-1n-1v vn n中有中有d(u)d(u)個(gè)結(jié)點(diǎn)與個(gè)結(jié)點(diǎn)與u u相鄰，所以在相鄰，所以在v v3 3v v4 4v v5 5v vn n中至少有中至少有d(u)d(u)個(gè)結(jié)點(diǎn)不與個(gè)結(jié)點(diǎn)不與v v相鄰，相鄰，因而因而d(v)d(v) n-1-d(u)n-1-d(u)即即d(v)+d(ud(v)+d(u)n )n 矛盾矛盾 V1=uV2=vv3v4viVi+1Vn-1vn 36例例15.515.5例例15.515.5 在某次國際會(huì)議的

39、預(yù)備會(huì)議中，共有在某次國際會(huì)議的預(yù)備會(huì)議中，共有8 8人參加，他們來自不人參加，他們來自不同的國家。已知他們中任何兩個(gè)無共同語言的人中的每一個(gè)，與同的國家。已知他們中任何兩個(gè)無共同語言的人中的每一個(gè)，與其余有共同語言的人數(shù)之和大于或等于其余有共同語言的人數(shù)之和大于或等于8 8，問能否將這，問能否將這8 8個(gè)人排在個(gè)人排在圓桌旁，使其任何人都能與兩邊的人交談。圓桌旁，使其任何人都能與兩邊的人交談。 解答解答 設(shè)設(shè)8 8個(gè)人分別為個(gè)人分別為v1 1, ,v2 2, , ,v8 8，作無向簡單圖作無向簡單圖G ，其中其中V v1 1, ,v2 2, , ,v8 8 ， vi, ,vjV，且且ij，若

40、若vi與與vj有共同語言，就在有共同語言，就在vi, ,vj之間連無向邊之間連無向邊( (vi, ,vj) )，由此組成邊集合由此組成邊集合E，則則G為為8 8階無向簡單圖，階無向簡單圖， viV，d( (vi) )為與為與vi有共同語言的人數(shù)。有共同語言的人數(shù)。由已知條件可知，由已知條件可知， vi, ,vjV且且ij，均有均有d( (vi)+)+d( (vj) )8 8。由由定理定理15.715.7的推論可知，的推論可知，G中存在哈密頓回路，中存在哈密頓回路，設(shè)設(shè)Cvi1 1vi2 2vi8 8為為G中一條哈密頓回路，中一條哈密頓回路，按這條回路的順序安排座次即可。按這條回路的順序安排座次

41、即可。哈密頓圖是能將圖中所有頂哈密頓圖是能將圖中所有頂點(diǎn)都能安排在某個(gè)初級回路點(diǎn)都能安排在某個(gè)初級回路上的圖上的圖。 37定理定理15.915.9定理定理15.915.9 若若D為為n( (n2)2)階階競賽圖，則競賽圖，則D中具有哈密頓通路。中具有哈密頓通路。 證明證明 對對n作歸納法。作歸納法。n2 2時(shí)，時(shí)，D的的基圖基圖為為K2 2，結(jié)論成立。結(jié)論成立。設(shè)設(shè)nk時(shí)結(jié)論成立。現(xiàn)在設(shè)時(shí)結(jié)論成立?，F(xiàn)在設(shè)nk+1+1。設(shè)設(shè)V( (D) ) v1 1, ,v2 2, , ,vk, ,vk+1+1 。令令D1 1D- -vk+1+1，易知易知D1 1為為k階競賽圖，階競賽圖，由歸納假設(shè)可知，由歸納

42、假設(shè)可知，D1 1存在哈密頓通路，存在哈密頓通路，設(shè)設(shè)1 1v 1 1v 2 2v k為其中一條。為其中一條。 38定理定理15.915.9下面證明下面證明vk+1+1可擴(kuò)到可擴(kuò)到1 1中去。中去。若存在若存在v r( (1 1rk) )，有有 E( (D) )，i1,2,1,2, ,r -1-1，而而 E( (D) )，見左圖所示，見左圖所示，則則v 1 1v 2 2v r-1-1vk+1+1v rv k為為D中哈密頓通路。中哈密頓通路。否則否則 i1,2,1,2, ,k ，均有均有 E( (D) )，見右圖所示，見右圖所示，則則 為為D中哈密頓通路。中哈密頓通路。 39例例15.615.6

43、下圖所示的三個(gè)圖中哪些是哈密頓圖？哪些是半哈密頓圖？下圖所示的三個(gè)圖中哪些是哈密頓圖？哪些是半哈密頓圖？ ( (1)1)存在哈密頓回路，所以存在哈密頓回路，所以( (1)1)為哈密頓圖。為哈密頓圖。( (2)2)取取V1 1 a, ,b, ,c, ,d, ,e ，從圖中刪除從圖中刪除V1 1得得7 7個(gè)連通分支，個(gè)連通分支， 由定理由定理15.615.6和和推論可知，不是哈密頓圖，也不是半哈密頓圖。推論可知，不是哈密頓圖，也不是半哈密頓圖。( (3)3)取取V1 1 b, ,e, ,h ，從圖中刪除從圖中刪除V1 1得得4 4個(gè)連通分支，由定理個(gè)連通分支，由定理15.615.6可可知，它不是哈

44、密頓圖。但存在哈密頓通路，所以是半哈密頓圖。知，它不是哈密頓圖。但存在哈密頓通路，所以是半哈密頓圖。 40 滿足定理滿足定理15.7推論的條件推論的條件(). 完全圖完全圖Kn(n 3)中任何兩個(gè)頂點(diǎn)中任何兩個(gè)頂點(diǎn)u, v, 均有均有 d(u)+d(v) = 2(n 1) n(n 3), 所以所以Kn為哈密頓圖為哈密頓圖. 破壞定理破壞定理15.6的條件的圖不是哈密頓圖的條件的圖不是哈密頓圖. 例例 在四分之一國際象棋盤在四分之一國際象棋盤(4 4方格組成方格組成)上上跳馬無解跳馬無解. 在國際象棋盤上跳馬有解在國際象棋盤上跳馬有解. 41 (1) (2) 圖圖10 令令V1=a, b, c,

45、 d, 則則p(G V1) = 6 4, 由定理由定理15.6可知圖可知圖中無哈密頓回路中無哈密頓回路.在國際象棋盤上跳馬有解在國際象棋盤上跳馬有解, 試試看試試看. 4215.3 15.3 帶權(quán)圖與貨郎擔(dān)問題帶權(quán)圖與貨郎擔(dān)問題定義定義15.315.3 給定圖給定圖G (G為無向圖或有向圖為無向圖或有向圖) )，設(shè)，設(shè)W：ER( (R為實(shí)數(shù)集為實(shí)數(shù)集) )，對，對G中任意的邊中任意的邊e( (vi, ,vj)()(G為有向圖為有向圖時(shí)，時(shí)，e )，設(shè)設(shè)W( (e) )wij，稱實(shí)數(shù)稱實(shí)數(shù)wij為邊為邊e上的權(quán)，并上的權(quán)，并將將wij標(biāo)注在邊標(biāo)注在邊e上，稱上，稱G為為帶權(quán)圖帶權(quán)圖，此時(shí)常將帶權(quán)

46、圖，此時(shí)常將帶權(quán)圖G記作記作 。)E(GeW(e)E(GeW(e)設(shè)設(shè)G G， 稱稱W( (e) )為為G 的權(quán)，并記作的權(quán)，并記作W( (G ) )，即即 W( (G ) )帶權(quán)圖應(yīng)用的領(lǐng)域是相當(dāng)廣泛的，許多圖論算法都是針帶權(quán)圖應(yīng)用的領(lǐng)域是相當(dāng)廣泛的，許多圖論算法都是針對帶權(quán)圖的。對帶權(quán)圖的。 43貨郎擔(dān)問題貨郎擔(dān)問題q 設(shè)有設(shè)有n個(gè)城市，城市之間均有道路，道路的長度均大于或等于個(gè)城市，城市之間均有道路，道路的長度均大于或等于0 0，可能是，可能是（對應(yīng)關(guān)聯(lián)的城市之間無交通線）。一個(gè)旅行商（對應(yīng)關(guān)聯(lián)的城市之間無交通線）。一個(gè)旅行商從某個(gè)城市出發(fā)，要從某個(gè)城市出發(fā)，要經(jīng)過每個(gè)城市一次且僅一次經(jīng)

47、過每個(gè)城市一次且僅一次，最后回到，最后回到出發(fā)的城市，問他如何走才能使他出發(fā)的城市，問他如何走才能使他走的路線最短走的路線最短？這就是著名的這就是著名的旅行商問題旅行商問題或或貨郎擔(dān)問題貨郎擔(dān)問題。q 這個(gè)問題可化歸為如下的圖論問題。這個(gè)問題可化歸為如下的圖論問題。設(shè)設(shè)G ，為一個(gè)為一個(gè)n階完全帶權(quán)圖階完全帶權(quán)圖Kn，各邊的權(quán)非負(fù)，各邊的權(quán)非負(fù)，且有的邊的權(quán)可能為且有的邊的權(quán)可能為。求求G G中一條最短的哈密頓回路中一條最短的哈密頓回路，這就，這就是貨郎擔(dān)問題的數(shù)學(xué)模型。是貨郎擔(dān)問題的數(shù)學(xué)模型。q 此問題中不同哈密頓回路的含義：此問題中不同哈密頓回路的含義：將圖中生成圈看成一個(gè)哈密頓回路，即不

48、考慮始點(diǎn)將圖中生成圈看成一個(gè)哈密頓回路，即不考慮始點(diǎn)( (終點(diǎn)終點(diǎn)) )的的區(qū)別以及順時(shí)針行遍與逆時(shí)針行遍的區(qū)別。區(qū)別以及順時(shí)針行遍與逆時(shí)針行遍的區(qū)別。 44例例15.715.7例例15.715.7 下下圖為圖為4 4階完全帶權(quán)圖階完全帶權(quán)圖K4 4。求出它的不同的哈密頓回路求出它的不同的哈密頓回路，并指出最短的哈密頓回路。，并指出最短的哈密頓回路。解答解答 由于貨郎擔(dān)問題中不同哈密頓回路的含義可知，求哈密頓由于貨郎擔(dān)問題中不同哈密頓回路的含義可知，求哈密頓回路從任何頂點(diǎn)出發(fā)都可以。下面先求出從回路從任何頂點(diǎn)出發(fā)都可以。下面先求出從a a點(diǎn)出發(fā)，考慮順點(diǎn)出發(fā)，考慮順時(shí)針與逆時(shí)針順序的不同的哈密

49、頓回路。時(shí)針與逆時(shí)針順序的不同的哈密頓回路。C1 1abcda C2 2abdcaC3 3acbdaC4 4acdbaC5 5adbcaC6 6adcba 45帶權(quán)圖的說明帶權(quán)圖的說明q n階完全帶權(quán)圖中共存在階完全帶權(quán)圖中共存在( (n-1)!/2-1)!/2種不同的哈密頓回路，經(jīng)種不同的哈密頓回路，經(jīng)過比較，可找出最短哈密頓回路。過比較，可找出最短哈密頓回路。q n4 4時(shí)，時(shí)， 有有3 3種不同哈密頓回路。種不同哈密頓回路。n5 5時(shí)，時(shí)， 有有1212種，種，n6 6時(shí)，時(shí)， 有有6060種，種，n7 7時(shí)，時(shí)， 有有360360種，種，n1010時(shí)，有時(shí)，有5 59!=1 814 4

50、009!=1 814 400種，種，。q 由此可見貨郎擔(dān)問題的計(jì)算量是相當(dāng)大的。由此可見貨郎擔(dān)問題的計(jì)算量是相當(dāng)大的。q 對于貨郎擔(dān)問題，人們一方面還在尋找好的算法，另一方對于貨郎擔(dān)問題，人們一方面還在尋找好的算法，另一方面也在尋找各種近似算法。面也在尋找各種近似算法。 46中國郵遞員問題中國郵遞員問題q 一名郵遞員帶著要分發(fā)的郵件從郵局出發(fā)，經(jīng)過要分發(fā)的一名郵遞員帶著要分發(fā)的郵件從郵局出發(fā)，經(jīng)過要分發(fā)的每個(gè)街道，送完郵件后又返回郵局。如果他必須至少一次每個(gè)街道，送完郵件后又返回郵局。如果他必須至少一次走過他管轄范圍內(nèi)的每一條街道，如何選擇投遞路線，使走過他管轄范圍內(nèi)的每一條街道，如何選擇投遞

51、路線，使郵遞員走盡可能少的路程。郵遞員走盡可能少的路程。q 這個(gè)問題是由我國數(shù)學(xué)家管梅谷先生（山東師范大學(xué)數(shù)學(xué)這個(gè)問題是由我國數(shù)學(xué)家管梅谷先生（山東師范大學(xué)數(shù)學(xué)系教授）在系教授）在19601960年首次提出的，因此在國際上稱之為中國年首次提出的，因此在國際上稱之為中國郵遞員問題。郵遞員問題。q 用圖論的述語，在一個(gè)連通的賦權(quán)圖用圖論的述語，在一個(gè)連通的賦權(quán)圖G( (V, ,E) )中，要尋找一中，要尋找一條回路，使該回路包含條回路，使該回路包含G中的每條邊至少一次，且該回路的中的每條邊至少一次，且該回路的權(quán)數(shù)最小。也就是說要從包含權(quán)數(shù)最小。也就是說要從包含G G的每條邊的回路中找一條權(quán)的每條邊

52、的回路中找一條權(quán)數(shù)最小的回路。數(shù)最小的回路。 47基本要求基本要求q 深刻理解歐拉圖與半歐拉圖的定義及判別定理。深刻理解歐拉圖與半歐拉圖的定義及判別定理。q 會(huì)用會(huì)用Fleury算法求出歐拉圖中的歐拉回路。算法求出歐拉圖中的歐拉回路。q 深刻理解哈密頓圖及半哈密頓圖的定義。深刻理解哈密頓圖及半哈密頓圖的定義。q 會(huì)用破壞哈密頓圖應(yīng)滿足的某些必要條件的方法判斷某些會(huì)用破壞哈密頓圖應(yīng)滿足的某些必要條件的方法判斷某些圖不是哈密頓圖。圖不是哈密頓圖。q 會(huì)用滿足哈密頓圖的充分條件的方法判斷某些圖是哈密頓會(huì)用滿足哈密頓圖的充分條件的方法判斷某些圖是哈密頓圖。圖。q 嚴(yán)格地分清哈密頓圖必要條件和充分條件，千萬不能將必嚴(yán)格地分清哈密頓圖必要條件和充分條件，千萬不能將必要條件當(dāng)充分條件，同樣地，也不能將充分條件當(dāng)成必要要條件當(dāng)充分條件，同樣地，也不能將充分條件當(dāng)成必要條件。條件。 48