離散數(shù)學(xué)課件第十章-幾種圖的介紹

第十章幾種圖的介紹離散數(shù)學(xué)陳志奎主編人民郵電出版社前言自從1736年歐拉（L.Euler）利用圖論的思想解決了哥尼斯堡（Konigsberg）七橋問(wèn)題以來(lái)，圖論經(jīng)歷了漫長(zhǎng)的發(fā)展道路。在很長(zhǎng)一段時(shí)期內(nèi)，圖論被當(dāng)成是數(shù)學(xué)家的智力游戲，解決一些著名的難題，曾經(jīng)吸引了眾多的學(xué)者。圖論中許多的概論和定理的建立都與解決這些問(wèn)題有關(guān)。1859年，英國(guó)數(shù)學(xué)家哈密頓發(fā)明了一種游戲：用一個(gè)規(guī)則的實(shí)心十二面體，它的20個(gè)頂點(diǎn)標(biāo)出世界著名的20個(gè)城市，要求游戲者找一條沿著各邊通過(guò)每個(gè)頂點(diǎn)剛好一次的閉回路，即「繞行世界」。用圖論的語(yǔ)言來(lái)說(shuō)，游戲的目的是在十二面體的圖中找出一個(gè)生成圈。這個(gè)問(wèn)題后來(lái)就叫做哈密頓問(wèn)題。由于運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)和編碼理論中的很多問(wèn)題都可以化為哈密頓問(wèn)題，從而引起廣泛的關(guān)注和研究。前言在圖論的歷史中，還有一個(gè)最著名的問(wèn)題——四色猜想。這個(gè)猜想說(shuō)，在一個(gè)平面或球面上的任何地圖能夠只用四種顏色來(lái)著色，使得沒(méi)有兩個(gè)相鄰的國(guó)家有相同的顏色。每個(gè)國(guó)家必須由一個(gè)單連通域構(gòu)成，而兩個(gè)國(guó)家相鄰是指它們有一段公共的邊界，而不僅僅只有一個(gè)公共點(diǎn)。四色猜想有一段有趣的歷史。每個(gè)地圖可以導(dǎo)出一個(gè)圖，其中國(guó)家都是點(diǎn)，當(dāng)相應(yīng)的兩個(gè)國(guó)家相鄰時(shí)這兩個(gè)點(diǎn)用一條線來(lái)連接。所以四色猜想是圖論中的一個(gè)問(wèn)題。它對(duì)圖的著色理論、平面圖理論、代數(shù)拓?fù)鋱D論等分支的發(fā)展起到推動(dòng)作用。前言在電子計(jì)算機(jī)問(wèn)世后，圖論的應(yīng)用范圍更加廣泛，在解決運(yùn)籌學(xué)、信息論、控制論、網(wǎng)絡(luò)理論、博奕論、化學(xué)、社會(huì)科學(xué)、經(jīng)濟(jì)學(xué)、建筑學(xué)、心理學(xué)、語(yǔ)言學(xué)和計(jì)算機(jī)科學(xué)中的問(wèn)題時(shí)，扮演著越來(lái)越重要的角色，受到工程界和數(shù)學(xué)界的特別重視，成為解決許多實(shí)際問(wèn)題的基本工具之一。本章將結(jié)合圖論基礎(chǔ)知識(shí)，進(jìn)一步介紹一些常用的基本圖類，如歐拉圖、哈密爾頓圖、二部圖、平面圖、網(wǎng)絡(luò)等，除研究每種圖類的本質(zhì)特征之外，都力求結(jié)合一些實(shí)際問(wèn)題來(lái)闡明圖論的廣泛可應(yīng)用性，介紹一些最基本的圖論算法，使讀者對(duì)圖的理論和應(yīng)用這兩個(gè)方面都有一定的了解。PART01歐拉圖主要內(nèi)容PART02哈密爾頓圖PART03二部圖及匹配PART04平面圖PART05網(wǎng)絡(luò)PART06圖的示例分析10.1歐拉圖定義10.1圖G中包含其所有邊的簡(jiǎn)單開(kāi)路徑稱為圖G的歐拉路徑，圖G中包含其所有邊的簡(jiǎn)單閉路徑稱為G的歐拉閉路。

圖10.1哥尼斯堡七橋

圖10.2哥尼斯堡七橋問(wèn)題的圖610.1歐拉圖例10.1圖10.3中（a）是歐拉閉路，（c）是歐拉路徑，（b）既不是歐拉路徑也不是歐拉閉路。圖10.3710.1歐拉圖定義10.2每個(gè)結(jié)點(diǎn)都是偶結(jié)點(diǎn)的連通無(wú)向圖稱為歐拉圖。每個(gè)結(jié)點(diǎn)的出度和入度相等的連通有向圖稱為歐拉有向圖。例10.2圖10.4中（b）是歐拉有向圖。圖10.4810.1歐拉圖定理10.1設(shè)G是連通無(wú)向圖，G是歐拉圖，當(dāng)且僅當(dāng)G有歐拉閉路。910.1歐拉圖定理10.2

設(shè)G=<V，E，>為連通無(wú)向圖，且，

，則G有一條從至的歐拉路徑當(dāng)且僅當(dāng)G恰有兩個(gè)奇結(jié)點(diǎn)和。1010.1歐拉圖定理10.3設(shè)G為弱連通的有向圖。G是歐拉有向圖，當(dāng)且僅當(dāng)G有歐拉閉路。定理10.4設(shè)G為弱連通有向圖。和為G的兩個(gè)不同結(jié)點(diǎn)。G有一條從至的歐拉路徑，當(dāng)且僅當(dāng)=+1，=-1，且對(duì)G的其他結(jié)點(diǎn)v有=1110.1歐拉圖定理10.5如果和是可運(yùn)算的歐拉圖，則是歐拉圖。由定理10.5可得圖10.5圖10.512PART01歐拉圖主要內(nèi)容PART02哈密爾頓圖PART03二部圖及匹配PART04平面圖PART05網(wǎng)絡(luò)PART06圖的示例分析10.2哈密爾頓圖愛(ài)爾蘭數(shù)學(xué)家哈密爾頓（WilliamHamilton）爵士1859年提出了一個(gè)“周游世界”的游戲。這個(gè)游戲把一個(gè)正十二面體的二十個(gè)頂點(diǎn)看成地球上的二十個(gè)城市。棱線看成是連接城市的航路（航空、航海線或陸路交通線），要求游戲者沿棱線走，尋找一條經(jīng)過(guò)所有結(jié)點(diǎn)（即城市）一次且僅一次的回路，如圖10.6（a）所示。也就是在圖10.6（b）中找一條包含所有結(jié)點(diǎn)的圈。圖（b）中的粗線所構(gòu)成的圈就是這個(gè)問(wèn)題的回答。與歐拉圖不同，哈密爾頓圖是遍歷圖中的每個(gè)結(jié)點(diǎn)，一條哈密爾頓回路不會(huì)在兩個(gè)結(jié)點(diǎn)間走兩次以上，因此沒(méi)有必要在有向圖中討論。14圖10.610.2哈密爾頓圖愛(ài)爾蘭數(shù)學(xué)家哈密爾頓（WilliamHamilton）爵士1859年提出了一個(gè)“周游世界”的游戲。這個(gè)游戲把一個(gè)正十二面體的二十個(gè)頂點(diǎn)看成地球上的二十個(gè)城市。棱線看成是連接城市的航路（航空、航海線或陸路交通線），要求游戲者沿棱線走，尋找一條經(jīng)過(guò)所有結(jié)點(diǎn)（即城市）一次且僅一次的回路，如圖10.6（a）所示。也就是在圖10.6（b）中找一條包含所有結(jié)點(diǎn)的圈。圖（b）中的粗線所構(gòu)成的圈就是這個(gè)問(wèn)題的回答。與歐拉圖不同，哈密爾頓圖是遍歷圖中的每個(gè)結(jié)點(diǎn)，一條哈密爾頓回路不會(huì)在兩個(gè)結(jié)點(diǎn)間走兩次以上，因此沒(méi)有必要在有向圖中討論。15圖10.610.2哈密爾頓圖定義10.3給定無(wú)向圖G，圖G中包含其所有頂點(diǎn)的簡(jiǎn)單開(kāi)路徑稱為圖G的哈密爾頓路徑，圖G中包含其所有頂點(diǎn)的簡(jiǎn)單閉路徑稱為G的哈密爾頓回路。具有哈密頓回路的圖稱為哈密爾頓圖。由定義可知哈密爾頓圈與哈密爾頓路通過(guò)圖G中的每個(gè)結(jié)點(diǎn)一次且僅一次，例如圖10.6（b）就是哈密爾頓圖（哈密爾頓圈用實(shí)線標(biāo)出）。1610.2哈密爾頓圖例10.3圖10.7中，圖（a）、（b）中有哈密爾頓圈，圖（c）中有哈密爾頓路，（d）中既沒(méi)有哈密爾頓圈也沒(méi)有哈密爾頓路。圖10.7

哈密爾頓圖和歐拉圖相比，雖然考慮的都是遍歷問(wèn)題，但是側(cè)重點(diǎn)不同。歐拉圖遍歷的是邊，而哈密爾頓圖遍歷的是結(jié)點(diǎn)。另外兩者的判定困難程度也不一樣，前面我們已經(jīng)給出了判定歐拉圖的充分必要條件，但對(duì)于哈密爾頓圖的判定，至今還沒(méi)有找出判定的充要條件，只能給出若干必要條件或充分條件。1710.2哈密爾頓圖定理10.6若G是哈密爾頓圖，則對(duì)于結(jié)點(diǎn)集的任一非空真子集

有。其中表示在G中刪去S中的結(jié)點(diǎn)后所構(gòu)成的圖，表示的連通分支數(shù)。18哈密爾頓圖的必要條件可用來(lái)判定某些圖不是哈密爾頓圖，只要能夠找到不滿足定理?xiàng)l件的結(jié)點(diǎn)集

V的非空子集

S。10.2哈密爾頓圖例10.4圖10.8（a）不是哈密爾頓圖。

圖10.8（a）中共有9個(gè)結(jié)點(diǎn)，如果取結(jié)點(diǎn)集S={3個(gè)白點(diǎn)}，即。而這時(shí)（如圖（b））。這說(shuō)明圖10.8（a）不是哈密爾頓圖。但要注意若一個(gè)圖滿足定理10.6的條件也不能保證這個(gè)圖一定是哈密爾頓圖，如圖10.8（c）。19圖10.810.2哈密爾頓圖定理10.7設(shè)圖G是具有n（≥3）個(gè)結(jié)點(diǎn)的無(wú)向簡(jiǎn)單圖，如果G中每一對(duì)結(jié)點(diǎn)度數(shù)之和大于等于n-1，則在G中存在一條哈密爾頓路。定理10.8若G是具有n（≥3）個(gè)結(jié)點(diǎn)的無(wú)向簡(jiǎn)單圖，對(duì)于G中每一對(duì)不相鄰的結(jié)點(diǎn)均有，則G是一個(gè)哈密爾頓圖。定理10.7和10.8都是充分條件，即滿足這些條件的圖一定是哈密爾頓圖。但不是所有的哈密爾頓圖都滿足這些條件。例如圖10.9是哈密爾頓圖,但它不滿足上述定理的條件。20圖10.910.2哈密爾頓圖例10.5某地有5個(gè)風(fēng)景點(diǎn)。若每個(gè)景點(diǎn)均有兩條道路與其它景點(diǎn)相通，問(wèn)是否可經(jīng)過(guò)每個(gè)景點(diǎn)恰好一次而游完這5處？解：將景點(diǎn)作為結(jié)點(diǎn)，道路作為邊，則得到一個(gè)有5個(gè)結(jié)點(diǎn)的無(wú)向圖。由題意，對(duì)每個(gè)結(jié)點(diǎn)，有則對(duì)任兩點(diǎn)，均有可知此圖一定有一條哈密爾頓路，本題有解。2110.2哈密爾頓圖例10.6今有和7人，已知下列事實(shí)。

a講英語(yǔ)； b講英語(yǔ)和漢語(yǔ)；

c講英語(yǔ)、意大利語(yǔ)和俄語(yǔ)； d講日語(yǔ)和漢語(yǔ)；

e講德國(guó)和意大利語(yǔ)； f講法語(yǔ)、日語(yǔ)和俄語(yǔ)；

g講法語(yǔ)和德語(yǔ)。試問(wèn)這7個(gè)人應(yīng)如何排座位，才能使每個(gè)人都能和他身邊的人交談？22解：設(shè)無(wú)向圖，其中圖G是連通圖，如圖10.10（a）所示。將這7個(gè)人排座圍圓桌而坐，使得每個(gè)人能與兩邊的人交談，即在圖10.10（a）中找哈密爾頓回路。經(jīng)觀察該回路是。即按照?qǐng)D10.10（b）安排座位即可。PART01歐拉圖主要內(nèi)容PART02哈密爾頓圖PART03二部圖及匹配PART04平面圖PART05網(wǎng)絡(luò)PART06圖的示例分析10.3二部圖及匹配定義10.4設(shè)無(wú)向圖G=<V，E，>。如果存在V的劃分{,}，使得中的任何兩個(gè)結(jié)點(diǎn)都不相鄰（i=1,2），則稱G為二部圖，和稱為G的互補(bǔ)結(jié)點(diǎn)子集。顯然，二部圖沒(méi)有自圈。與二部圖的一條邊關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn)一定分屬于兩個(gè)互補(bǔ)結(jié)點(diǎn)子集。一般來(lái)說(shuō)，二部圖的互補(bǔ)結(jié)點(diǎn)子集的劃分不是唯一的。如圖10.11的二部圖，和是它的互補(bǔ)結(jié)點(diǎn)子集，

和

也是它的互補(bǔ)結(jié)點(diǎn)子集。圖10.11二部圖2410.3二部圖及匹配一個(gè)無(wú)向圖如果能畫(huà)成上面的樣式，很容易判定它是二部圖。有些圖雖然表面上不是上面的樣式，但經(jīng)過(guò)改畫(huà)就能成為上面的樣式，仍可判定它是一個(gè)二部圖，如圖10.12中（a）可改畫(huà)成圖（b），圖（c）可改畫(huà)成圖（d）?？梢钥闯觯鼈?nèi)允嵌繄D。圖10.122510.3二部圖及匹配定理10.9設(shè)G是階大于1的無(wú)向圖。G是二部圖，當(dāng)且僅當(dāng)G的所有回路長(zhǎng)度均為偶數(shù)。定義10.5設(shè)和是簡(jiǎn)單二部圖G的互補(bǔ)結(jié)點(diǎn)子集，如果中的每個(gè)結(jié)點(diǎn)與中的每個(gè)結(jié)點(diǎn)相鄰，則稱G為完全二部圖。

我們把互補(bǔ)結(jié)點(diǎn)子集分別包含m和n個(gè)結(jié)點(diǎn)的完全二部圖記為。圖10.14畫(huà)出了的兩個(gè)圖示。很重要，我們?cè)谟懻搱D的平面性時(shí)還要用到它。2610.3二部圖及匹配二部圖的主要應(yīng)用是匹配，“匹配”是圖論中的一個(gè)重要內(nèi)容，它在所謂“人員分配問(wèn)題”和“最優(yōu)分配問(wèn)題”等運(yùn)籌學(xué)中的問(wèn)題上有重要的應(yīng)用。首先看實(shí)際中常碰見(jiàn)的問(wèn)題：給n個(gè)工作人員安排m項(xiàng)任務(wù)，n個(gè)人用表示。并不是每個(gè)工作人員均能勝任所有的任務(wù)，一個(gè)人只能勝任其中個(gè)任務(wù)，那么如何安排才能做到最大限度地使每項(xiàng)任務(wù)都有人做，并使盡可能多的人有工作做？例如，現(xiàn)有5個(gè)人，5項(xiàng)工作。已知能勝任

和，能勝任和，能勝任和，能勝任和，能勝任、和。如何安排才能使每個(gè)人都有工作做，且每項(xiàng)工作都有人做？2710.3二部圖及匹配顯然，我們只需構(gòu)造這樣的數(shù)學(xué)模型：以和（i，j=1，2，3，4，5）為頂點(diǎn)，在與其勝任的工作之間連邊，得二部圖G，如圖10.15所示，然后在G中找一個(gè)邊的子集，使得每個(gè)頂點(diǎn)只與一條邊關(guān)聯(lián)（圖中粗線），問(wèn)題便得以解決了。這就是所謂匹配問(wèn)題，下面給出匹配的基本概念和術(shù)語(yǔ)。圖10.15匹配問(wèn)題示意圖2810.3二部圖及匹配定義10.6設(shè)無(wú)向圖G=<V，E，>，（1）如果不包含自圈，并且中的任何兩條邊都不鄰接，則稱為G中的匹配。（2）如果是G中的匹配，并且對(duì)于G中的一切匹配，只要必有

，則稱為G中的極大匹配。（3）G中的邊數(shù)最多的匹配稱為G中的最大匹配。（4）G中的最大匹配包含的邊數(shù)稱為G的匹配數(shù)。顯然，最大匹配一定是極大匹配，而極大匹配不一定是最大匹配。在一個(gè)無(wú)向圖中，可以有多個(gè)極大匹配和最大匹配。2910.3二部圖及匹配例10.7在圖10.16中，{a,c}，{a,c,g}，{a,f}，{b,e}，{b,g}，{b,f,h}，{c,h}，{c,p}，{d,g}，{d,h}，{f,p}是極大匹配，其中{a,c,g}和{b,f,h}是最大匹配。匹配數(shù)是3。圖10.163010.3二部圖及匹配定義10.7設(shè)和是二部圖G的互補(bǔ)結(jié)點(diǎn)子集。如果G的匹配數(shù)等于，則稱G中的最大匹配為到的完美匹配。顯然，只有∣V2∣≥∣V1∣時(shí)可能存在從V1到V2的完美匹配。但這個(gè)條件并不是充分條件。如圖10.16給出的二部圖中，V1＝{a1,a2,a3,a4},V2＝{p1,p2,p3,p4,p5,p6},∣V2∣>∣V1∣，但并不存在V1到V2的完美匹配。下面的定理給出了存在完美匹配的充分必要條件。圖10.16無(wú)向圖中的匹配3110.3二部圖及匹配定理10.10設(shè)

和

是二部圖G的互補(bǔ)結(jié)點(diǎn)子集。存在

到

的完美匹配，當(dāng)且僅當(dāng)對(duì)于任意,，其中當(dāng)二部圖的結(jié)點(diǎn)數(shù)目比較大時(shí)，定理10.10用起來(lái)不太方便，下面給出存在完美匹配的一個(gè)充分條件，判斷二部圖是否存在完美匹配時(shí)，可以先用這個(gè)充分條件，如果得不出結(jié)論，再用定理10.10。3210.3二部圖及匹配定理10.11設(shè)V1和V2是二部圖G的互補(bǔ)結(jié)點(diǎn)子集，t是正整數(shù)。對(duì)于V1中的每個(gè)結(jié)點(diǎn)，在V2中至少有t個(gè)結(jié)點(diǎn)與其鄰接。對(duì)于V2中的每個(gè)結(jié)點(diǎn)，在V1中至多有t個(gè)結(jié)點(diǎn)與其鄰接。則存在V1到V2的完美匹配。33PART01歐拉圖主要內(nèi)容PART02哈密爾頓圖PART03二部圖及匹配PART04平面圖PART05網(wǎng)絡(luò)PART06圖的示例分析10.4平面圖例10.8一個(gè)工廠有3個(gè)車間和3個(gè)倉(cāng)庫(kù)。為了工作需要，車間與倉(cāng)庫(kù)之間將設(shè)專用的車道。為避免發(fā)生車禍，應(yīng)盡量減少車道的交叉點(diǎn)，最好是沒(méi)有交叉點(diǎn)，這是否可能？如圖10.17（a）所示，A，B，C是3個(gè)車間，M，N，P是3座倉(cāng)庫(kù)。經(jīng)過(guò)努力表明，要想建造不相交的道路是不可能的，但可以使交叉點(diǎn)最少（如圖10.17（b）所示）。此類實(shí)際問(wèn)題涉及到平面圖的研究。近年來(lái)，由于大規(guī)模集成電路的發(fā)展，也促進(jìn)了平面圖的研究。本節(jié)介紹平面圖的一些基本概念和常用結(jié)論。圖10.173510.4平面圖定義10.8在一個(gè)平面上，如果能夠畫(huà)出無(wú)向圖G的圖解，其中沒(méi)有任何邊的交叉，則稱圖G是個(gè)平面圖；否則，稱G是非平面圖。直觀上說(shuō)，所謂平面圖就是可以畫(huà)在平面上，使邊除端點(diǎn)外彼此不相交的圖。應(yīng)當(dāng)注意，有些圖從表面上看，它的某些邊是相交的，但是不能就此肯定它不是平面圖。3610.4平面圖例10.9對(duì)于圖10.18（a）（b）中的無(wú)向圖來(lái)說(shuō)，試把該圖解加以重畫(huà)之后，它將不包含任何邊的交叉，如圖10.17（e）（f）所示。因此，由圖10.17（a）（b）給出的圖是平面圖，而（c）（d）不是。圖10.183710.4平面圖設(shè)G={V，E，ψ}是能夠畫(huà)于平面上的圖解中的無(wú)向圖，并且設(shè)C=v1…v2…v3…v4…v1是圖G中的任何基本循環(huán)。此外，設(shè)x＝v1…v3和x

＝v2…v4是圖G中的任意兩條不交叉的基本路徑。在圖10.19中給出了兩種可能的結(jié)構(gòu)。顯然，x和x

或都在基本循環(huán)C的內(nèi)部，或者都在基本循環(huán)C的外部，當(dāng)且僅當(dāng)G是個(gè)非平面圖。因?yàn)檫@時(shí)基本路徑x和x

是相互交叉的。用視察法證明給定圖的非平面性時(shí)，上述的簡(jiǎn)單性質(zhì)甚為有用。圖10.193810.4平面圖例10.10設(shè)有一個(gè)電路，它含有兩個(gè)結(jié)點(diǎn)子集V1和V2，且有|V1|=|V2|=3。用導(dǎo)線把一個(gè)集合中的每一個(gè)結(jié)點(diǎn)，都與另外一個(gè)集合中的每一個(gè)結(jié)點(diǎn)連通，如圖10.20所示。試問(wèn)，是否有可能這樣來(lái)接線，使得導(dǎo)線相互不交叉。對(duì)于印刷電路，避免交叉具有實(shí)際意義。解：這個(gè)問(wèn)題等價(jià)于判定圖10.20中的圖是否是個(gè)平面圖?？梢钥闯?，給定圖中有一個(gè)基本循環(huán)C=v1v6v3v5v2v4v1，如圖10.21所示。39圖10.20圖10.2110.4平面圖試考察三條邊{v1，v5}，{v2，v6}，{v3，v4}，上述每條邊或是處于循環(huán)C的內(nèi)部，或是處于C的外部。顯然，三條邊中至少有兩條邊同時(shí)處于C的同一側(cè)，因此避免不了交叉，如圖10.22所示。故給定的圖是非平面圖。圖10.224010.4平面圖下面就來(lái)闡明庫(kù)拉托夫斯基（Kuratowski，波蘭數(shù)學(xué)家）定理。試考察圖10.23中的兩個(gè)圖。在例10.10中已經(jīng)證明了圖10.20中的圖是個(gè)非平面圖。把圖10.20加以改畫(huà)以后，就能夠得到圖10.23（a）。由此可見(jiàn)，圖10.20同構(gòu)于圖10.23（a），因此圖10.23（a）也是個(gè)非平面圖。另外，采用該例中所使用的方法，也能證明圖10.23（b）也是個(gè)非平面圖。這兩個(gè)非平面圖都稱為庫(kù)拉托夫斯基圖。圖10.234110.4平面圖在圖10.24中，給出了兩個(gè)圖解。如圖10.24（a）所示，試往圖中的一條邊上，插上一個(gè)新的次數(shù)為2的結(jié)點(diǎn)，把一條邊分解成兩條邊，則不會(huì)改變給定圖的平面性。另外，如圖10.24（b）所示，把聯(lián)系于一個(gè)次數(shù)為2的結(jié)點(diǎn)的兩條邊，合并成一條邊，也不會(huì)改變給定圖的平面性。圖10.244210.4平面圖定義10.9設(shè)G1和G2是兩個(gè)無(wú)向圖。如果G1和G2是同構(gòu)的，或者是通過(guò)反復(fù)插入和（或）刪除次數(shù)為2的結(jié)點(diǎn)，能夠把G1和G2轉(zhuǎn)化成同構(gòu)的圖，則稱G1和G2在次數(shù)為2的結(jié)點(diǎn)內(nèi)是同構(gòu)的。例10.11圖10.25中的4個(gè)圖，在次數(shù)為2的結(jié)點(diǎn)內(nèi)是同構(gòu)的。圖10.254310.4平面圖定理10.12設(shè)G是一個(gè)無(wú)向圖。圖G中不存在任何與圖10.23中的兩個(gè)圖同構(gòu)的子圖，當(dāng)且僅當(dāng)圖G是個(gè)平面圖。稱為庫(kù)拉托夫斯基定理。例10.12根據(jù)庫(kù)拉托夫斯基定理證明圖10.26中的（彼得森圖）是非平面圖。圖10.254410.4平面圖定義10.10

多邊形的圖的歸納法定義如下。一個(gè)多邊形是一個(gè)多邊形的圖。設(shè)G=<V，E，ψ>是一個(gè)多邊形的圖，再設(shè)P=viu1u2…ul-1vj是長(zhǎng)度為l≥1的任何基本路徑，它不與圖G中任一路徑交叉，且有vi，vj∈V，但是對(duì)于n=1,2,…，l-1來(lái)說(shuō)，unV。于是，由圖G和P所構(gòu)成的圖G=<V’，E’，ψ’>

也是一個(gè)多邊形的圖，其中V=V∪｛u1，u2，…，ul-1｝E=E∪｛{vi，u1}，{u1，u2}，…，{ul-1，vj}｝多邊形的圖是個(gè)平面圖（或多重邊圖，因?yàn)樵试S長(zhǎng)度為2的循環(huán)存在），它能夠把平面劃分成數(shù)個(gè)區(qū)域，每一個(gè)區(qū)域都是由一個(gè)多邊形定界。4510.4平面圖例10.13圖10.27中的圖是一個(gè)多邊形的圖。圖10.27多邊形的圖4610.4平面圖定義10.11由多邊形的圖定界的每一個(gè)區(qū)域，都稱為圖G的面。例如，圖10.27中的區(qū)域F1，F(xiàn)2，F(xiàn)3等等，都是該多邊形圖的面。定義10.12

包含有多邊形的圖G的所有面的邊界的多邊形，稱為G的極大基本循環(huán)。例如，圖10.27中的循環(huán)v1v2v3v4v5v6v7v1，就是該多邊形的圖的極大基本循環(huán)。應(yīng)該說(shuō)明，給定圖G的極大基本循環(huán)外側(cè)的無(wú)限區(qū)域，是另外一個(gè)面，一般稱為G的無(wú)限面。事實(shí)上，如果把圖G的圖解畫(huà)在球面上，則G的無(wú)限面與其它的有限面并沒(méi)有什么區(qū)別。4710.4平面圖定義10.13如果圖G的兩個(gè)面共有一條邊，則稱這樣的兩個(gè)面是鄰接的面。定理10.13

（歐拉公式）設(shè)G=<V，E，ψ>是個(gè)具有k個(gè)面（包括無(wú)限面在內(nèi)）的(n,m)多邊形的圖。則n

m+k=2。4810.4平面圖例10.14在圖10.28中，給出了一個(gè)多邊形的圖(實(shí)線畫(huà)出的)和它的對(duì)偶(虛線畫(huà)出的)，就說(shuō)明了上述方法。由上述的構(gòu)成方法不難看出，每一個(gè)多邊形的圖G，其對(duì)偶圖也必定是一個(gè)多邊形的圖，而且G和G*是互為對(duì)偶的。49圖10.28對(duì)偶圖10.4平面圖定義10.14如果多邊形的圖G的對(duì)偶G*同構(gòu)于G，則稱G是自對(duì)偶圖。例10.15在圖10.29中，給出了一個(gè)自對(duì)偶圖。50圖10.29自偶圖10.4平面圖定理10.14若平面圖是自對(duì)偶圖，且有n個(gè)結(jié)點(diǎn)，m條邊，則定義10.15平面圖的正常著色(簡(jiǎn)稱著色，是指對(duì)的每個(gè)結(jié)點(diǎn)指派一種顏色，使得相鄰結(jié)點(diǎn)都有不同的顏色)。若可用n種顏色對(duì)圖G著色，則稱G是n

—可著色的。對(duì)圖G著色時(shí)，需要的最少顏色數(shù)稱為G的著色數(shù)，記為5110.4平面圖定理10.15（四色定理）任何簡(jiǎn)單平面圖都是4—可著色的。定理10.16（五色定理）任何簡(jiǎn)單平面圖，均有52PART01歐拉圖主要內(nèi)容PART02哈密爾頓圖PART03二部圖及匹配PART04平面圖PART05網(wǎng)絡(luò)PART06圖的示例分析10.5網(wǎng)絡(luò)定義10.16一個(gè)網(wǎng)絡(luò)N=(V,

A)是指一個(gè)連通無(wú)環(huán)且滿足下列條件的有向圖。（1）有一個(gè)頂點(diǎn)子集X，其每個(gè)頂點(diǎn)的入度都是0。（2）有一個(gè)與X不相交的頂點(diǎn)子集Y，其每個(gè)頂點(diǎn)的出度都為0。（3）每條弧都有一個(gè)非負(fù)的權(quán)值，稱為弧的容量。上述網(wǎng)絡(luò)N可以記作N=(V,X,Y,A,C)，其中，X稱為網(wǎng)絡(luò)的源點(diǎn)集，Y稱為網(wǎng)絡(luò)的匯點(diǎn)集，V和A分別為頂點(diǎn)集和弧集，網(wǎng)絡(luò)中的除源點(diǎn)和匯點(diǎn)之外的頂點(diǎn)稱為中轉(zhuǎn)點(diǎn)。源點(diǎn)和匯點(diǎn)在實(shí)際網(wǎng)絡(luò)中對(duì)應(yīng)于網(wǎng)絡(luò)的入口和出口，或者說(shuō)計(jì)算機(jī)網(wǎng)絡(luò)的源結(jié)點(diǎn)和目的結(jié)點(diǎn)。5410.5網(wǎng)絡(luò)C為網(wǎng)絡(luò)的容量函數(shù)，容量函數(shù)是定義在弧集A上的非負(fù)函數(shù)。在實(shí)際網(wǎng)絡(luò)中，它對(duì)應(yīng)于相應(yīng)路線上的通行能力，如公路的寬度、計(jì)算機(jī)網(wǎng)絡(luò)的帶寬等。例如，在圖10.33所示的網(wǎng)絡(luò)中，{x1,x2}是源點(diǎn)集，{y1,y2}是匯點(diǎn)集。其他結(jié)點(diǎn)是中轉(zhuǎn)結(jié)點(diǎn)，弧上的數(shù)字表示弧的容量。圖10.33網(wǎng)絡(luò)示例5510.5網(wǎng)絡(luò)如果一個(gè)網(wǎng)絡(luò)中的源點(diǎn)集和匯點(diǎn)集都只包含一個(gè)頂點(diǎn)，我們稱該網(wǎng)絡(luò)為單源單匯網(wǎng)絡(luò)。事實(shí)上，對(duì)于任意網(wǎng)絡(luò)N=(V,X,Y,A,C)，在經(jīng)過(guò)一定的處理后，都可以轉(zhuǎn)變?yōu)橐粋€(gè)單源單匯網(wǎng)絡(luò)。處理的方法為：（1）給網(wǎng)絡(luò)N添加兩個(gè)新的頂點(diǎn)s和t。（2）對(duì)任意xX，從s向x添加一條弧，其容量為（或

）。（3）對(duì)任意yY，從y向t添加一條弧，其容量為（或

）。其中，N+(x)表示頂點(diǎn)x的出鄰點(diǎn)集合{u|(x,u)A}，N-(y)表示頂點(diǎn)y的入鄰點(diǎn)集合{u|(u,y)A}。新添加的頂點(diǎn)s和t分別稱為人工源和人工匯。5610.5網(wǎng)絡(luò)簡(jiǎn)單地說(shuō)，只需要在原有非單源單匯網(wǎng)絡(luò)中添加一個(gè)新的源點(diǎn)和一個(gè)新的匯點(diǎn)，并且添加從新的源點(diǎn)指向原有源點(diǎn)的弧，再添加從原有匯點(diǎn)指向新的匯點(diǎn)的弧，就能得到一個(gè)單源單匯網(wǎng)絡(luò)。圖10.34單源單匯網(wǎng)絡(luò)對(duì)圖10.33所示的網(wǎng)絡(luò)添加人工源和人工匯后，將變?yōu)閳D10.34所示的單源單匯網(wǎng)絡(luò)。單源單匯網(wǎng)絡(luò)是一種特殊的網(wǎng)絡(luò)，它在各種網(wǎng)絡(luò)問(wèn)題的求解方面比非單源單匯網(wǎng)絡(luò)更為簡(jiǎn)單。由于任意網(wǎng)絡(luò)都可以轉(zhuǎn)化為單源單匯網(wǎng)絡(luò)，后續(xù)章節(jié)中對(duì)網(wǎng)絡(luò)流的討論都可以只考慮單源單匯網(wǎng)絡(luò)。5710.5網(wǎng)絡(luò)在一些實(shí)際應(yīng)用中，需要考慮弧和頂點(diǎn)都有容量限制的網(wǎng)絡(luò)。例如，在某些網(wǎng)絡(luò)中，需要考慮結(jié)點(diǎn)的緩存大小，此時(shí)結(jié)點(diǎn)的轉(zhuǎn)發(fā)能力會(huì)受到限制。結(jié)點(diǎn)能力的限制并不能直接在圖上體現(xiàn)出來(lái)，對(duì)于這樣的情況，可以做一個(gè)轉(zhuǎn)換，其方法為：將中轉(zhuǎn)能力受限的結(jié)點(diǎn)分裂為兩個(gè)結(jié)點(diǎn)，并且在這兩個(gè)結(jié)點(diǎn)之間加入一條弧，這樣就可以利用這條新加入的弧來(lái)表示結(jié)點(diǎn)的轉(zhuǎn)發(fā)能力受限。經(jīng)過(guò)轉(zhuǎn)化為單源單匯網(wǎng)絡(luò)并將結(jié)點(diǎn)能力的受限轉(zhuǎn)化為弧的受限后，實(shí)際網(wǎng)絡(luò)問(wèn)題可以轉(zhuǎn)化為圖論中的網(wǎng)絡(luò)問(wèn)題。5810.5網(wǎng)絡(luò)定義10.17

可行流為：網(wǎng)絡(luò)N=(V,X,Y,A,C)中的一個(gè)可行流是指定義在A上的一個(gè)整值函數(shù)f，使得：（1）對(duì)任意aA，0≤f(a)≤c(a),（容量約束）；（2）對(duì)任意vV-(X∪Y)，f-(v)=f+(v)，（流量守恒）。其中，f-(v)表示點(diǎn)v處入弧上的流量之和，即流入v的流量之和，f+(v)表示點(diǎn)v處出弧上的流量之和，即從v流出的流量之和。59網(wǎng)絡(luò)流10.5網(wǎng)絡(luò)也就是說(shuō)，可行流滿足兩個(gè)條件：一是容量約束，即可行流在某一弧上的流量小于該弧的容量；二是流量守恒，即流入某一中轉(zhuǎn)點(diǎn)的流量等于流出該點(diǎn)的流量。需要強(qiáng)調(diào)的是，可行流總是存在的，如果f(a)=0，這個(gè)流稱為零值流。對(duì)于網(wǎng)絡(luò)N中任意可行流f和任意頂點(diǎn)子集S，從S中流出的流量記為f+(S)，它表示從S中頂點(diǎn)指向S外頂點(diǎn)的弧上的流量之和；流入S的流量記為f-(S)，表示從S外頂點(diǎn)指向S中頂點(diǎn)的弧上流量之和。60網(wǎng)絡(luò)流10.5網(wǎng)絡(luò)定義10.18設(shè)f是網(wǎng)絡(luò)N=(V,X,Y,A,C)中的一個(gè)可行流，則必有f+(X)=f-(Y)。f+(X)（或f-(Y)）稱為流f的流量，記為Valf。流是網(wǎng)絡(luò)中的重要概念，在實(shí)際網(wǎng)絡(luò)問(wèn)題中，經(jīng)常需要求解與流相關(guān)的問(wèn)題，例如網(wǎng)絡(luò)的最大流等。所謂最大流，是指網(wǎng)絡(luò)N中流量最大的可行流。網(wǎng)絡(luò)的最大流對(duì)于實(shí)際應(yīng)用具有重要意義，例如，公路網(wǎng)絡(luò)中獲得最大的運(yùn)輸量、計(jì)算機(jī)網(wǎng)絡(luò)中獲得最大的轉(zhuǎn)發(fā)增益等等。為了得到網(wǎng)絡(luò)的最大流，L.R.Ford和D.R.Fulkerson在1956年提出了著名的最大流最小割定理，巧妙地將流與割對(duì)應(yīng)起來(lái)，將最大流問(wèn)題轉(zhuǎn)化為最小割問(wèn)題。61流量10.5網(wǎng)絡(luò)定義10.19設(shè)N=(V,x,y,A,C)是一個(gè)單源單匯網(wǎng)絡(luò)。假設(shè)網(wǎng)絡(luò)中的某些頂點(diǎn)組成集合S，S?V，=V-S。我們用(S,)表示尾在S中而頭在中的所有弧的集合（即從S中的頂點(diǎn)指向S之外頂點(diǎn)的所有弧的集合）。如果

，而，則稱弧集(S,)為網(wǎng)絡(luò)N的一個(gè)割。一個(gè)割(S,)的容量是指(S,)中各條弧的容量之和，記為Cap(S,)。6210.5網(wǎng)絡(luò)定義10.19設(shè)N=(V,x,y,A,C)是一個(gè)單源單匯網(wǎng)絡(luò)。假設(shè)網(wǎng)絡(luò)中的某些頂點(diǎn)組成集合S，S?V，=V-S。我們用(S,)表示尾在S中而頭在中的所有弧的集合（即從S中的頂點(diǎn)指向S之外頂點(diǎn)的所有弧的集合）。如果

，而，則稱弧集(S,)為網(wǎng)絡(luò)N的一個(gè)割。一個(gè)割(S,)的容量是指(S,)中各條弧的容量之和，記為Cap(S,)。6310.5網(wǎng)絡(luò)例如，在圖10.24中所示的單源單匯網(wǎng)絡(luò)N中，令S={s,x1,x2,v2}，則割(S,)={x1v1,x2v1,v2y1,v2y2}，割的容量Cap(S,)=11。對(duì)網(wǎng)絡(luò)N中的任意流f和任意割(S,)，流f的流量等于流出S的流量與流入S的流量之差，即Valf=f+(S)-f-(S)。網(wǎng)絡(luò)N可能存在多個(gè)割，各個(gè)割的容量并不一定相等，其中容量最小的一個(gè)割稱為網(wǎng)絡(luò)N的最小割。即：如果網(wǎng)絡(luò)N不存在割使得

，則割K稱為網(wǎng)絡(luò)N的最小割。6410.5網(wǎng)絡(luò)定理10.17最大流最小割定理的基本內(nèi)容為：任一網(wǎng)絡(luò)N=(V,X,Y,A,C)中，最大流的流量等于最小割的容量。實(shí)際上，割就是一個(gè)弧的集合，如果去掉這些弧，就可以把網(wǎng)絡(luò)“分割”成分別包含了源點(diǎn)和匯點(diǎn)的兩部分。由于從源點(diǎn)到匯點(diǎn)必須要經(jīng)過(guò)這些弧，因此，如果能求出最小的割集，就能得到最大流。最大流最小割定理對(duì)于求解最大流具有非常重要的指導(dǎo)意義，關(guān)于怎樣求解網(wǎng)絡(luò)的最大流，我們將在下一節(jié)介紹。6510.5網(wǎng)絡(luò)定義10.20設(shè)P=uv1…ukv是網(wǎng)絡(luò)N=(V,x,y,A,C)中一條u-v路，若弧<vi,vi+1>A，則稱此弧為u-v路P的一條正向?。ɑ蚍Q前向弧、順向?。艋?lt;vi+1,vi>A，則稱此弧為u-v路P的一條反向弧（或稱后向弧、逆向?。?。將u-v路P所經(jīng)過(guò)的弧（無(wú)論正向弧還是反向?。┓Q為路P上的弧。66在圖10.35中的網(wǎng)絡(luò)N中，x-y路P=xv1v3v4y上，所有弧都是正向?。欢趚-y路Q=xv2v4v3y上，弧<x,v2>和<v3,y>是正向弧，而<v4,v2>和<v3,v4>是反向弧?？梢钥闯?，對(duì)于同一條弧<v3,v4>，在路P中為正向弧，而在路Q中為反向弧?？梢?jiàn)，一條弧是正向弧還是反向弧與路的選擇有關(guān)。10.5網(wǎng)絡(luò)定義10.21假設(shè)f是網(wǎng)絡(luò)N=(V,X,Y,A,C)中的一個(gè)可行流，u是N中任意一點(diǎn)，P是網(wǎng)絡(luò)N中的一條x-u路，如果對(duì)路P上的任一條弧a，都有：（1）若弧a是P的正向弧，則c(a)-f(a)>0；（2）若弧a是P的反向弧，則f(a)>0。則稱P是N的一條f可增x-u路。特別的，N中的一條f可增x-y路可簡(jiǎn)稱為N的一條f可增路。對(duì)于N中任意一條f可增路P和P上任意一條弧a，假設(shè)沿路P可增加的流量為，這一值稱為f可增路P上流的增量（可增量）。6710.5網(wǎng)絡(luò)68圖10.36網(wǎng)絡(luò)的課可增路可增量在求解網(wǎng)絡(luò)的最大流問(wèn)題時(shí)非常重要，求解網(wǎng)絡(luò)最大流問(wèn)題的幾種常用算法都是基于可增量方法的。下面，我們介紹最大流問(wèn)題求解的兩種經(jīng)典算法：標(biāo)號(hào)算法和Dinic算法。10.5網(wǎng)絡(luò)標(biāo)號(hào)算法就是由可增路的概念得到的。其基本原理為：對(duì)于一個(gè)網(wǎng)絡(luò)N中的一個(gè)可行流f，如果能找到N中的一條f可增x-y路P，則可沿著P修改流的值，得到一個(gè)流量更大的可行流f

’。修改后流的流量為Valf

’=Valf+Δf(P)。如果反復(fù)找N中的可增路，沿著可增路將流量擴(kuò)大，直到找不出可增路為止，就可以達(dá)到最大流。那么，怎樣判斷可行流f的可增路是否存在呢？或者說(shuō)怎樣找f的可增路？69標(biāo)號(hào)算法10.5網(wǎng)絡(luò)解決這一問(wèn)題需要使用Ford-Fulkerson標(biāo)號(hào)法，標(biāo)號(hào)過(guò)程如下。設(shè)網(wǎng)絡(luò)N=(V,x,y,A,C)中當(dāng)前可行流為f。從源點(diǎn)x開(kāi)始，首先給x標(biāo)上∞，即l(x)=∞（x稱為已標(biāo)未查頂點(diǎn)，其它頂點(diǎn)稱為未標(biāo)未查頂點(diǎn)）。任選一已標(biāo)未查頂點(diǎn)u，檢查其所有尚未標(biāo)號(hào)的鄰點(diǎn)：（1）對(duì)u的尚未標(biāo)號(hào)的出鄰點(diǎn)v（即<u,v>A），若c(u,v)>f(u,v)，則給v標(biāo)號(hào)：，（v稱為已標(biāo)未查頂點(diǎn)）否則，不給v標(biāo)號(hào)。（2）對(duì)u的尚未標(biāo)號(hào)的入鄰點(diǎn)v（即<v,u>A），若f(u,v)>0，則給v標(biāo)號(hào)：，（v稱為已標(biāo)未查頂點(diǎn)）否則，不給v標(biāo)號(hào)。70標(biāo)號(hào)算法10.5網(wǎng)絡(luò)當(dāng)檢查完u的所有鄰點(diǎn)之后，u稱為已標(biāo)已查頂點(diǎn)。反復(fù)進(jìn)行上述操作，最終結(jié)果有兩種情況：（1）匯點(diǎn)y獲得標(biāo)號(hào)，此時(shí)已經(jīng)得到了f的可增流（2）y點(diǎn)沒(méi)有獲得標(biāo)號(hào)，并且已經(jīng)沒(méi)有已標(biāo)未查頂點(diǎn)。此時(shí)當(dāng)前的流f就是最大流。圖10.38（下頁(yè)）演示了網(wǎng)絡(luò)N從零值流開(kāi)始，利用標(biāo)號(hào)算法求最大流的過(guò)程。在每條弧上，括號(hào)外的數(shù)字表示當(dāng)前流值，括號(hào)里的數(shù)字表示弧的容量。在每個(gè)頂點(diǎn)旁邊有一組三元標(biāo)號(hào)。在這個(gè)三元標(biāo)號(hào)中，第一個(gè)元素表示該點(diǎn)的標(biāo)號(hào)值是通過(guò)哪個(gè)點(diǎn)獲得的，它用于反向追蹤可增路；第二個(gè)元素的正或者負(fù)表示標(biāo)號(hào)的前一個(gè)點(diǎn)是通過(guò)正向弧還是反向弧連接到當(dāng)前點(diǎn)的，它用于標(biāo)識(shí)在增流時(shí)應(yīng)該在弧上增加流值還是減小流值；第三個(gè)元素為該頂點(diǎn)的標(biāo)號(hào)數(shù)值，表示從源點(diǎn)x到該點(diǎn)通過(guò)當(dāng)前找到的可增路可以增加的流值。71標(biāo)號(hào)算法10.5網(wǎng)絡(luò)72標(biāo)號(hào)算法圖10.38標(biāo)號(hào)算法示例10.5網(wǎng)絡(luò)在圖10.38（a）中，網(wǎng)絡(luò)中的流是零值流。標(biāo)號(hào)結(jié)束后，匯點(diǎn)y獲得的標(biāo)號(hào)為(v4,+,7)。標(biāo)號(hào)的第一項(xiàng)為當(dāng)前點(diǎn)的前一個(gè)點(diǎn)，根據(jù)這一點(diǎn)我們可以反向追蹤得到可增路xv2v4y；標(biāo)號(hào)的第三項(xiàng)表示可以增加的流值，也就是說(shuō)可以增加7個(gè)單位的流量。據(jù)此，我們可以對(duì)網(wǎng)絡(luò)進(jìn)行增流，得到圖10.38（b）。在圖10.8（b）中，標(biāo)號(hào)結(jié)束后y獲得的標(biāo)號(hào)為(v3,+,5)。根據(jù)標(biāo)號(hào)的第一項(xiàng)可以反向追蹤得到可增路xv1v3y，這條可增路能增加的流值為5。增流后可以得到圖10.38（c）。同樣，我們可以從圖10.38（c）再次增流，得到圖10.38（d），此時(shí)，已經(jīng)沒(méi)有已標(biāo)未查點(diǎn)了，而匯點(diǎn)y還沒(méi)有獲得標(biāo)號(hào)，因此，當(dāng)前網(wǎng)絡(luò)流已經(jīng)是最大流了。73標(biāo)號(hào)算法10.5網(wǎng)絡(luò)在標(biāo)號(hào)算法中，有可能出現(xiàn)每次只能增加一個(gè)單位流量的情況，這時(shí)，如果弧的容量為m，需要2m次增流才能達(dá)到最大流?？梢?jiàn)，標(biāo)號(hào)算法的計(jì)算量不完全依賴于問(wèn)題的規(guī)模（頂點(diǎn)數(shù)和弧數(shù)），還依賴于弧的容量。我們把計(jì)算量雖然是問(wèn)題規(guī)模的多項(xiàng)式，但是還依賴于其它參量的算法稱為偽多項(xiàng)式算法。Ford-Fulkerson標(biāo)號(hào)算法就是一種偽多項(xiàng)式算法。標(biāo)號(hào)算法不是一個(gè)多項(xiàng)式算法，其復(fù)雜度還依賴于弧的容量，因此，我們需要復(fù)雜度更低的算法。Dinic算法就是一種改進(jìn)的算法。74標(biāo)號(hào)算法10.5網(wǎng)絡(luò)定義10.22對(duì)于網(wǎng)絡(luò)N=(V,x,y,A,C)和N上的一個(gè)可行流f，構(gòu)造一個(gè)新的網(wǎng)絡(luò)N(f)=(V,x,y,A(f),C’)，其中A(f)及容量函數(shù)C′

定義如下：（1）若<u,v>A并且f(u,v)<c(u,v)，則<u,v>A(f

)，并且c′

(u,v)=c(u,v)-f(u,v)。（2）若<u,v>A并且f(u,v)>0，則<v,u>A(f

)，并且c′

(u,v)=f(u,v)。這樣構(gòu)造的網(wǎng)絡(luò)N(f

)稱為網(wǎng)絡(luò)N關(guān)于流f的增量網(wǎng)絡(luò)。簡(jiǎn)單的說(shuō)，對(duì)應(yīng)于N中一條非飽和流，N(f

)中有一條正向弧，其容量值為N中弧的容量與流量之差；對(duì)應(yīng)于N中一條非零流弧，N(f

)中有一條反向弧，其容量值為N中弧的流量。75Dinic算法10.5網(wǎng)絡(luò)圖10.39顯示了一個(gè)網(wǎng)絡(luò)和它的增量網(wǎng)絡(luò)。在圖10.39（a）中的網(wǎng)絡(luò)N中，有一條飽和弧<x,v1>，因此，在對(duì)應(yīng)的增量網(wǎng)絡(luò)圖10.39（b）中，只有一條與之方向相反的弧<v1,x>與之對(duì)應(yīng)；在網(wǎng)絡(luò)N中，有2條零流弧<v1,v2>和<v3,v2>，因此在增量網(wǎng)絡(luò)中也有與它們對(duì)應(yīng)的弧<v1,v2>和<v3,v2>；而對(duì)于網(wǎng)絡(luò)N中的非零流非飽和弧，增量網(wǎng)絡(luò)中將有正反兩條弧與之對(duì)應(yīng)。增量網(wǎng)絡(luò)N(f

)中每條弧的容量恰好是N中對(duì)應(yīng)弧的流可增量。圖10.3976Dinic算法10.5網(wǎng)絡(luò)在增量網(wǎng)絡(luò)N(f

)中，我們把從x到y(tǒng)的有向路稱為增量網(wǎng)絡(luò)N(f

)的x-y有向路。N(f

)的x-y有向路是與網(wǎng)絡(luò)N中的x-y路對(duì)應(yīng)的，它是N的f可增路。因此，我們可以用在增量網(wǎng)絡(luò)N(

f

)中找x-y有向路的方法來(lái)尋找網(wǎng)絡(luò)N的f可增路。這一轉(zhuǎn)換關(guān)系正是Dinic算法的依據(jù)。

為了更快地得到最大流，我們需要對(duì)增量網(wǎng)絡(luò)進(jìn)行分層并且得到輔助網(wǎng)絡(luò)。77Dinic算法10.5網(wǎng)絡(luò)定義10.23在網(wǎng)絡(luò)N=(V,x,y,A,C)中，令：Vi={vV|N中x到v的最短有向路的長(zhǎng)度為i}。假設(shè)x到y(tǒng)的最短有向路的長(zhǎng)度為n，則：（1）xV，yVn。（2）Vi∩Vj=Φ，(j≠i)。Vi中的頂點(diǎn)稱為網(wǎng)絡(luò)N的第i層頂點(diǎn)。上述有向路的長(zhǎng)度是指路上有向邊的數(shù)目，而兩點(diǎn)間最短有向路指兩點(diǎn)間有向邊最少的有向路。按照上述分層原則，我們可以對(duì)圖10.40中的網(wǎng)絡(luò)N進(jìn)行分層。V0={x},V1={v1,v2},V2={y,v3,v4}78Dinic算法10.5網(wǎng)絡(luò)分層后的網(wǎng)絡(luò)如圖10.41所示。很容易看出，網(wǎng)絡(luò)頂點(diǎn)分層后，弧有三種可能性：從第i層頂點(diǎn)指向第i+1層頂點(diǎn)；從第i層頂點(diǎn)指向第i層頂點(diǎn)；從第i層頂點(diǎn)指向第j層頂點(diǎn)(j<i)。根據(jù)層的定義，不可能出現(xiàn)第i層頂點(diǎn)指向第i+k(k≥2)的情況。79Dinic算法圖10.40待分層的網(wǎng)絡(luò)N圖10.41網(wǎng)絡(luò)N的分層10.5網(wǎng)絡(luò)對(duì)分層后的網(wǎng)絡(luò)進(jìn)行進(jìn)一步的操作就可以得到輔助網(wǎng)絡(luò)。輔助網(wǎng)絡(luò)是在增量網(wǎng)絡(luò)和網(wǎng)絡(luò)分層的基礎(chǔ)上得到的。其定義為：對(duì)于網(wǎng)絡(luò)N=(V,x,y,A,C)，假設(shè)N(f

)是N的關(guān)于流f的增量網(wǎng)絡(luò)。對(duì)N(f

)的頂點(diǎn)按照最短有向路進(jìn)行分層后，刪除層數(shù)不低于y的頂點(diǎn)（即比y層數(shù)高的頂點(diǎn)和與y同層的頂點(diǎn)），再刪除從高層指向低層的弧和同層頂點(diǎn)之間的弧，得到的N(f

)的子網(wǎng)絡(luò)稱為N的關(guān)于流f的輔助網(wǎng)絡(luò)，記為AN(f

)。此時(shí)所剩下的各條弧上的容量與N(f

)相同。80輔助網(wǎng)絡(luò)10.5網(wǎng)絡(luò)圖10.42演示了從網(wǎng)絡(luò)N到增量網(wǎng)絡(luò)N(f

)，再對(duì)增量網(wǎng)絡(luò)N(f

)進(jìn)行分層并得到輔助網(wǎng)絡(luò)的過(guò)程。81輔助網(wǎng)絡(luò)圖10.42網(wǎng)絡(luò)N的增量網(wǎng)絡(luò)、分層和輔助網(wǎng)絡(luò)示例10.5網(wǎng)絡(luò)有了前面介紹的增量網(wǎng)絡(luò)、網(wǎng)絡(luò)分層和輔助網(wǎng)絡(luò)的概念之后，可以利用分層后的輔助網(wǎng)絡(luò)求最大流，這一算法是Dinic提出的，我們稱之為Dinic算法。Dinic算法可以從網(wǎng)絡(luò)N=(V,x,y,A,C)的任意可行流f開(kāi)始，執(zhí)行如下過(guò)程：（1）構(gòu)造增量網(wǎng)絡(luò)N(f

)（2）對(duì)N(f

)分層并構(gòu)造輔助網(wǎng)絡(luò)AN(f

)（3）求AN(f

)中的一條x-y有向路P，它就是N中的一條f可增路；（4）在N中沿著P增流得到更大的流，并去掉因增流在AN(f

)中所導(dǎo)致的飽和弧。如果此時(shí)AN(f

)中仍然有x-y有向路，則再沿著新的x-y有向路在N中增流，直到N(f

)剩余網(wǎng)絡(luò)中沒(méi)有x-y有向路為止；（5）反復(fù)執(zhí)行（1）—（4），直到新流f的增量網(wǎng)絡(luò)N(f

)不能分層到達(dá)y位置。完成上述步驟后，網(wǎng)絡(luò)N不再有f可增路，因此得到的是最大流。82Dinic網(wǎng)絡(luò)10.5網(wǎng)絡(luò)我們同樣以圖10.38中的網(wǎng)絡(luò)為例來(lái)演示Dinic算法，從而比較標(biāo)號(hào)算法和Dinic算法的聯(lián)系和區(qū)別。Dinic算法的演示過(guò)程如圖10.43所示。83Dinic網(wǎng)絡(luò)10.5網(wǎng)絡(luò)可以看出，執(zhí)行的過(guò)程與標(biāo)號(hào)算法類似，但是在求可增流的過(guò)程中，Dinic算法借助增量網(wǎng)絡(luò)和輔助網(wǎng)絡(luò)更直觀的得到可增流，為了演示標(biāo)號(hào)算法和Dinic算法的聯(lián)系，每次增流都只進(jìn)行了一次，實(shí)際上，前兩次增流可以一次完成。在簡(jiǎn)單的網(wǎng)絡(luò)中，兩者差別不大，但是在復(fù)雜的網(wǎng)絡(luò)中，Dinic算法在復(fù)雜度上有一定的優(yōu)勢(shì)。下面我們來(lái)看Dinic算法的復(fù)雜度。在Dinic算法中，找路循環(huán)最多能進(jìn)行e次，而在分層輔助網(wǎng)絡(luò)中找一條x-y有向路的計(jì)算量為O(v)，因此，算法的總計(jì)算復(fù)雜度為O((v-1)(e+ev))=O(v2e)。其中，e為弧的數(shù)量、v為頂點(diǎn)的數(shù)量。在每次可增加的量較小時(shí)，Dinic算法的復(fù)雜度要明顯低于標(biāo)號(hào)算法。84Dinic網(wǎng)絡(luò)10.5網(wǎng)絡(luò)定義10.24

設(shè)a,b是開(kāi)關(guān)網(wǎng)絡(luò)GN上兩個(gè)結(jié)點(diǎn)，而

是a，b兩點(diǎn)間的道路，其中

若

道路上各邊的權(quán)的連乘積為

，并令則稱fab為開(kāi)關(guān)網(wǎng)絡(luò)GN關(guān)于結(jié)點(diǎn)a，b的開(kāi)關(guān)函數(shù)。85開(kāi)關(guān)網(wǎng)絡(luò)10.5網(wǎng)絡(luò)定義10.25對(duì)于開(kāi)關(guān)網(wǎng)絡(luò)有矩陣其中則稱矩陣為開(kāi)關(guān)網(wǎng)絡(luò)的傳輸矩陣。86開(kāi)關(guān)網(wǎng)絡(luò)10.5網(wǎng)絡(luò)而對(duì)矩陣，其中則稱矩陣為開(kāi)關(guān)網(wǎng)絡(luò)的連接矩陣。如果說(shuō)連接矩陣A類似于鄰接矩陣，而傳輸矩陣頗與路徑矩陣相當(dāng)，不難得到如下關(guān)系式這里是矩陣A的n-1次冪，不過(guò)乘是邏輯乘，和是邏輯和，并服從邏輯運(yùn)算法則。87開(kāi)關(guān)網(wǎng)絡(luò)10.5網(wǎng)絡(luò)例10.17簡(jiǎn)單接觸網(wǎng)絡(luò)如圖10.46所示。這里

就是結(jié)點(diǎn)

間“不超過(guò)兩步”走到的道路的開(kāi)關(guān)函數(shù)88圖10.4610.5網(wǎng)絡(luò)例10.178910.5網(wǎng)絡(luò)定理10.18若是開(kāi)關(guān)網(wǎng)絡(luò)的兩個(gè)結(jié)點(diǎn)，，則對(duì)于中不含

邊的回路，必有間的道路，，使，即回路為道路與的對(duì)稱差。9010.5網(wǎng)絡(luò)例10.18設(shè)第一步：引進(jìn)邊，并從回路矩陣出發(fā)，通過(guò)一系列初等變換，目的要得出基本回路矩陣，步驟如下：從基本回路矩陣可知，圖有m=9，余數(shù)變數(shù)=4，樹(shù)的邊數(shù)=5，n=6。第二步：從基本回路矩陣9110.5網(wǎng)絡(luò)與基本割集矩陣的關(guān)系可得矩陣如下：對(duì)矩陣進(jìn)行下列一系列初等變換，便能得到一個(gè)每列至多有兩個(gè)元素1的矩陣。9210.5網(wǎng)絡(luò)第三步：對(duì)上面所的矩陣增加最后一行，使得每列有兩個(gè)元素1，于是得關(guān)聯(lián)矩陣。根據(jù)基本道路矩陣與關(guān)聯(lián)矩陣，可得開(kāi)關(guān)網(wǎng)絡(luò)圖（去掉邊）如圖10.50所示。93圖10.50PART01歐拉圖主要內(nèi)容PART02哈密爾頓圖PART03二部圖及匹配PART04平面圖PART05網(wǎng)絡(luò)PART06圖的示例分析10.6圖的實(shí)例分析1962年我國(guó)的管梅谷首先提出并研究了如下的問(wèn)題：郵遞員從郵局出發(fā)經(jīng)過(guò)他投遞的每一條街道，然后返回郵局，郵遞員希望找出一條行走距離最短的路線。這個(gè)問(wèn)題被外國(guó)人稱為中國(guó)郵遞員問(wèn)題（ChinesePostmanProblem）。我們把郵遞員的投遞區(qū)域看作一個(gè)連通的帶權(quán)無(wú)向圖G，其中G的頂點(diǎn)看作街道的交叉口和端點(diǎn)，街道看作邊，權(quán)看作街道的長(zhǎng)度，解決中國(guó)郵遞員問(wèn)題，就是在連通帶權(quán)無(wú)向圖中，尋找經(jīng)過(guò)每邊至少一次且權(quán)和最小的回路。如果對(duì)應(yīng)的圖G是歐拉圖，那么從對(duì)應(yīng)于郵局的頂點(diǎn)出發(fā)的任何一條歐拉回路都是符合上述要求的郵遞員的最優(yōu)投遞路線。95中國(guó)郵遞員問(wèn)題10.6圖的實(shí)例分析如果圖G只有兩個(gè)奇點(diǎn)x和y，則存在一條以x和y為端點(diǎn)的歐拉鏈，因此，由這條歐拉Euler鏈加x到y(tǒng)最短路即是所求的最優(yōu)投遞路線。如果連通圖G不是歐拉圖也不是半歐拉Euler圖，由于圖G有偶數(shù)個(gè)奇點(diǎn)，對(duì)于任兩個(gè)奇點(diǎn)x和y，在G中必有一條路連接它們。將這條路上的每條邊改為二重邊得到新圖H1，則x和y就變?yōu)镠1的偶點(diǎn)，在這條路上的其他頂點(diǎn)的度數(shù)均增加2，即奇偶數(shù)不變，于是H1的奇點(diǎn)個(gè)數(shù)比G的奇點(diǎn)個(gè)數(shù)少2。對(duì)H1重復(fù)上述過(guò)程得H2，再對(duì)H2重復(fù)上述過(guò)程得H3，…，經(jīng)若干次后，可將G中所有頂點(diǎn)變成偶點(diǎn)，從而得到多重歐拉圖（在中，若某兩點(diǎn)u和v之間連接的邊數(shù)多于2，則可去掉其中的偶數(shù)條多重邊，最后剩下連接u與v的邊僅有1或2條邊，這樣得到的圖仍是歐拉圖）。這個(gè)歐拉歐拉圖的一條歐拉回路就相應(yīng)于中國(guó)郵遞員問(wèn)題的一個(gè)可行解，且歐拉回路的長(zhǎng)度等于G的所有邊的長(zhǎng)度加上由G到所添加的邊的長(zhǎng)度之和。但怎樣才能使這樣的歐拉回路的長(zhǎng)度最短呢？如此得到的圖中最短的歐拉Euler回路稱為圖G的最優(yōu)環(huán)游。96中國(guó)郵遞員問(wèn)題10.6圖的實(shí)例分析定理10.19設(shè)P是加權(quán)連通圖G中一條包含G的所有邊至少一次的閉鏈，則P最優(yōu)（即具有最小長(zhǎng)度）的充要條件是：（1）P中沒(méi)有二重以上的邊。（2）在G的每個(gè)圈C中，重復(fù)邊集E的長(zhǎng)度之和不超過(guò)這個(gè)圈的長(zhǎng)度的一半，即97中國(guó)郵遞員問(wèn)題10.6圖的實(shí)例分析根據(jù)上面的討論及定理10.19，我們可以設(shè)計(jì)出求非歐拉帶權(quán)非歐拉連通圖G的最優(yōu)環(huán)游的算法。此算法稱為最優(yōu)環(huán)游的奇偶點(diǎn)圖上作業(yè)法。（1）把G中所有奇點(diǎn)配成對(duì)，將每對(duì)奇點(diǎn)之間的一條路上的每邊改為二重邊，得到一個(gè)新圖G1，新圖G1中沒(méi)有奇點(diǎn)，即G1為多重歐拉圖。（2）若G1中每一對(duì)頂點(diǎn)之間有多于2條邊連接，則去掉其中的偶數(shù)條邊，留下1條或2條邊連接這兩個(gè)頂點(diǎn)。直到每一對(duì)相鄰頂點(diǎn)至多由2條邊連接，得到圖G2。（3）檢查G2的每一個(gè)圈C，若某一個(gè)圈C上重復(fù)邊的權(quán)和超過(guò)此圈權(quán)和的一半，則將C中的重復(fù)邊改為不重復(fù)，而將單邊改為重復(fù)邊。重復(fù)這一過(guò)程，直到對(duì)G2的所有圈，其重復(fù)邊的權(quán)和不超此圈權(quán)和的一半，得到圖G3。（4）G3的Euler回路。98中國(guó)郵遞員問(wèn)題10.6圖的實(shí)例分析例10.19求圖10.51所示圖G的最優(yōu)環(huán)游。解：圖G中有6個(gè)奇點(diǎn)v2，v4，v5，v7，v9，v10，把它們配成三對(duì)：v2與v5，v4與v7，v9與v10。在圖G中，取一條連接v2與v5的路v2v3v4v5，把邊(v2，v3)，(v3，v4)，(v4，v5)作為重復(fù)邊加入圖中；再取v4與v7之間一條路v4v5v6v7，把邊(v4，v5)，(v5，v6)，(v6，v7)作為重復(fù)邊加入圖中，在v9和v10之間加一條重復(fù)邊(v9，v10)，如圖10.52所示，這個(gè)圖沒(méi)有奇點(diǎn)，是一個(gè)歐拉圖。圖10.51-10.5399中國(guó)郵遞員問(wèn)題10.6圖的實(shí)例分析在圖10.52中，頂點(diǎn)v4與v5之間有3條重邊，去掉其中2條，得圖10.53所示的圖，該圖仍是一個(gè)歐拉圖。如圖10.53中，圈v2v3v4v11v2的總權(quán)為24，而圈上重復(fù)邊的權(quán)和為14，大于該圈總權(quán)的一半，于是去掉邊(v2,v3)和(v3,v4)上的重復(fù)邊，而在邊(v2

,v11)和(v4,v11)上加入重復(fù)邊，此時(shí)重復(fù)邊的權(quán)和為10，小于該圈總權(quán)的一半。同理，圈v5v6v7v12v5的總權(quán)為25，而重復(fù)邊權(quán)和為15，于是去掉邊(v5,

v6)和(v6,v7)上的重復(fù)邊，在邊(v5,v12)和(v7,v12)上加重復(fù)邊，如圖10.54所示。圖10.54-10.56100中國(guó)郵遞員問(wèn)題10.6圖的實(shí)例分析圖10.54中，圈v4v5v12v11v4的總權(quán)為15，而重復(fù)邊的權(quán)和為8，從而調(diào)整為圖10.55所示。圖10.55中，圈v1v2v11v12v7v8v9v10v1的總權(quán)為36，而重復(fù)邊的總權(quán)為20，繼續(xù)調(diào)整為圖10.56所示。檢查圖10.56，可知定理的⑴和⑵均滿足，故為最優(yōu)方案，接著給出出圖10.56所示圖的Euler回路，即為圖G的最優(yōu)環(huán)游

由上例可知，對(duì)于比較大的圖，要考察每個(gè)圈上重復(fù)邊權(quán)和不大于該圈總權(quán)和的一半，確定每個(gè)圈的時(shí)間復(fù)雜性太大。1973年Edmonds和Johnson給出了一個(gè)更有效算法。101中國(guó)郵遞員問(wèn)題10.6圖的實(shí)例分析旅行售貨員問(wèn)題（TravelingSalesmanProblem）是在加權(quán)完全無(wú)向圖中，求經(jīng)過(guò)每個(gè)頂點(diǎn)恰好一次的（邊）權(quán)和最小的哈密爾頓圈，又稱之為最優(yōu)哈密爾頓圈（OptimumHamiltoncycle）。如果我們將加權(quán)圖中的結(jié)點(diǎn)看作城市，加權(quán)邊看作距離，旅行售貨員問(wèn)題就成為找出一條最短路線，使得旅行售貨員從某個(gè)城市出發(fā)，遍歷每個(gè)城市一次，最后再回到出發(fā)的城市。102旅行售貨員問(wèn)題10.6圖的實(shí)例分析若選定出發(fā)點(diǎn)，對(duì)n個(gè)城市進(jìn)行排列，因第二個(gè)頂點(diǎn)有n-1種選擇，第三個(gè)頂點(diǎn)有n-2種選擇，依次類推，共有(n-1)!條哈密爾頓圈?？紤]到一個(gè)哈密爾頓圈可以用相反兩個(gè)方向來(lái)遍歷，因而只需檢查個(gè)哈密爾頓圈，從中找出權(quán)和最小的一個(gè)。我們知道隨著n的增加而增長(zhǎng)得極快，比如有20個(gè)頂點(diǎn)，需考慮（約為）條不同的哈密爾頓圈。要檢查每條哈密爾頓圈用最快的計(jì)算機(jī)也需大約1年的時(shí)間才能求出該圖中長(zhǎng)度最短的一條哈密爾頓圈。因?yàn)槁眯惺圬泦T問(wèn)題同時(shí)具有理論和實(shí)踐的重要性，所以已經(jīng)投入了巨大的努力來(lái)設(shè)計(jì)解決它的有效算法。目前還沒(méi)有找到一個(gè)有效算法！當(dāng)有許多需要訪問(wèn)的頂點(diǎn)時(shí)，解決旅行售貨員問(wèn)題的實(shí)際方法是使用近似算法（Approximationalgorithm）。103旅行售貨員問(wèn)題10.6圖的實(shí)例分析最鄰近方法的步驟如下：（1）由任意選擇的結(jié)點(diǎn)開(kāi)始，指出與該結(jié)點(diǎn)最靠近（即權(quán)最?。┑狞c(diǎn)，形成有一條邊的初始路。（2）設(shè)x表示最新加到這條路上的結(jié)點(diǎn)，從不在路上的所有結(jié)點(diǎn)中選一個(gè)與x最靠近的結(jié)點(diǎn)，把連接x與這個(gè)結(jié)點(diǎn)的邊加到這條路上。重復(fù)這一步，直到圖中所有結(jié)點(diǎn)包含在路上。（3）將連接起點(diǎn)與最后加入的結(jié)點(diǎn)之間的邊加到這條路上，就得到一個(gè)哈密爾頓圈，即得問(wèn)題的近似解。104旅行售貨員問(wèn)題10.6圖的實(shí)例分析例10.20用“最鄰近方法”找出圖10.57所示加權(quán)完全圖中具有充分小權(quán)的哈密爾頓圈。解：ADCBEFA的權(quán)和為55，BCADEFB的權(quán)和為53，CBADEFC的權(quán)和為42，DABCFED的權(quán)和為42，EADCBFE的權(quán)和為51，F(xiàn)CBADEF的權(quán)和為42。由上例可知，所選取的哈密爾頓圈不同，其近似解也不同，而“最鄰近插入法”對(duì)上述方法可以進(jìn)行改進(jìn)，從而產(chǎn)生一個(gè)較好的結(jié)果。該方法在每次迭代中都構(gòu)成一個(gè)閉的旅行路線。它是由多個(gè)階段而形成的一個(gè)個(gè)旅程，逐步建立起來(lái)的，每一次比上一次多一個(gè)頂點(diǎn)，即是說(shuō)，下一個(gè)旅程比上一個(gè)旅程多一個(gè)頂點(diǎn)，求解時(shí)，在已建立旅程以外的頂點(diǎn)中，尋找最鄰近于旅程中某個(gè)頂點(diǎn)的頂點(diǎn)，然后將其插入該旅程中，并使增加的距離盡可能小，當(dāng)全部頂點(diǎn)收入這個(gè)旅程后，就找到了我們所求的最短哈密爾頓圈的近似解。105旅行售貨員問(wèn)題10.6圖的實(shí)例分析最鄰近插入法的步驟如下（圖中有n個(gè)結(jié)點(diǎn)）：（1）取圖中一點(diǎn)，作閉回路，置。（2），則輸出閉回路，結(jié)束；否則轉(zhuǎn)⑶。（3）在已有閉回路之外的結(jié)點(diǎn)中，選取與閉回路最鄰近的點(diǎn)u。（4）將u插入閉回路的不同位置可得k條不同的閉回路，從這k條閉回路選取一條長(zhǎng)度最小的作為新的閉回路。，轉(zhuǎn)（2）。106旅行售貨員問(wèn)題10.6圖的實(shí)例分析例10.21用“最鄰近插入法”找出圖10.57所示加權(quán)完全圖中具有充分小權(quán)的哈密爾頓圈。解：①開(kāi)始于頂點(diǎn)A，組成閉旅程AA。②最鄰近A的頂點(diǎn)為D，建立閉旅程ADA。③頂點(diǎn)B最鄰近頂點(diǎn)A，建立閉旅程ADBA。④由于C最鄰近B，將C插入，分別得到三個(gè)閉旅程ACDBA、ADCBA、ADBCA，其長(zhǎng)度依次為33、20、23，選取長(zhǎng)度最短的旅程ADCBA。⑤距旅程ADCBA中頂點(diǎn)最鄰近頂點(diǎn)為F，將F插入，分別得到四個(gè)閉旅程AFDCBA、ADFCBA、ADCFBA、ADCBFA，其長(zhǎng)度依次為52、34、37、45，選取長(zhǎng)度最短的旅程ADFCBA。⑥把頂點(diǎn)E插入旅程ADFCBA中，得到5個(gè)閉旅程AEDFCBA、ADEFCBA、ADFECBA、ADFCEBA、ADFCBEA、，其長(zhǎng)度依次為54、42、60、61、49。顯然，長(zhǎng)度最短的旅程ADEFCBA即為我們要求的最短哈密爾頓圈的近似解。107旅行售貨員問(wèn)題10.6圖的實(shí)例分析排課是高校教學(xué)管理中一項(xiàng)重要而且復(fù)雜的基本工作，其實(shí)質(zhì)就是為學(xué)校所設(shè)置的課程安排一組適當(dāng)?shù)慕虒W(xué)時(shí)間與空間，從而使整個(gè)教學(xué)活動(dòng)能夠有計(jì)劃有秩序地進(jìn)行。在排課問(wèn)題中，其主要任務(wù)是將具有多種屬性的各種資源，如教室、班級(jí)、教師、學(xué)生、課程、時(shí)間等，以一個(gè)周期的方式進(jìn)行合理的匹配，使其不發(fā)生沖突。事實(shí)上，在排課問(wèn)題中，每節(jié)課可抽象為教師和學(xué)生在時(shí)間和空間上的統(tǒng)一。因此，課表是協(xié)調(diào)教師和上課班級(jí)在上課時(shí)間、上課教室兩個(gè)要素的總調(diào)度。課表算法本質(zhì)要求主體即教師和上課班級(jí)合理使用時(shí)間和教室兩種資源。課表的編排包括教師和上課班級(jí)在上課時(shí)間（節(jié)次）和上課地點(diǎn)（教室）上的編排，這其中的組合可能性太多，為此可將模型簡(jiǎn)化為兩個(gè)子模型：教師和上課班級(jí)在時(shí)間（節(jié)次）上的編排；教師和上課班級(jí)在地點(diǎn)（教室）上的編排，而這兩個(gè)優(yōu)化過(guò)程都可以轉(zhuǎn)化為圖論問(wèn)題來(lái)解決。108排課問(wèn)題10.6圖的實(shí)例分析109排課問(wèn)題排課問(wèn)題在時(shí)間上的安排實(shí)際上就是安排每一個(gè)教師在具體的時(shí)間段到某個(gè)具體的班級(jí)去上課。這個(gè)安排要求滿足下面的條件：同一時(shí)間每位教師只能到一個(gè)班級(jí)去上課；一個(gè)班級(jí)在同一個(gè)時(shí)間也只能由一位教師來(lái)上課。用圖論的知識(shí)可以來(lái)表示這個(gè)問(wèn)題。例如：有n位教師，用x1,x2,…,xn來(lái)表示，有m

個(gè)班，用y1,y2,…,ym來(lái)表示，教師xi要給班級(jí)yj上課就將xi與yj相連，如果一周內(nèi)教師xi要給班級(jí)yj

上2次課，則連2條線，以此類推?？梢韵茸饕粋€(gè)二部圖G，使G=(X,Y,E)，其中X={x1,x2,…,xn}代表n

個(gè)教師，Y={y1,y2,…,ym}代表m

個(gè)班級(jí)，E代表xi與yj之間連接的邊，如圖10.58表示。圖10.5810.6圖的實(shí)例分析有相同頂點(diǎn)的邊稱為相鄰邊。對(duì)每一條邊進(jìn)行著色，一種顏色代表一個(gè)時(shí)間段，通常在大學(xué)中2個(gè)課時(shí)為1節(jié)課，每天4節(jié)，一周5天，故而在排課問(wèn)題中邊色數(shù)是20，代表的是20個(gè)時(shí)間段，同種顏色的邊代表同一個(gè)時(shí)間段。因?yàn)樵谕粫r(shí)間每位教師只能到一個(gè)班級(jí)去上課，而一個(gè)班級(jí)也只能由一位教師來(lái)上課，相鄰的邊代表有共同的教師或?qū)W生，不可以安排在同一個(gè)時(shí)間段同時(shí)上課，因此相鄰的邊不能著相同的顏色。時(shí)間表的安排就變成了對(duì)所有的邊進(jìn)行著色，有相同頂點(diǎn)的邊著不同的顏色，而所有顏色的種類不能超過(guò)20種。110排課問(wèn)題10.6圖的實(shí)例分析課表在地點(diǎn)安排上則是安排某個(gè)班級(jí)在某個(gè)時(shí)間段在一個(gè)具體的教室上課的問(wèn)題，它必須要滿足的條件是：班級(jí)人數(shù)小于教室的容量，也就是容量大于班級(jí)人數(shù)的教室都可用，這樣班級(jí)與