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

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

圖10.1哥尼斯堡七橋

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

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

，則G有一條從至的歐拉路徑當(dāng)且僅當(dāng)G恰有兩個奇結(jié)點(diǎn)和。1010.1歐拉圖定理10.3設(shè)G為弱連通的有向圖。G是歐拉有向圖，當(dāng)且僅當(dāng)G有歐拉閉路。定理10.4設(shè)G為弱連通有向圖。和為G的兩個不同結(jié)點(diǎn)。G有一條從至的歐拉路徑，當(dāng)且僅當(dāng)=+1，=-1，且對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哈密爾頓圖愛爾蘭數(shù)學(xué)家哈密爾頓（WilliamHamilton）爵士1859年提出了一個“周游世界”的游戲。這個游戲把一個正十二面體的二十個頂點(diǎn)看成地球上的二十個城市。棱線看成是連接城市的航路（航空、航海線或陸路交通線），要求游戲者沿棱線走，尋找一條經(jīng)過所有結(jié)點(diǎn)（即城市）一次且僅一次的回路，如圖10.6（a）所示。也就是在圖10.6（b）中找一條包含所有結(jié)點(diǎn)的圈。圖（b）中的粗線所構(gòu)成的圈就是這個問題的回答。與歐拉圖不同，哈密爾頓圖是遍歷圖中的每個結(jié)點(diǎn)，一條哈密爾頓回路不會在兩個結(jié)點(diǎn)間走兩次以上，因此沒有必要在有向圖中討論。14圖10.610.2哈密爾頓圖愛爾蘭數(shù)學(xué)家哈密爾頓（WilliamHamilton）爵士1859年提出了一個“周游世界”的游戲。這個游戲把一個正十二面體的二十個頂點(diǎn)看成地球上的二十個城市。棱線看成是連接城市的航路（航空、航海線或陸路交通線），要求游戲者沿棱線走，尋找一條經(jīng)過所有結(jié)點(diǎn)（即城市）一次且僅一次的回路，如圖10.6（a）所示。也就是在圖10.6（b）中找一條包含所有結(jié)點(diǎn)的圈。圖（b）中的粗線所構(gòu)成的圈就是這個問題的回答。與歐拉圖不同，哈密爾頓圖是遍歷圖中的每個結(jié)點(diǎn)，一條哈密爾頓回路不會在兩個結(jié)點(diǎn)間走兩次以上，因此沒有必要在有向圖中討論。15圖10.610.2哈密爾頓圖定義10.3給定無向圖G，圖G中包含其所有頂點(diǎn)的簡單開路徑稱為圖G的哈密爾頓路徑，圖G中包含其所有頂點(diǎn)的簡單閉路徑稱為G的哈密爾頓回路。具有哈密頓回路的圖稱為哈密爾頓圖。由定義可知哈密爾頓圈與哈密爾頓路通過圖G中的每個結(jié)點(diǎn)一次且僅一次，例如圖10.6（b）就是哈密爾頓圖（哈密爾頓圈用實(shí)線標(biāo)出）。1610.2哈密爾頓圖例10.3圖10.7中，圖（a）、（b）中有哈密爾頓圈，圖（c）中有哈密爾頓路，（d）中既沒有哈密爾頓圈也沒有哈密爾頓路。圖10.7

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

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

V的非空子集

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

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

a講英語； b講英語和漢語；

c講英語、意大利語和俄語； d講日語和漢語；

e講德國和意大利語； f講法語、日語和俄語；

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

和

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

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

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

，則稱為G中的極大匹配。（3）G中的邊數(shù)最多的匹配稱為G中的最大匹配。（4）G中的最大匹配包含的邊數(shù)稱為G的匹配數(shù)。顯然，最大匹配一定是極大匹配，而極大匹配不一定是最大匹配。在一個無向圖中，可以有多個極大匹配和最大匹配。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∣時可能存在從V1到V2的完美匹配。但這個條件并不是充分條件。如圖10.16給出的二部圖中，V1＝{a1,a2,a3,a4},V2＝{p1,p2,p3,p4,p5,p6},∣V2∣>∣V1∣，但并不存在V1到V2的完美匹配。下面的定理給出了存在完美匹配的充分必要條件。圖10.16無向圖中的匹配3110.3二部圖及匹配定理10.10設(shè)

和

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

到

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

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

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

也是一個多邊形的圖，其中V=V∪｛u1，u2，…，ul-1｝E=E∪｛{vi，u1}，{u1，u2}，…，{ul-1，vj}｝多邊形的圖是個平面圖（或多重邊圖，因?yàn)樵试S長度為2的循環(huán)存在），它能夠把平面劃分成數(shù)個區(qū)域，每一個區(qū)域都是由一個多邊形定界。4510.4平面圖例10.13圖10.27中的圖是一個多邊形的圖。圖10.27多邊形的圖4610.4平面圖定義10.11由多邊形的圖定界的每一個區(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)該說明，給定圖G的極大基本循環(huán)外側(cè)的無限區(qū)域，是另外一個面，一般稱為G的無限面。事實(shí)上，如果把圖G的圖解畫在球面上，則G的無限面與其它的有限面并沒有什么區(qū)別。4710.4平面圖定義10.13如果圖G的兩個面共有一條邊，則稱這樣的兩個面是鄰接的面。定理10.13

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

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

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

A)是指一個連通無環(huán)且滿足下列條件的有向圖。（1）有一個頂點(diǎn)子集X，其每個頂點(diǎn)的入度都是0。（2）有一個與X不相交的頂點(diǎn)子集Y，其每個頂點(diǎn)的出度都為0。（3）每條弧都有一個非負(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ò)中對應(yīng)于網(wǎng)絡(luò)的入口和出口，或者說計(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ò)中，它對應(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ò)如果一個網(wǎng)絡(luò)中的源點(diǎn)集和匯點(diǎn)集都只包含一個頂點(diǎn)，我們稱該網(wǎng)絡(luò)為單源單匯網(wǎng)絡(luò)。事實(shí)上，對于任意網(wǎng)絡(luò)N=(V,X,Y,A,C)，在經(jīng)過一定的處理后，都可以轉(zhuǎn)變?yōu)橐粋€單源單匯網(wǎng)絡(luò)。處理的方法為：（1）給網(wǎng)絡(luò)N添加兩個新的頂點(diǎn)s和t。（2）對任意xX，從s向x添加一條弧，其容量為（或

）。（3）對任意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ò)簡單地說，只需要在原有非單源單匯網(wǎng)絡(luò)中添加一個新的源點(diǎn)和一個新的匯點(diǎn)，并且添加從新的源點(diǎn)指向原有源點(diǎn)的弧，再添加從原有匯點(diǎn)指向新的匯點(diǎn)的弧，就能得到一個單源單匯網(wǎng)絡(luò)。圖10.34單源單匯網(wǎng)絡(luò)對圖10.33所示的網(wǎng)絡(luò)添加人工源和人工匯后，將變?yōu)閳D10.34所示的單源單匯網(wǎng)絡(luò)。單源單匯網(wǎng)絡(luò)是一種特殊的網(wǎng)絡(luò)，它在各種網(wǎng)絡(luò)問題的求解方面比非單源單匯網(wǎng)絡(luò)更為簡單。由于任意網(wǎng)絡(luò)都可以轉(zhuǎn)化為單源單匯網(wǎng)絡(luò)，后續(xù)章節(jié)中對網(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)的緩存大小，此時結(jié)點(diǎn)的轉(zhuǎn)發(fā)能力會受到限制。結(jié)點(diǎn)能力的限制并不能直接在圖上體現(xiàn)出來，對于這樣的情況，可以做一個轉(zhuǎn)換，其方法為：將中轉(zhuǎn)能力受限的結(jié)點(diǎn)分裂為兩個結(jié)點(diǎn)，并且在這兩個結(jié)點(diǎn)之間加入一條弧，這樣就可以利用這條新加入的弧來表示結(jié)點(diǎn)的轉(zhuǎn)發(fā)能力受限。經(jīng)過轉(zhuǎn)化為單源單匯網(wǎng)絡(luò)并將結(jié)點(diǎn)能力的受限轉(zhuǎn)化為弧的受限后，實(shí)際網(wǎng)絡(luò)問題可以轉(zhuǎn)化為圖論中的網(wǎng)絡(luò)問題。5810.5網(wǎng)絡(luò)定義10.17

可行流為：網(wǎng)絡(luò)N=(V,X,Y,A,C)中的一個可行流是指定義在A上的一個整值函數(shù)f，使得：（1）對任意aA，0≤f(a)≤c(a),（容量約束）；（2）對任意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ò)也就是說，可行流滿足兩個條件：一是容量約束，即可行流在某一弧上的流量小于該弧的容量；二是流量守恒，即流入某一中轉(zhuǎn)點(diǎn)的流量等于流出該點(diǎn)的流量。需要強(qiáng)調(diào)的是，可行流總是存在的，如果f(a)=0，這個流稱為零值流。對于網(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)中的一個可行流，則必有f+(X)=f-(Y)。f+(X)（或f-(Y)）稱為流f的流量，記為Valf。流是網(wǎng)絡(luò)中的重要概念，在實(shí)際網(wǎng)絡(luò)問題中，經(jīng)常需要求解與流相關(guān)的問題，例如網(wǎng)絡(luò)的最大流等。所謂最大流，是指網(wǎng)絡(luò)N中流量最大的可行流。網(wǎng)絡(luò)的最大流對于實(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年提出了著名的最大流最小割定理，巧妙地將流與割對應(yīng)起來，將最大流問題轉(zhuǎn)化為最小割問題。61流量10.5網(wǎng)絡(luò)定義10.19設(shè)N=(V,x,y,A,C)是一個單源單匯網(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的一個割。一個割(S,)的容量是指(S,)中各條弧的容量之和，記為Cap(S,)。6210.5網(wǎng)絡(luò)定義10.19設(shè)N=(V,x,y,A,C)是一個單源單匯網(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的一個割。一個割(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。對網(wǎng)絡(luò)N中的任意流f和任意割(S,)，流f的流量等于流出S的流量與流入S的流量之差，即Valf=f+(S)-f-(S)。網(wǎng)絡(luò)N可能存在多個割，各個割的容量并不一定相等，其中容量最小的一個割稱為網(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í)際上，割就是一個弧的集合，如果去掉這些弧，就可以把網(wǎng)絡(luò)“分割”成分別包含了源點(diǎn)和匯點(diǎn)的兩部分。由于從源點(diǎn)到匯點(diǎn)必須要經(jīng)過這些弧，因此，如果能求出最小的割集，就能得到最大流。最大流最小割定理對于求解最大流具有非常重要的指導(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的一條反向?。ɑ蚍Q后向弧、逆向?。?。將u-v路P所經(jīng)過的弧（無論正向弧還是反向?。┓Q為路P上的弧。66在圖10.35中的網(wǎng)絡(luò)N中，x-y路P=xv1v3v4y上，所有弧都是正向弧；而在x-y路Q=xv2v4v3y上，弧<x,v2>和<v3,y>是正向弧，而<v4,v2>和<v3,v4>是反向弧?？梢钥闯?，對于同一條弧<v3,v4>，在路P中為正向弧，而在路Q中為反向弧?？梢?，一條弧是正向弧還是反向弧與路的選擇有關(guān)。10.5網(wǎng)絡(luò)定義10.21假設(shè)f是網(wǎng)絡(luò)N=(V,X,Y,A,C)中的一個可行流，u是N中任意一點(diǎn)，P是網(wǎng)絡(luò)N中的一條x-u路，如果對路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路可簡稱為N的一條f可增路。對于N中任意一條f可增路P和P上任意一條弧a，假設(shè)沿路P可增加的流量為，這一值稱為f可增路P上流的增量（可增量）。6710.5網(wǎng)絡(luò)68圖10.36網(wǎng)絡(luò)的課可增路可增量在求解網(wǎng)絡(luò)的最大流問題時非常重要，求解網(wǎng)絡(luò)最大流問題的幾種常用算法都是基于可增量方法的。下面，我們介紹最大流問題求解的兩種經(jīng)典算法：標(biāo)號算法和Dinic算法。10.5網(wǎng)絡(luò)標(biāo)號算法就是由可增路的概念得到的。其基本原理為：對于一個網(wǎng)絡(luò)N中的一個可行流f，如果能找到N中的一條f可增x-y路P，則可沿著P修改流的值，得到一個流量更大的可行流f

’。修改后流的流量為Valf

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

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

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

)中每條弧的容量恰好是N中對應(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路對應(yīng)的，它是N的f可增路。因此，我們可以用在增量網(wǎng)絡(luò)N(

f

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

為了更快地得到最大流，我們需要對增量網(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的最短有向路的長度為i}。假設(shè)x到y(tǒng)的最短有向路的長度為n，則：（1）xV，yVn。（2）Vi∩Vj=Φ，(j≠i)。Vi中的頂點(diǎn)稱為網(wǎng)絡(luò)N的第i層頂點(diǎn)。上述有向路的長度是指路上有向邊的數(shù)目，而兩點(diǎn)間最短有向路指兩點(diǎn)間有向邊最少的有向路。按照上述分層原則，我們可以對圖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ò)對分層后的網(wǎng)絡(luò)進(jìn)行進(jìn)一步的操作就可以得到輔助網(wǎng)絡(luò)。輔助網(wǎng)絡(luò)是在增量網(wǎng)絡(luò)和網(wǎng)絡(luò)分層的基礎(chǔ)上得到的。其定義為：對于網(wǎng)絡(luò)N=(V,x,y,A,C)，假設(shè)N(f

)是N的關(guān)于流f的增量網(wǎng)絡(luò)。對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

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

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

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

)進(jìn)行分層并得到輔助網(wǎng)絡(luò)的過程。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開始，執(zhí)行如下過程：（1）構(gòu)造增量網(wǎng)絡(luò)N(f

)（2）對N(f

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

)（3）求AN(f

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

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

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

)剩余網(wǎng)絡(luò)中沒有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ò)為例來演示Dinic算法，從而比較標(biāo)號算法和Dinic算法的聯(lián)系和區(qū)別。Dinic算法的演示過程如圖10.43所示。83Dinic網(wǎng)絡(luò)10.5網(wǎng)絡(luò)可以看出，執(zhí)行的過程與標(biāo)號算法類似，但是在求可增流的過程中，Dinic算法借助增量網(wǎng)絡(luò)和輔助網(wǎng)絡(luò)更直觀的得到可增流，為了演示標(biāo)號算法和Dinic算法的聯(lián)系，每次增流都只進(jìn)行了一次，實(shí)際上，前兩次增流可以一次完成。在簡單的網(wǎng)絡(luò)中，兩者差別不大，但是在復(fù)雜的網(wǎng)絡(luò)中，Dinic算法在復(fù)雜度上有一定的優(yōu)勢。下面我們來看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ù)量。在每次可增加的量較小時，Dinic算法的復(fù)雜度要明顯低于標(biāo)號算法。84Dinic網(wǎng)絡(luò)10.5網(wǎng)絡(luò)定義10.24

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

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

若

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

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

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

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

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

,v11)和(v4,v11)上加入重復(fù)邊，此時重復(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中國郵遞員問題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)游

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

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

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

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

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