數(shù)學(xué)建模離散優(yōu)化模型與算法設(shè)計(jì)

1、整理課件整理課件數(shù)學(xué)建模離散優(yōu)化模型及算法設(shè)計(jì)之前之前, ,我們介紹了與計(jì)算復(fù)雜性有關(guān)的一些基本概念我們介紹了與計(jì)算復(fù)雜性有關(guān)的一些基本概念. .人們發(fā)現(xiàn)人們發(fā)現(xiàn), ,在離散在離散問(wèn)題中存在著兩個(gè)互不相交的類：?jiǎn)栴}中存在著兩個(gè)互不相交的類：P P類與類與NPNP完全類（若完全類（若P PNPNP）。前者具）。前者具有求解的有效算法而后者不可能有這種算法。從這一點(diǎn)上講，有求解的有效算法而后者不可能有這種算法。從這一點(diǎn)上講，P P問(wèn)題可問(wèn)題可以看成是一類具有良好性質(zhì)而又較容易求解的問(wèn)題，而以看成是一類具有良好性質(zhì)而又較容易求解的問(wèn)題，而NPNP完全問(wèn)題則是完全問(wèn)題則是固有地難解的。固有地難解的。在

2、中看到，有著廣泛應(yīng)用背景的線性規(guī)劃問(wèn)題是一個(gè)在中看到，有著廣泛應(yīng)用背景的線性規(guī)劃問(wèn)題是一個(gè)P P問(wèn)題。這樣，作為問(wèn)題。這樣，作為線性規(guī)劃子問(wèn)題的運(yùn)輸問(wèn)題及作為運(yùn)輸問(wèn)題子問(wèn)題的指派問(wèn)題自然更是線性規(guī)劃子問(wèn)題的運(yùn)輸問(wèn)題及作為運(yùn)輸問(wèn)題子問(wèn)題的指派問(wèn)題自然更是P P問(wèn)題。雖然從平均的角度講，人們似乎更常遇到問(wèn)題。雖然從平均的角度講，人們似乎更常遇到NPNP完全問(wèn)題，但完全問(wèn)題，但P P仍不失仍不失為一個(gè)十分重要的問(wèn)題類。一方面，很多為一個(gè)十分重要的問(wèn)題類。一方面，很多P P問(wèn)題象線性規(guī)劃一樣有著極廣問(wèn)題象線性規(guī)劃一樣有著極廣泛的應(yīng)用前景，且它們本身又是十分有趣的；另一方面，它們也是研究泛的應(yīng)用前景，且

3、它們本身又是十分有趣的；另一方面，它們也是研究一些更為復(fù)雜、難解的問(wèn)題時(shí)經(jīng)常被采用的研究工具。在本章中，將再一些更為復(fù)雜、難解的問(wèn)題時(shí)經(jīng)常被采用的研究工具。在本章中，將再介紹一些經(jīng)常遇到的介紹一些經(jīng)常遇到的P P問(wèn)題并給出求解它們的有效算法。問(wèn)題并給出求解它們的有效算法。 一、擬陣問(wèn)題及貪婪算法一、擬陣問(wèn)題及貪婪算法在在P類中又存在著一個(gè)被稱為擬陣的具有更為良好性質(zhì)的問(wèn)題類，其中的任類中又存在著一個(gè)被稱為擬陣的具有更為良好性質(zhì)的問(wèn)題類，其中的任一問(wèn)題均可用一種被稱為貪婪法的方法來(lái)求解，而這一性質(zhì)并不是所有的一問(wèn)題均可用一種被稱為貪婪法的方法來(lái)求解，而這一性質(zhì)并不是所有的P問(wèn)題都具有的。問(wèn)題都具

4、有的。 例例 9.1 （最小生成樹(shù)問(wèn)題（最小生成樹(shù)問(wèn)題MST）給定一連通圖給定一連通圖G=（V，E），）， ，有一表示邊長(zhǎng)的權(quán)有一表示邊長(zhǎng)的權(quán)C（e）（表示頂點(diǎn)間的距離或費(fèi)用），求此圖的具有最）（表示頂點(diǎn)間的距離或費(fèi)用），求此圖的具有最小總權(quán)的生成樹(shù)。小總權(quán)的生成樹(shù)。e此問(wèn)題的標(biāo)準(zhǔn)形式為給定一完全圖此問(wèn)題的標(biāo)準(zhǔn)形式為給定一完全圖G G，其每邊賦有一權(quán)數(shù)，求此完全圖的，其每邊賦有一權(quán)數(shù)，求此完全圖的最小生成樹(shù)。所謂樹(shù)是指連通而無(wú)圈的圖，單獨(dú)的一個(gè)點(diǎn)也可看成一顆最小生成樹(shù)。所謂樹(shù)是指連通而無(wú)圈的圖，單獨(dú)的一個(gè)點(diǎn)也可看成一顆樹(shù)。樹(shù)用樹(shù)。樹(shù)用( (U U，T T) )表示，表示，U U為樹(shù)的頂點(diǎn)，為樹(shù)

5、的頂點(diǎn)，T T為樹(shù)的邊集。不相交的樹(shù)的集合為樹(shù)的邊集。不相交的樹(shù)的集合被稱為森林。一個(gè)連通圖的生成樹(shù)是指圖中具有最多邊數(shù)的一棵樹(shù)。容被稱為森林。一個(gè)連通圖的生成樹(shù)是指圖中具有最多邊數(shù)的一棵樹(shù)。容易證明，對(duì)于一個(gè)連通圖易證明，對(duì)于一個(gè)連通圖G G，G G 的任一生成樹(shù)必有的任一生成樹(shù)必有V V-1-1條邊。條邊。求解最小生成樹(shù)的算法主要依據(jù)下面的定理：求解最小生成樹(shù)的算法主要依據(jù)下面的定理：定理定理 9.1 設(shè)設(shè)（V1，T1），），（Vk ,Tk）為連通圖為連通圖G中的森林，中的森林，V1 U V2U Vk=V。 k,若僅有一個(gè)頂點(diǎn)在若僅有一個(gè)頂點(diǎn)在Vi中的具有最小權(quán)的邊為（中的具有最小權(quán)的邊為

6、（ ,u），），則必有一棵則必有一棵G的最小生成樹(shù)包含邊（的最小生成樹(shù)包含邊（ ,u）。）。, 1i根據(jù)定根據(jù)定1可以作了如下算法：任選一點(diǎn)可以作了如下算法：任選一點(diǎn) ，令，令 若若V1=V，停；否則，找出僅有一個(gè)頂點(diǎn)在，停；否則，找出僅有一個(gè)頂點(diǎn)在V1中的邊里具有最小權(quán)的邊中的邊里具有最小權(quán)的邊（ ,u），設(shè)，將），設(shè)，將u加入加入V1（ ,u）加入）加入T。重復(fù)上述步驟，直到。重復(fù)上述步驟，直到V1=V。 1 11:,:.VT 證明：設(shè)：設(shè)G的一棵最小生成樹(shù)（的一棵最小生成樹(shù)（V，T）不含（）不含（ ,u）。將（）。將（ ,u）加入）加入T，由于（由于（V，T）是生成樹(shù)，）是生成樹(shù)，T U

7、（ ,u）中含有過(guò)（）中含有過(guò)（ ,u）的唯一的圈。不）的唯一的圈。不妨設(shè)妨設(shè) ，則，則 ，此圈中的點(diǎn)不全由，此圈中的點(diǎn)不全由Vi中的點(diǎn)組成中的點(diǎn)組成,因此必存在因此必存在圈中的另一邊圈中的另一邊 。刪去邊。刪去邊 得到一新的生成樹(shù)（得到一新的生成樹(shù)（V，T1），），T1= ，須其總權(quán)不超過(guò)（，須其總權(quán)不超過(guò)（V，T）的權(quán)）的權(quán),即（即（V，T）是包含邊（是包含邊（ ,u）的最小生成樹(shù)。）的最小生成樹(shù)。iViV,iiuuu,uu例例9.2 求圖中圖求圖中圖G的最小生成樹(shù)。的最小生成樹(shù)。解：不妨從頂點(diǎn)開(kāi)始尋找。不妨從頂點(diǎn)開(kāi)始尋找。 標(biāo)號(hào)標(biāo)號(hào)1，先加入，先加入 （因?yàn)檫厵?quán)（因?yàn)檫厵?quán)最?。?，最小），

8、 標(biāo)號(hào)標(biāo)號(hào)2。再加入。再加入 標(biāo)號(hào)標(biāo)號(hào)3。，每次加入一條一頂點(diǎn)已標(biāo)，每次加入一條一頂點(diǎn)已標(biāo)號(hào)加一頂點(diǎn)未標(biāo)號(hào)而又具有最小權(quán)的邊，直到所有頂點(diǎn)均標(biāo)號(hào)為止。找號(hào)加一頂點(diǎn)未標(biāo)號(hào)而又具有最小權(quán)的邊，直到所有頂點(diǎn)均標(biāo)號(hào)為止。找到的最小生成樹(shù)已用又線標(biāo)在圖到的最小生成樹(shù)已用又線標(biāo)在圖9.2中。中。 111,V212244 容易看出算法的計(jì)算量為容易看出算法的計(jì)算量為O (V)2 ，所以此算法是有效算法，若，所以此算法是有效算法，若G具有具有O（ ）條邊，其中）條邊，其中n= V ，計(jì)算量的界還是不能改進(jìn)的，因?yàn)槊織l，計(jì)算量的界還是不能改進(jìn)的，因?yàn)槊織l邊至少應(yīng)被檢查一次。邊至少應(yīng)被檢查一次。2nC由例可以看出

9、，算法執(zhí)行的每一步均加入一條可以加入的（即不生成圈由例可以看出，算法執(zhí)行的每一步均加入一條可以加入的（即不生成圈的）具有最小權(quán)的邊，而不去考慮它對(duì)以后選取的影響，這種算法被稱的）具有最小權(quán)的邊，而不去考慮它對(duì)以后選取的影響，這種算法被稱為貪婪算法。為貪婪算法。例例9.3 (入樹(shù)問(wèn)題入樹(shù)問(wèn)題) 給出一個(gè)有向圖給出一個(gè)有向圖G=（V，A），對(duì)），對(duì)A中的每一條孤中的每一條孤e，給，給出一個(gè)權(quán)出一個(gè)權(quán)C（e），求），求A的一個(gè)具有最大權(quán)（或最小權(quán)）的子集的一個(gè)具有最大權(quán)（或最小權(quán)）的子集B，要求，要求B中任意兩條孤都沒(méi)有公共的終點(diǎn)。中任意兩條孤都沒(méi)有公共的終點(diǎn)?？疾煜旅娴娜霕?shù)問(wèn)題實(shí)例：考察下面的入樹(shù)

10、問(wèn)題實(shí)例：例例 給出有向圖給出有向圖G=（V，A）（圖）（圖），孤上標(biāo)出的數(shù)字為該邊的，孤上標(biāo)出的數(shù)字為該邊的權(quán)，求此圖具有最大權(quán)的入樹(shù)。權(quán)，求此圖具有最大權(quán)的入樹(shù)。解：由于入樹(shù)不能包含具有公共終點(diǎn)的孤，故對(duì)每一頂點(diǎn)解：由于入樹(shù)不能包含具有公共終點(diǎn)的孤，故對(duì)每一頂點(diǎn) 只能選取只能選取一條入孤。為使選出的弧具有最大權(quán)，只需要對(duì)每一頂點(diǎn)選取權(quán)最大的一條入孤。為使選出的弧具有最大權(quán)，只需要對(duì)每一頂點(diǎn)選取權(quán)最大的入孤，可用計(jì)算量為入孤，可用計(jì)算量為O O（V VE E）的貪婪法求解，具有最大權(quán)的入樹(shù)）的貪婪法求解，具有最大權(quán)的入樹(shù)為為 。 i 1221244553, 類似地，出樹(shù)問(wèn)題也可以用貪婪法求解

11、。類似地，出樹(shù)問(wèn)題也可以用貪婪法求解。 例例9.5 (矩陣擬陣問(wèn)題矩陣擬陣問(wèn)題)給出一個(gè)矩陣給出一個(gè)矩陣Amxn，記其，記其n個(gè)列向量為個(gè)列向量為e1,，en。設(shè)對(duì)每一列向量設(shè)對(duì)每一列向量en已指定一權(quán)已指定一權(quán)C（en）求）求 的一個(gè)線性無(wú)關(guān)的一個(gè)線性無(wú)關(guān)的子集，它具有最大的權(quán)和。的子集，它具有最大的權(quán)和。 1,iin易見(jiàn)，這一問(wèn)題也可以用貪婪法求解。集合易見(jiàn)，這一問(wèn)題也可以用貪婪法求解。集合 的線性無(wú)關(guān)的的線性無(wú)關(guān)的子集被稱為獨(dú)立子集，利用貪婪法必可求得具有最大權(quán)的獨(dú)立子集，可用子集被稱為獨(dú)立子集，利用貪婪法必可求得具有最大權(quán)的獨(dú)立子集，可用線性代數(shù)知識(shí)加以證明線性代數(shù)知識(shí)加以證明（見(jiàn)習(xí)題

12、（見(jiàn)習(xí)題1）。 1,iin例例 求矩陣求矩陣A的列向量具有最大權(quán)和的獨(dú)立子集的列向量具有最大權(quán)和的獨(dú)立子集7*45762101543100012731214531011AC(C(e ei i) ) 8 4 7 5 2 6 48 4 7 5 2 6 4解：采用貪婪法，先取權(quán)最大的列采用貪婪法，先取權(quán)最大的列e1，同時(shí)對(duì)，同時(shí)對(duì)A作高斯消去，逐次加入作高斯消去，逐次加入線性無(wú)關(guān)的向量：線性無(wú)關(guān)的向量：A的列向量中具有最大權(quán)的獨(dú)立子集為的列向量中具有最大權(quán)的獨(dú)立子集為 。1354取e6取e4取e3? ? ? ? ? ? ? ?4511020543100033421104531011123111054

13、3100033421104531011A4/904/194/90204/514/34/100033421104531011定義定義9.1 (擬陣擬陣) 設(shè)設(shè)E是一個(gè)有限集，是一個(gè)有限集，為為E的部分子集構(gòu)成的封閉系統(tǒng)（即的部分子集構(gòu)成的封閉系統(tǒng)（即若若 ，則必有，則必有 ）。若）。若M=（E，）上的離散優(yōu)化問(wèn)題的每一）上的離散優(yōu)化問(wèn)題的每一實(shí)例均可用貪婪算法求出最優(yōu)解，則稱實(shí)例均可用貪婪算法求出最優(yōu)解，則稱M為一擬陣。（注：為一擬陣。（注：被稱為獨(dú)立系被稱為獨(dú)立系統(tǒng)）。統(tǒng)）。,AAA現(xiàn)以矩陣擬陣為例，對(duì)定義作一說(shuō)明。現(xiàn)以矩陣擬陣為例，對(duì)定義作一說(shuō)明。對(duì)矩陣擬陣的每一實(shí)例，對(duì)矩陣擬陣的每一實(shí)例，

14、E=e1,en為矩陣列向量的集合，為矩陣列向量的集合，為為E的線性無(wú)關(guān)的線性無(wú)關(guān)子集構(gòu)成的系統(tǒng)，稱為獨(dú)立系統(tǒng)，其元素被稱為獨(dú)立子集。由于子集構(gòu)成的系統(tǒng)，稱為獨(dú)立系統(tǒng)，其元素被稱為獨(dú)立子集。由于E的任一線的任一線性無(wú)關(guān)子集的子集也是性無(wú)關(guān)子集的子集也是E的線性無(wú)關(guān)子集，故獨(dú)立系統(tǒng)的線性無(wú)關(guān)子集，故獨(dú)立系統(tǒng)是封閉的。又由于是封閉的。又由于這一離散優(yōu)化問(wèn)題的任一實(shí)例都可用貪婪法求解，故構(gòu)成一擬陣，被稱為這一離散優(yōu)化問(wèn)題的任一實(shí)例都可用貪婪法求解，故構(gòu)成一擬陣，被稱為矩陣擬陣。例被稱為圖擬陣，例被稱為劃分?jǐn)M陣。矩陣擬陣。例被稱為圖擬陣，例被稱為劃分?jǐn)M陣。 擬陣問(wèn)題（或稱擬陣結(jié)構(gòu)）擬陣問(wèn)題（或稱擬陣結(jié)構(gòu)

15、）有一個(gè)明顯而又本質(zhì)的特性，其任一極大獨(dú)立有一個(gè)明顯而又本質(zhì)的特性，其任一極大獨(dú)立子集中包含著相同個(gè)數(shù)的元素，從而可以引入基的概念。例如，矩陣列向子集中包含著相同個(gè)數(shù)的元素，從而可以引入基的概念。例如，矩陣列向量的所有線性無(wú)關(guān)極大組均具有相同的向量個(gè)數(shù)，這就導(dǎo)出了基量的所有線性無(wú)關(guān)極大組均具有相同的向量個(gè)數(shù)，這就導(dǎo)出了基即矩即矩陣列秩的概念。對(duì)于圖擬陣，每一極大獨(dú)立集均為一生成樹(shù)，其邊數(shù)均為陣列秩的概念。對(duì)于圖擬陣，每一極大獨(dú)立集均為一生成樹(shù)，其邊數(shù)均為|V|-1。對(duì)于劃分?jǐn)M陣，孤集被劃分成個(gè)。對(duì)于劃分?jǐn)M陣，孤集被劃分成個(gè)|V|個(gè)子集，每一子集由指向同一頂個(gè)子集，每一子集由指向同一頂點(diǎn)的孤組成

16、。顯然，任一極大獨(dú)立集應(yīng)在每一子集中取一條孤，故其基數(shù)點(diǎn)的孤組成。顯然，任一極大獨(dú)立集應(yīng)在每一子集中取一條孤，故其基數(shù)為頂點(diǎn)個(gè)數(shù)。為頂點(diǎn)個(gè)數(shù)。 我們不加證明地引入下面的定理，雖然其證明并不十分困難。我們不加證明地引入下面的定理，雖然其證明并不十分困難。 定理定理 E為一有限集合，為為一有限集合，為E的部分子集構(gòu)成的封閉獨(dú)立系統(tǒng)。以下的部分子集構(gòu)成的封閉獨(dú)立系統(tǒng)。以下兩個(gè)條件均為兩個(gè)條件均為M=(E, y)構(gòu)成擬陣（即其上的優(yōu)化問(wèn)題可用貪婪法求解）構(gòu)成擬陣（即其上的優(yōu)化問(wèn)題可用貪婪法求解）的充分必要條件：的充分必要條件：（條件（條件2） 若若I、I均為均為A的兩個(gè)極大獨(dú)立集，則的兩個(gè)極大獨(dú)立集，

17、則|I|=|I|。AE （條件（條件1）若若I、I |I| M|，G中至少含一條路，其中中至少含一條路，其中M中的邊多于中的邊多于M中的邊，不難看出，這條路是中的邊，不難看出，這條路是G的的關(guān)于關(guān)于M的增廣路。的增廣路。 現(xiàn)在可以看出，找最大匹配的關(guān)鍵在于找增廣路。讀者不難用頂點(diǎn)標(biāo)號(hào)現(xiàn)在可以看出，找最大匹配的關(guān)鍵在于找增廣路。讀者不難用頂點(diǎn)標(biāo)號(hào)的辦法（由未蓋點(diǎn)出發(fā)），作出一個(gè)求解兩分圖匹配的增廣路算法。此的辦法（由未蓋點(diǎn)出發(fā)），作出一個(gè)求解兩分圖匹配的增廣路算法。此算法稍加改動(dòng)，還可以用于非兩分圖的情況。算法稍加改動(dòng)，還可以用于非兩分圖的情況。三、網(wǎng)絡(luò)流問(wèn)題三、網(wǎng)絡(luò)流問(wèn)題網(wǎng)絡(luò)流問(wèn)題是又一類具有

18、廣泛應(yīng)用前景的網(wǎng)絡(luò)流問(wèn)題是又一類具有廣泛應(yīng)用前景的P問(wèn)題，本節(jié)將介紹一些有關(guān)問(wèn)題，本節(jié)將介紹一些有關(guān)網(wǎng)絡(luò)流問(wèn)題的基本理論與算法。網(wǎng)絡(luò)流問(wèn)題的基本理論與算法。1、最大流問(wèn)題（、最大流問(wèn)題（MFP）邊賦值的有向圖稱為網(wǎng)絡(luò)。給定一個(gè)網(wǎng)絡(luò)，其邊賦值表示該邊的容量。最邊賦值的有向圖稱為網(wǎng)絡(luò)。給定一個(gè)網(wǎng)絡(luò)，其邊賦值表示該邊的容量。最大流問(wèn)題要求在不超過(guò)邊容量的前提下求出網(wǎng)絡(luò)中兩個(gè)指定頂點(diǎn)之間的最大流問(wèn)題要求在不超過(guò)邊容量的前提下求出網(wǎng)絡(luò)中兩個(gè)指定頂點(diǎn)之間的最大流。例如：當(dāng)網(wǎng)絡(luò)是通訊網(wǎng)時(shí)，我們可能會(huì)去求出網(wǎng)絡(luò)中兩個(gè)指定點(diǎn)間大流。例如：當(dāng)網(wǎng)絡(luò)是通訊網(wǎng)時(shí)，我們可能會(huì)去求出網(wǎng)絡(luò)中兩個(gè)指定點(diǎn)間的最大通話量；當(dāng)網(wǎng)絡(luò)是

19、城市的街道時(shí)，我們又可能會(huì)去求兩地間的最大的最大通話量；當(dāng)網(wǎng)絡(luò)是城市的街道時(shí)，我們又可能會(huì)去求兩地間的最大交通流，即單位時(shí)間內(nèi)允許通過(guò)的車輛數(shù)等等。交通流，即單位時(shí)間內(nèi)允許通過(guò)的車輛數(shù)等等。建模：建模：給定一有向圖給定一有向圖G=（V，A），），A的每一條孤（邊）（的每一條孤（邊）（i,j）上已賦一）上已賦一表示邊容量的非負(fù)整數(shù)表示邊容量的非負(fù)整數(shù)C（i,j）。并已指定）。并已指定V中的兩個(gè)頂點(diǎn)中的兩個(gè)頂點(diǎn) s、t，分別稱，分別稱它們?yōu)榘l(fā)點(diǎn)和收點(diǎn)。它們?yōu)榘l(fā)點(diǎn)和收點(diǎn)。設(shè)網(wǎng)絡(luò)中已存在一個(gè)流（不一定是最大流），記孤（設(shè)網(wǎng)絡(luò)中已存在一個(gè)流（不一定是最大流），記孤（i,j）上的流量為）上的流量為 （i,

20、j），記），記s發(fā)出的總流量（即發(fā)出的總流量（即t收到的總流量）為收到的總流量）為 ，根據(jù)平衡條件，可，根據(jù)平衡條件，可得如下的約束條件，得如下的約束條件， ，有，有i 其中是其中是 指指A中以頂點(diǎn)中以頂點(diǎn)i為起點(diǎn)的孤集，為起點(diǎn)的孤集， 是指是指A中以中以 i為終點(diǎn)的孤集為終點(diǎn)的孤集,(.1)式表示式表示s發(fā)出流為發(fā)出流為 ，t收入的流為收入的流為 ，其余各點(diǎn)只起中轉(zhuǎn)作用，其余各點(diǎn)只起中轉(zhuǎn)作用，既不增加也不消耗流量。根據(jù)邊容量限止，還應(yīng)有既不增加也不消耗流量。根據(jù)邊容量限止，還應(yīng)有 iAiA,i jC i ji jA而我們的愿望是使總流量盡可能地大。而我們的愿望是使總流量盡可能地大。即在（即在

21、（9.1）、）、(9.2)式約束下式約束下使達(dá)到最大，易見(jiàn)，這是一個(gè)線性規(guī)劃問(wèn)題的子問(wèn)題，故使達(dá)到最大，易見(jiàn)，這是一個(gè)線性規(guī)劃問(wèn)題的子問(wèn)題，故 類。類。PtivtsisivjijiAijiAiji若若若.0),(),(),(),(對(duì)于一個(gè)較為復(fù)雜的網(wǎng)絡(luò)，要想直接找出最大流是不太可能的。為了簡(jiǎn)化對(duì)于一個(gè)較為復(fù)雜的網(wǎng)絡(luò)，要想直接找出最大流是不太可能的。為了簡(jiǎn)化問(wèn)題，我們先引入一些符號(hào)。問(wèn)題，我們先引入一些符號(hào)。記記、為為的兩個(gè)不相交的子集，的兩個(gè)不相交的子集，s ，用（，）表示發(fā)，用（，）表示發(fā)點(diǎn)在，收點(diǎn)在的邊集，點(diǎn)在，收點(diǎn)在的邊集，記記，并定義如下的切割概念：，并定義如下的切割概念：,P tQ,

22、i P j Qi P j QP Qi j C P QC i j定義定義9.5 （切割）（切割） 設(shè)設(shè)是是的頂點(diǎn)集合的頂點(diǎn)集合的一個(gè)真子集，的一個(gè)真子集， 為為關(guān)于關(guān)于的補(bǔ)集。若的補(bǔ)集。若、 滿足滿足 且且 則稱則稱和和 為的一個(gè)切割。為的一個(gè)切割。PPSPtPP根據(jù)切割的定義可以看出，當(dāng)和根據(jù)切割的定義可以看出，當(dāng)和 為一切割時(shí)，如果去掉連接為一切割時(shí)，如果去掉連接和的和的邊集（邊集（， ），就切斷了由通往），就切斷了由通往t的所有通路。所以，對(duì)網(wǎng)絡(luò)的任一切的所有通路。所以，對(duì)網(wǎng)絡(luò)的任一切割（割（， ），），（， ）必為最大流的一個(gè)上界，）必為最大流的一個(gè)上界，而而 。PPPP,P PP P例

23、例9.9 網(wǎng)絡(luò)如圖網(wǎng)絡(luò)如圖9.6所示，邊（?。┥系膬蓴?shù)字分別表示邊容量及實(shí)際流所示，邊（?。┥系膬蓴?shù)字分別表示邊容量及實(shí)際流量。取，則，顯然量。取，則，顯然、 是網(wǎng)絡(luò)的是網(wǎng)絡(luò)的一個(gè)切割。對(duì)于這一切割容易算出一個(gè)切割。對(duì)于這一切割容易算出而網(wǎng)絡(luò)的流量而網(wǎng)絡(luò)的流量 。P,6,9P PC P P為了盡可能地增大網(wǎng)絡(luò)上的流量，按如下方法作出一個(gè)和為了盡可能地增大網(wǎng)絡(luò)上的流量，按如下方法作出一個(gè)和具有相同頂具有相同頂點(diǎn)并具有相同發(fā)點(diǎn)和收點(diǎn)的增廣網(wǎng)絡(luò)點(diǎn)并具有相同發(fā)點(diǎn)和收點(diǎn)的增廣網(wǎng)絡(luò) （ ） （簡(jiǎn)記（簡(jiǎn)記）。）。包含兩包含兩類邊，對(duì)中每一條邊（類邊，對(duì)中每一條邊（i，j） ： A（1）若）若 ，作正向邊（，

24、作正向邊（i，j）, 規(guī)定容量規(guī)定容量 ，即剩余容量。，即剩余容量。,i jC j i,C j iC j ij i（2）若）若 ，作反向邊（，作反向邊（j,i），）， 規(guī)定容量規(guī)定容量 事實(shí)上是邊（事實(shí)上是邊（j,i）上最多可減少的容量。）上最多可減少的容量。,0i j,Cj ij iCj i第一類邊稱為正規(guī)邊，第二類邊則稱為增廣邊。例如由圖中的流可以作第一類邊稱為正規(guī)邊，第二類邊則稱為增廣邊。例如由圖中的流可以作出其相應(yīng)的增廣網(wǎng)絡(luò)圖，其中實(shí)箭線為正規(guī)定，虛箭線為增廣邊，邊上出其相應(yīng)的增廣網(wǎng)絡(luò)圖，其中實(shí)箭線為正規(guī)定，虛箭線為增廣邊，邊上的數(shù)字為邊容量。的數(shù)字為邊容量。如果增廣網(wǎng)絡(luò)上存在著由如果

25、增廣網(wǎng)絡(luò)上存在著由st的通路的通路p（稱為原網(wǎng)絡(luò)的一條增廣路），（稱為原網(wǎng)絡(luò)的一條增廣路），記記 ，則只要在，則只要在P中的一切正規(guī)邊上增加流量中的一切正規(guī)邊上增加流量a，而在對(duì)應(yīng)，而在對(duì)應(yīng)增廣邊（增廣邊（j, i），），G的邊（的邊（i, j）上減少流量）上減少流量a，就得到，就得到G的一個(gè)由的一個(gè)由st的增的增大了流量大了流量a的更大的流。例如，從圖的更大的流。例如，從圖9.7上可以找出增廣路上可以找出增廣路，a=2。于是，圖。于是，圖9.6中的流可改進(jìn)增大為圖中的流可改進(jìn)增大為圖9.8(a)中中的流，總流量為的流，總流量為7。由于其增廣網(wǎng)絡(luò)圖。由于其增廣網(wǎng)絡(luò)圖9.8(b)中不再存在增廣路

26、，無(wú)法再中不再存在增廣路，無(wú)法再繼續(xù)增大。容易看出，若取繼續(xù)增大。容易看出，若取s出發(fā)（在增廣網(wǎng)絡(luò)上）可到達(dá)的點(diǎn)的集合出發(fā)（在增廣網(wǎng)絡(luò)上）可到達(dá)的點(diǎn)的集合為為P，則，則P=, ， =,，C（P， ）=7，而流量已達(dá)到，而流量已達(dá)到7，故此流已是最大流。故此流已是最大流。 ( , )min( , )i jPaC i jPP（1）( , )( , ), ( , )( ,)i jC i ji jP P（2） ( , )0, ( , )( , )i ji jP P故故 ，已不能再增大，（注：這是線性規(guī)劃的補(bǔ)松馳定理）。已不能再增大，（注：這是線性規(guī)劃的補(bǔ)松馳定理）。( ,)( ,)P PC P P綜上

27、所述，有下面的有關(guān)網(wǎng)絡(luò)流問(wèn)題的定理。綜上所述，有下面的有關(guān)網(wǎng)絡(luò)流問(wèn)題的定理。定理定理9.59.5 （Ford和和Fulkerson最大流最小切割定理）最大流最小切割定理） 任一由任一由s到到t的流，的流，其流量不大于任一切割的容量其流量不大于任一切割的容量C（P， ），而最大流的流量則等于最?。?，而最大流的流量則等于最小切割的容量。進(jìn)而切割的容量。進(jìn)而 為最大流且（為最大流且（P， ）為最小切割當(dāng)且僅當(dāng)：）為最小切割當(dāng)且僅當(dāng)：（1） 有有（2） 有有 。PP( , )( ,)i jP P( , )( , )i jC i j( , )( ,)i jP P( , )0i j增廣路可以通過(guò)對(duì)頂點(diǎn)標(biāo)號(hào)

28、的方法來(lái)尋找。由于邊容量均為整數(shù)，而每次增廣路可以通過(guò)對(duì)頂點(diǎn)標(biāo)號(hào)的方法來(lái)尋找。由于邊容量均為整數(shù)，而每次經(jīng)改進(jìn)，流量至少增加一，故算法總能很快求得最大流。經(jīng)改進(jìn)，流量至少增加一，故算法總能很快求得最大流。定理定理 網(wǎng)絡(luò)網(wǎng)絡(luò)G上的流是最大流的充要條件為其增廣網(wǎng)絡(luò)上不存在由上的流是最大流的充要條件為其增廣網(wǎng)絡(luò)上不存在由s到到t 的通路。的通路。證明：證明：若增廣網(wǎng)絡(luò)上存在由若增廣網(wǎng)絡(luò)上存在由s到到t的通路的通路P，則對(duì)，則對(duì)P上的正規(guī)邊（上的正規(guī)邊（i, j）增加流）增加流量量a，對(duì)，對(duì)P的增廣邊（的增廣邊（j, i）對(duì)應(yīng)）對(duì)應(yīng)G的邊（的邊（i, j）減少流量）減少流量a，即可得到一個(gè)更，即可得到

29、一個(gè)更大的可行流。若增廣網(wǎng)絡(luò)上不存在由大的可行流。若增廣網(wǎng)絡(luò)上不存在由s到到t的路，記增廣圖上的路，記增廣圖上s可達(dá)到的點(diǎn)組可達(dá)到的點(diǎn)組成的集合為成的集合為P，則對(duì)切割（，則對(duì)切割（P, ）必有：）必有：P2、最小費(fèi)用最大流問(wèn)題、最小費(fèi)用最大流問(wèn)題對(duì)于一個(gè)給定的網(wǎng)絡(luò)，由發(fā)點(diǎn)對(duì)于一個(gè)給定的網(wǎng)絡(luò)，由發(fā)點(diǎn)s到收點(diǎn)到收點(diǎn)t常常存在著多個(gè)具有相同流量的最常常存在著多個(gè)具有相同流量的最大流。如圖所示，圖中的（大流。如圖所示，圖中的（a）、（）、（b）、（）、（c）均是流量為）均是流量為7的最大流，邊的最大流，邊上的兩個(gè)數(shù)字依次為容量和邊上的實(shí)際流量。有時(shí)候，當(dāng)流流經(jīng)一條邊時(shí)上的兩個(gè)數(shù)字依次為容量和邊上的實(shí)

30、際流量。有時(shí)候，當(dāng)流流經(jīng)一條邊時(shí)需支付一定的費(fèi)用，我們不僅希望找出一個(gè)最大流，而且希望找出的最大需支付一定的費(fèi)用，我們不僅希望找出一個(gè)最大流，而且希望找出的最大流在具有相同流量的流中具有最小的總費(fèi)用，這時(shí)問(wèn)題可描述為：對(duì)有向流在具有相同流量的流中具有最小的總費(fèi)用，這時(shí)問(wèn)題可描述為：對(duì)有向圖圖G=（V，A）的每條邊（?。ǎ┑拿織l邊（弧）（i, j）給定一個(gè)邊容量）給定一個(gè)邊容量C（i, j）及一個(gè)單位）及一個(gè)單位流量費(fèi)用流量費(fèi)用l(i, j)。希望求出由。希望求出由s到到t的最大流，使得總費(fèi)用最少，即求最大流的最大流，使得總費(fèi)用最少，即求最大流*，使，使*( , )()min ( , ) (

31、, )i jALl i ji j最大流例如，在交通網(wǎng)絡(luò)中，例如，在交通網(wǎng)絡(luò)中，l(i, j)可以是可以是i, j之間的距離或運(yùn)費(fèi)。自然，在運(yùn)送之間的距離或運(yùn)費(fèi)。自然，在運(yùn)送相同數(shù)量貨物時(shí)，我們希望總距離或總運(yùn)費(fèi)最小?，F(xiàn)在，我們將以最大相同數(shù)量貨物時(shí)，我們希望總距離或總運(yùn)費(fèi)最小。現(xiàn)在，我們將以最大流問(wèn)題的增廣路算法為基礎(chǔ)，導(dǎo)出求解最小費(fèi)用最大流問(wèn)題的算法。流問(wèn)題的增廣路算法為基礎(chǔ)，導(dǎo)出求解最小費(fèi)用最大流問(wèn)題的算法。對(duì)于網(wǎng)絡(luò)上的一個(gè)現(xiàn)行流對(duì)于網(wǎng)絡(luò)上的一個(gè)現(xiàn)行流 ，作出其增廣網(wǎng)絡(luò)，作出其增廣網(wǎng)絡(luò)G( )，對(duì)，對(duì)G中的正規(guī)邊中的正規(guī)邊賦值賦值l(i, j)，對(duì)，對(duì)G中的增廣邊中的增廣邊(i, j)則賦

32、值則賦值l(i, j)。 定義定義 增廣網(wǎng)絡(luò)增廣網(wǎng)絡(luò)G上由上由s到到t的流量為零但邊流量不全為零的流稱為一個(gè)循環(huán)流。的流量為零但邊流量不全為零的流稱為一個(gè)循環(huán)流。最小費(fèi)用最大流問(wèn)題可以變換成為一個(gè)線性規(guī)劃問(wèn)題，根據(jù)線性規(guī)劃理最小費(fèi)用最大流問(wèn)題可以變換成為一個(gè)線性規(guī)劃問(wèn)題，根據(jù)線性規(guī)劃理論可以證明下面的定理：論可以證明下面的定理： 定理定理9.69.6 網(wǎng)絡(luò)中的流網(wǎng)絡(luò)中的流 是最小費(fèi)用的，當(dāng)且僅當(dāng)其增廣網(wǎng)絡(luò)是最小費(fèi)用的，當(dāng)且僅當(dāng)其增廣網(wǎng)絡(luò)G中不存在中不存在負(fù)費(fèi)用的循環(huán)流（證明略）。負(fù)費(fèi)用的循環(huán)流（證明略）。例例 圖（圖（a）給出了有向圖）給出了有向圖G上的一個(gè)可行流，其中弧上的三個(gè)數(shù)字分別為上的

33、一個(gè)可行流，其中弧上的三個(gè)數(shù)字分別為容量、單位流費(fèi)用及實(shí)際流量。圖（容量、單位流費(fèi)用及實(shí)際流量。圖（b）為相應(yīng)的增廣網(wǎng)絡(luò)，其中邊（?。橄鄳?yīng)的增廣網(wǎng)絡(luò)，其中邊（?。┥系膬蓚€(gè)數(shù)字分別為容量及單位流費(fèi)用。求此網(wǎng)絡(luò)的一個(gè)更小費(fèi)用流。上的兩個(gè)數(shù)字分別為容量及單位流費(fèi)用。求此網(wǎng)絡(luò)的一個(gè)更小費(fèi)用流。從圖（從圖（b）中可以找出一個(gè)負(fù)費(fèi)用循環(huán)流）中可以找出一個(gè)負(fù)費(fèi)用循環(huán)流s21s（其余邊流量為（其余邊流量為0），），每單位流量的總費(fèi)用為每單位流量的總費(fèi)用為5。調(diào)整此循環(huán)流上的流量，得到圖（。調(diào)整此循環(huán)流上的流量，得到圖（a）中的）中的流。原先的流總費(fèi)用為流。原先的流總費(fèi)用為17，調(diào)整后的總費(fèi)用為，調(diào)整后的總費(fèi)

34、用為12，減少值為負(fù)費(fèi)用循環(huán)，減少值為負(fù)費(fèi)用循環(huán)流的總費(fèi)用。流的總費(fèi)用。圖（圖（a）中流的增廣網(wǎng)絡(luò)（）中流的增廣網(wǎng)絡(luò)（b）中已不存在負(fù)費(fèi)用循環(huán)流，它是一個(gè)最小費(fèi)用）中已不存在負(fù)費(fèi)用循環(huán)流，它是一個(gè)最小費(fèi)用的流。的流。定理定理 設(shè)設(shè)1是網(wǎng)絡(luò)上流量為是網(wǎng)絡(luò)上流量為的最小費(fèi)用流，的最小費(fèi)用流，2是其增廣網(wǎng)絡(luò)上由是其增廣網(wǎng)絡(luò)上由s到到t的最小的最小費(fèi)用單位流增廣路，則費(fèi)用單位流增廣路，則1+2是此網(wǎng)絡(luò)流量為是此網(wǎng)絡(luò)流量為+1的最小費(fèi)用流。的最小費(fèi)用流。證明：證明：設(shè)設(shè)1+2不是流量為不是流量為+1的最小費(fèi)用流，由定理的最小費(fèi)用流，由定理6，在，在 1+ 2的增廣網(wǎng)的增廣網(wǎng)絡(luò)中必存在一負(fù)圈絡(luò)中必存在一負(fù)

35、圈C。記構(gòu)造。記構(gòu)造2的增廣路為的增廣路為P。由于。由于 1是最小費(fèi)用流，是最小費(fèi)用流， 1的增廣網(wǎng)絡(luò)中不存在負(fù)圈，故的增廣網(wǎng)絡(luò)中不存在負(fù)圈，故C中必有一邊（中必有一邊（i, j），其反向邊（），其反向邊（j, i）含）含在在P中（因?yàn)槿缛舨蝗?，中（因?yàn)槿缛舨蝗?，C不含不含P中任意邊，則中任意邊，則C將含在將含在1的增廣網(wǎng)絡(luò)中，與的增廣網(wǎng)絡(luò)中，與1為最小費(fèi)用流的假設(shè)矛盾，見(jiàn)圖為最小費(fèi)用流的假設(shè)矛盾，見(jiàn)圖9.12），但這又說(shuō)明），但這又說(shuō)明P（C（i, j）是）是S到到t的更小費(fèi)用單位流增廣路，與的更小費(fèi)用單位流增廣路，與P是最小費(fèi)用單位流增廣路的假設(shè)矛盾。是最小費(fèi)用單位流增廣路的假設(shè)矛盾。根據(jù)

36、定理及定理，求最大流的算法只需稍作變動(dòng)即根據(jù)定理及定理，求最大流的算法只需稍作變動(dòng)即可用來(lái)求解最小費(fèi)用最大流。算法可以用歸納方式可用來(lái)求解最小費(fèi)用最大流。算法可以用歸納方式給出，當(dāng)給出，當(dāng)=0時(shí)，可取時(shí)，可取=0，這顯然是，這顯然是=0的最小費(fèi)的最小費(fèi)用流。在以后逐次增大流量時(shí)，若增廣網(wǎng)絡(luò)中存在用流。在以后逐次增大流量時(shí)，若增廣網(wǎng)絡(luò)中存在著多于一條增廣路時(shí)，每次均選用其中單位流費(fèi)用著多于一條增廣路時(shí)，每次均選用其中單位流費(fèi)用最小的一條。這樣，每次得到的均為相同流量的流最小的一條。這樣，每次得到的均為相同流量的流中費(fèi)用最小的，而最后得到的即為最小費(fèi)用最大流。中費(fèi)用最小的，而最后得到的即為最小費(fèi)用

37、最大流。網(wǎng)絡(luò)流問(wèn)題的算法在解決實(shí)際問(wèn)題時(shí)常常被用到。它可用來(lái)求解運(yùn)輸問(wèn)網(wǎng)絡(luò)流問(wèn)題的算法在解決實(shí)際問(wèn)題時(shí)常常被用到。它可用來(lái)求解運(yùn)輸問(wèn)題、指派問(wèn)題及賦權(quán)兩分圖匹配問(wèn)題（等價(jià)于指派問(wèn)題），也可用來(lái)尋題、指派問(wèn)題及賦權(quán)兩分圖匹配問(wèn)題（等價(jià)于指派問(wèn)題），也可用來(lái)尋找網(wǎng)絡(luò)的瓶頸找網(wǎng)絡(luò)的瓶頸即最小切割（即最小切割（P， ）確定的邊。作為一個(gè)網(wǎng)絡(luò)流問(wèn)題）確定的邊。作為一個(gè)網(wǎng)絡(luò)流問(wèn)題的應(yīng)用實(shí)例，我們來(lái)求解例的應(yīng)用實(shí)例，我們來(lái)求解例9.7中的婚姻姻問(wèn)題：增加發(fā)點(diǎn)中的婚姻姻問(wèn)題：增加發(fā)點(diǎn)s和收點(diǎn)和收點(diǎn)t，將，將原圖的邊改為有向邊，所有邊的容量為原圖的邊改為有向邊，所有邊的容量為1。找出最大財(cái)禮數(shù)。找出最大財(cái)禮數(shù)2

38、8，以此數(shù)，以此數(shù)減每邊原有的財(cái)禮費(fèi)，并用此差為各邊的費(fèi)用，得一最小費(fèi)用最大流問(wèn)減每邊原有的財(cái)禮費(fèi)，并用此差為各邊的費(fèi)用，得一最小費(fèi)用最大流問(wèn)題（未注數(shù)字的邊費(fèi)用均為零），其網(wǎng)絡(luò)圖見(jiàn)圖題（未注數(shù)字的邊費(fèi)用均為零），其網(wǎng)絡(luò)圖見(jiàn)圖9.13。此問(wèn)題在使用三。此問(wèn)題在使用三次增廣路后可求得最佳結(jié)果。次增廣路后可求得最佳結(jié)果。 P四、最短路徑問(wèn)題四、最短路徑問(wèn)題最短路徑問(wèn)題是又一個(gè)經(jīng)常遇到的最短路徑問(wèn)題是又一個(gè)經(jīng)常遇到的P問(wèn)題，它在工藝流程的安排、管道或問(wèn)題，它在工藝流程的安排、管道或網(wǎng)絡(luò)的鋪設(shè)、設(shè)備更新等實(shí)際生產(chǎn)中常被用到，是網(wǎng)絡(luò)規(guī)劃的基本問(wèn)題之網(wǎng)絡(luò)的鋪設(shè)、設(shè)備更新等實(shí)際生產(chǎn)中常被用到，是網(wǎng)絡(luò)規(guī)劃的基

39、本問(wèn)題之一。顧名思義，最短路徑求的是以下問(wèn)題：給定一個(gè)網(wǎng)絡(luò)，如何求出網(wǎng)絡(luò)一。顧名思義，最短路徑求的是以下問(wèn)題：給定一個(gè)網(wǎng)絡(luò)，如何求出網(wǎng)絡(luò)中指定兩點(diǎn)間總距離（或總費(fèi)用）最小的路徑。中指定兩點(diǎn)間總距離（或總費(fèi)用）最小的路徑。例例 給定圖中的網(wǎng)絡(luò)，邊上的數(shù)字為兩頂點(diǎn)間的距離（或費(fèi)用），求由給定圖中的網(wǎng)絡(luò)，邊上的數(shù)字為兩頂點(diǎn)間的距離（或費(fèi)用），求由A到到E的最短路徑。的最短路徑。求解最短路徑問(wèn)題的求解最短路徑問(wèn)題的Dijkstra算法體現(xiàn)了動(dòng)態(tài)規(guī)劃算法的基本思想。若點(diǎn)算法體現(xiàn)了動(dòng)態(tài)規(guī)劃算法的基本思想。若點(diǎn)P在在A到到E的最短路上，則的最短路上，則P到到E的最短路徑必整個(gè)地包含在的最短路徑必整個(gè)地包含在

40、A到到E的最短路的最短路徑上。因?yàn)?，若不然，將由徑上。因?yàn)?，若不然，將由P到到E的最短路徑導(dǎo)出的最短路徑導(dǎo)出A到到E的更短路徑，從而的更短路徑，從而導(dǎo)出矛盾。算法既可以通過(guò)對(duì)頂點(diǎn)逐次標(biāo)號(hào)來(lái)實(shí)現(xiàn)，也可以通過(guò)矩陣運(yùn)導(dǎo)出矛盾。算法既可以通過(guò)對(duì)頂點(diǎn)逐次標(biāo)號(hào)來(lái)實(shí)現(xiàn)，也可以通過(guò)矩陣運(yùn)算進(jìn)行。在使用標(biāo)號(hào)法時(shí)，既可以從起點(diǎn)開(kāi)始標(biāo)，也可以從終點(diǎn)開(kāi)始標(biāo)。算進(jìn)行。在使用標(biāo)號(hào)法時(shí)，既可以從起點(diǎn)開(kāi)始標(biāo)，也可以從終點(diǎn)開(kāi)始標(biāo)。（兩者目的略有不同）對(duì)例中的網(wǎng)絡(luò)，如從起點(diǎn)（兩者目的略有不同）對(duì)例中的網(wǎng)絡(luò)，如從起點(diǎn)A開(kāi)始標(biāo)導(dǎo)，先在開(kāi)始標(biāo)導(dǎo)，先在A點(diǎn)標(biāo)點(diǎn)標(biāo)上上0。再找出離。再找出離A最近的點(diǎn)最近的點(diǎn)B3，標(biāo)上，標(biāo)上A到到B3的最短

41、矩離的最短矩離1并記錄下并記錄下A點(diǎn)（表點(diǎn)（表明由明由A而來(lái)）。一般，在標(biāo)新頂點(diǎn)時(shí)，先找出離已標(biāo)號(hào)頂點(diǎn)最近的頂點(diǎn)。而來(lái)）。一般，在標(biāo)新頂點(diǎn)時(shí)，先找出離已標(biāo)號(hào)頂點(diǎn)最近的頂點(diǎn)。比較各已標(biāo)號(hào)頂點(diǎn)（與擬標(biāo)號(hào)頂點(diǎn)有邊相連）的標(biāo)號(hào)與它到擬標(biāo)號(hào)頂點(diǎn)比較各已標(biāo)號(hào)頂點(diǎn)（與擬標(biāo)號(hào)頂點(diǎn)有邊相連）的標(biāo)號(hào)與它到擬標(biāo)號(hào)頂點(diǎn)距離之和，找出各種中最小者作為新頂點(diǎn)的標(biāo)號(hào)，并記錄下其前的已標(biāo)距離之和，找出各種中最小者作為新頂點(diǎn)的標(biāo)號(hào)，并記錄下其前的已標(biāo)號(hào)頂點(diǎn)。直到擬到達(dá)的終點(diǎn)已標(biāo)號(hào)為止。例如，圖指出，號(hào)頂點(diǎn)。直到擬到達(dá)的終點(diǎn)已標(biāo)號(hào)為止。例如，圖指出，A到到E的最短路的最短路徑為徑為AB2C1D1E，最短距離為，最短距離為19。

42、容易看出，算法是多項(xiàng)式時(shí)間的。在標(biāo)每一頂點(diǎn)時(shí)，最多作了容易看出，算法是多項(xiàng)式時(shí)間的。在標(biāo)每一頂點(diǎn)時(shí)，最多作了| V |次運(yùn)算。次運(yùn)算。算法進(jìn)行中，事實(shí)上在構(gòu)造一棵由已標(biāo)號(hào)頂點(diǎn)及它們與其前行點(diǎn)間的邊算法進(jìn)行中，事實(shí)上在構(gòu)造一棵由已標(biāo)號(hào)頂點(diǎn)及它們與其前行點(diǎn)間的邊組成的樹(shù)。每一頂點(diǎn)均不可能重復(fù)標(biāo)號(hào)，故總計(jì)算量的一個(gè)上界為組成的樹(shù)。每一頂點(diǎn)均不可能重復(fù)標(biāo)號(hào)，故總計(jì)算量的一個(gè)上界為O（|V|2）。）。按一般習(xí)慣，動(dòng)態(tài)規(guī)劃算法常按逆順序進(jìn)行。圖給出了按向前標(biāo)號(hào)的結(jié)果，按一般習(xí)慣，動(dòng)態(tài)規(guī)劃算法常按逆順序進(jìn)行。圖給出了按向前標(biāo)號(hào)的結(jié)果，最短路徑已用雙線劃出。最短路徑已用雙線劃出。 從圖中可看出從圖中可看出A到

43、各點(diǎn)的距離及最短路徑，而從圖中則可看出由各點(diǎn)到到各點(diǎn)的距離及最短路徑，而從圖中則可看出由各點(diǎn)到E點(diǎn)的距離及最短路徑，這是兩者的區(qū)別。點(diǎn)的距離及最短路徑，這是兩者的區(qū)別。 讀者不難給出一般問(wèn)題的計(jì)算步驟，也不難推廣得到能求出任意兩點(diǎn)間最讀者不難給出一般問(wèn)題的計(jì)算步驟，也不難推廣得到能求出任意兩點(diǎn)間最短路徑的算法。短路徑的算法。作為最短路徑問(wèn)題的一個(gè)應(yīng)用實(shí)例，我們來(lái)研究下面的設(shè)備更新問(wèn)題：作為最短路徑問(wèn)題的一個(gè)應(yīng)用實(shí)例，我們來(lái)研究下面的設(shè)備更新問(wèn)題：例例 某單位使用一種設(shè)備。該設(shè)備在某單位使用一種設(shè)備。該設(shè)備在5年內(nèi)的預(yù)期價(jià)格見(jiàn)表，使用不同年年內(nèi)的預(yù)期價(jià)格見(jiàn)表，使用不同年數(shù)的設(shè)備的年維修費(fèi)用見(jiàn)表數(shù)

44、的設(shè)備的年維修費(fèi)用見(jiàn)表9.2 ?，F(xiàn)準(zhǔn)備制訂一個(gè)五年內(nèi)的設(shè)備更新計(jì)劃，。現(xiàn)準(zhǔn)備制訂一個(gè)五年內(nèi)的設(shè)備更新計(jì)劃，使五年內(nèi)支付的設(shè)備購(gòu)置費(fèi)用及總維修費(fèi)用最少。使五年內(nèi)支付的設(shè)備購(gòu)置費(fèi)用及總維修費(fèi)用最少。這顯然是一個(gè)十分有意義的實(shí)際問(wèn)題，即使作為個(gè)人，也會(huì)經(jīng)常遇到更這顯然是一個(gè)十分有意義的實(shí)際問(wèn)題，即使作為個(gè)人，也會(huì)經(jīng)常遇到更換交通工具、家用電器等設(shè)備更新問(wèn)題的實(shí)例。當(dāng)然，作為一般情況，換交通工具、家用電器等設(shè)備更新問(wèn)題的實(shí)例。當(dāng)然，作為一般情況，還可能要考慮殘值，如購(gòu)買了新車，舊車可以折價(jià)處理，回收資金與已還可能要考慮殘值，如購(gòu)買了新車，舊車可以折價(jià)處理，回收資金與已使用年數(shù)有關(guān)。使用年數(shù)有關(guān)。解：解

45、：作有向圖圖，圖中點(diǎn)作有向圖圖，圖中點(diǎn)i表示第表示第i年初（或第年初（或第i1）年末），弧（）年末），弧（i, j）上的數(shù)字表示第上的數(shù)字表示第i年初購(gòu)買設(shè)備到第年初購(gòu)買設(shè)備到第j年初更換，在該段時(shí)間內(nèi)的總費(fèi)用。年初更換，在該段時(shí)間內(nèi)的總費(fèi)用。例如，?。ɡ纾。?，）上的數(shù)）上的數(shù)68表示第一年初購(gòu)買設(shè)備到表示第一年初購(gòu)買設(shè)備到5年后的第六年年后的第六年初更換，需支付購(gòu)設(shè)備費(fèi)初更換，需支付購(gòu)設(shè)備費(fèi)10萬(wàn)元及各年維修費(fèi)萬(wàn)元及各年維修費(fèi) 58 萬(wàn)元，共計(jì)萬(wàn)元，共計(jì)68萬(wàn)元。萬(wàn)元。問(wèn)題化為求由頂點(diǎn)問(wèn)題化為求由頂點(diǎn)到頂點(diǎn)到頂點(diǎn)的最短路。的最短路。容易看出，作出容易看出，作出n年設(shè)備更新問(wèn)題的有向圖將問(wèn)

46、題化為最短路徑問(wèn)題大約年設(shè)備更新問(wèn)題的有向圖將問(wèn)題化為最短路徑問(wèn)題大約需要需要O(n2)計(jì)算量，其后要求求解的最短路徑問(wèn)題的計(jì)算量也是計(jì)算量，其后要求求解的最短路徑問(wèn)題的計(jì)算量也是O(n2)，故，故設(shè)備更新問(wèn)題可在設(shè)備更新問(wèn)題可在O(n2)時(shí)間內(nèi)求解。時(shí)間內(nèi)求解。表表表表第i年12345價(jià)格（萬(wàn)年）1010111213已使用年數(shù)01234（萬(wàn)年）48111520五、歐拉圈與最短郵路問(wèn)題五、歐拉圈與最短郵路問(wèn)題歐拉圈問(wèn)題起源于著名的七橋問(wèn)題。給定一個(gè)無(wú)向圖歐拉圈問(wèn)題起源于著名的七橋問(wèn)題。給定一個(gè)無(wú)向圖G=（V，E），問(wèn)能），問(wèn)能否由一個(gè)頂點(diǎn)出發(fā)，經(jīng)且僅經(jīng)過(guò)每條邊一次并返回原出發(fā)頂點(diǎn)。如果能夠，否

47、由一個(gè)頂點(diǎn)出發(fā)，經(jīng)且僅經(jīng)過(guò)每條邊一次并返回原出發(fā)頂點(diǎn)。如果能夠，則每一個(gè)這樣的圈被稱為圖則每一個(gè)這樣的圈被稱為圖G的歐拉圈，而圖的歐拉圈，而圖G則被稱為是一個(gè)歐拉圖。則被稱為是一個(gè)歐拉圖。顯然，圖顯然，圖G為歐拉圖的充要條件是它可以被一筆畫出且首尾相連（當(dāng)首尾為歐拉圖的充要條件是它可以被一筆畫出且首尾相連（當(dāng)首尾不能相連時(shí)則被稱為歐拉路）。由此，立即可得出下面的定理：不能相連時(shí)則被稱為歐拉路）。由此，立即可得出下面的定理：定理定理 G為為 歐拉圖的充要條件是：歐拉圖的充要條件是：G是連通的且是連通的且G的每一個(gè)頂點(diǎn)都與偶數(shù)的每一個(gè)頂點(diǎn)都與偶數(shù)條件相關(guān)聯(lián)。條件相關(guān)聯(lián)。把關(guān)聯(lián)偶數(shù)條邊的頂點(diǎn)稱為偶頂

48、點(diǎn)，把關(guān)聯(lián)奇數(shù)條邊的頂點(diǎn)稱為奇頂點(diǎn)，把關(guān)聯(lián)偶數(shù)條邊的頂點(diǎn)稱為偶頂點(diǎn)，把關(guān)聯(lián)奇數(shù)條邊的頂點(diǎn)稱為奇頂點(diǎn)，則容易看出奇頂點(diǎn)的個(gè)數(shù)必為偶數(shù)個(gè)（因?yàn)槊恳还P畫都產(chǎn)生一個(gè)起點(diǎn)與則容易看出奇頂點(diǎn)的個(gè)數(shù)必為偶數(shù)個(gè)（因?yàn)槊恳还P畫都產(chǎn)生一個(gè)起點(diǎn)與一個(gè)終點(diǎn)），又易得出一個(gè)終點(diǎn)），又易得出定理定理 G為歐拉路的充要條件為：為歐拉路的充要條件為：G是連通的且奇頂點(diǎn)的個(gè)數(shù)為是連通的且奇頂點(diǎn)的個(gè)數(shù)為2。綜合定理和定理可知，綜合定理和定理可知，G可一筆畫出的充要條件為可一筆畫出的充要條件為G是連通的且奇頂點(diǎn)的是連通的且奇頂點(diǎn)的個(gè)數(shù)為個(gè)數(shù)為0或或2，當(dāng)奇頂點(diǎn)個(gè)數(shù)為零時(shí)，尚可設(shè)法使起點(diǎn)和終點(diǎn)相重。下面的，當(dāng)奇頂點(diǎn)個(gè)數(shù)為零時(shí)，尚可設(shè)

49、法使起點(diǎn)和終點(diǎn)相重。下面的圖（圖（a）為歐拉圈，而圖（）為歐拉圈，而圖（b）則為歐拉路，后者雖可一筆畫出，但必須以）則為歐拉路，后者雖可一筆畫出，但必須以一個(gè)奇頂點(diǎn)為起點(diǎn)，以另一個(gè)奇頂為終點(diǎn)。一個(gè)奇頂點(diǎn)為起點(diǎn)，以另一個(gè)奇頂為終點(diǎn)。圖的連通性可以十分容易地用標(biāo)號(hào)算法加以檢驗(yàn)。而圖的奇頂點(diǎn)數(shù)又可通圖的連通性可以十分容易地用標(biāo)號(hào)算法加以檢驗(yàn)。而圖的奇頂點(diǎn)數(shù)又可通過(guò)對(duì)其頂點(diǎn)一一檢測(cè)而求得。容易看出總計(jì)算量是多頂式時(shí)間的，故歐拉過(guò)對(duì)其頂點(diǎn)一一檢測(cè)而求得。容易看出總計(jì)算量是多頂式時(shí)間的，故歐拉圈問(wèn)題和歐拉路問(wèn)題均是十分簡(jiǎn)單的圈問(wèn)題和歐拉路問(wèn)題均是十分簡(jiǎn)單的P問(wèn)題，從而，等價(jià)地，一筆畫問(wèn)題問(wèn)題，從而，等價(jià)地

50、，一筆畫問(wèn)題也可十分容易地求解：若圖也可十分容易地求解：若圖G是歐拉圖，則從任一頂點(diǎn)出發(fā)均可將它一筆是歐拉圖，則從任一頂點(diǎn)出發(fā)均可將它一筆畫出；若圖畫出；若圖G是歐拉路，則由一奇頂點(diǎn)出發(fā)，一一經(jīng)偶頂點(diǎn)地走過(guò)各條邊，是歐拉路，則由一奇頂點(diǎn)出發(fā)，一一經(jīng)偶頂點(diǎn)地走過(guò)各條邊，最后到達(dá)另一奇頂點(diǎn)，即可將最后到達(dá)另一奇頂點(diǎn)，即可將G一筆畫出；否則一筆畫出；否則G不能一筆畫出，（當(dāng)然，不能一筆畫出，（當(dāng)然，如何走法仍需規(guī)劃一下）。如何走法仍需規(guī)劃一下）。 與歐拉圖有較大聯(lián)系的另一有名的與歐拉圖有較大聯(lián)系的另一有名的P問(wèn)題是無(wú)向圖上的中國(guó)郵路問(wèn)題。給問(wèn)題是無(wú)向圖上的中國(guó)郵路問(wèn)題。給定一個(gè)無(wú)向圖，它的每一條邊上

51、都賦有一個(gè)表示該邊長(zhǎng)度（或費(fèi)用）的權(quán)。定一個(gè)無(wú)向圖，它的每一條邊上都賦有一個(gè)表示該邊長(zhǎng)度（或費(fèi)用）的權(quán)。要求從一指定頂點(diǎn)出發(fā)，至少經(jīng)過(guò)每一條邊一次最后返回原出發(fā)點(diǎn)，并使要求從一指定頂點(diǎn)出發(fā)，至少經(jīng)過(guò)每一條邊一次最后返回原出發(fā)點(diǎn)，并使經(jīng)過(guò)邊的總長(zhǎng)度最小。其中如重復(fù)走過(guò)某些邊，則邊長(zhǎng)應(yīng)重復(fù)計(jì)算，重復(fù)經(jīng)過(guò)邊的總長(zhǎng)度最小。其中如重復(fù)走過(guò)某些邊，則邊長(zhǎng)應(yīng)重復(fù)計(jì)算，重復(fù)幾次計(jì)算幾次。一個(gè)由郵局出發(fā)去各街道送信最后返回郵局的郵遞員遇到幾次計(jì)算幾次。一個(gè)由郵局出發(fā)去各街道送信最后返回郵局的郵遞員遇到的問(wèn)題就是一個(gè)中國(guó)郵路問(wèn)題。的問(wèn)題就是一個(gè)中國(guó)郵路問(wèn)題。無(wú)向圖上的中國(guó)郵路問(wèn)題也不難解決。若無(wú)向圖無(wú)向圖上的中國(guó)

52、郵路問(wèn)題也不難解決。若無(wú)向圖G是歐拉圖，則任一歐拉是歐拉圖，則任一歐拉圖都提供了一條最佳郵路。若圖都提供了一條最佳郵路。若G不是歐拉圖，如前所說(shuō)，圖中的奇頂點(diǎn)數(shù)不是歐拉圖，如前所說(shuō)，圖中的奇頂點(diǎn)數(shù)必為偶數(shù)。然后，求出任意兩個(gè)奇頂點(diǎn)之間的最短路徑及最短矩離最短必為偶數(shù)。然后，求出任意兩個(gè)奇頂點(diǎn)之間的最短路徑及最短矩離最短路徑長(zhǎng)度），再解一個(gè)奇頂點(diǎn)之間的最小權(quán)匹配（或指派問(wèn)題，注意這路徑長(zhǎng)度），再解一個(gè)奇頂點(diǎn)之間的最小權(quán)匹配（或指派問(wèn)題，注意這里的距離矩陣是對(duì)稱的）。將各匹配奇點(diǎn)間的最短路徑加入里的距離矩陣是對(duì)稱的）。將各匹配奇點(diǎn)間的最短路徑加入G中，就得到中，就得到了最知路問(wèn)題的解，我們將在中考

53、察一個(gè)這類問(wèn)題的實(shí)例。了最知路問(wèn)題的解，我們將在中考察一個(gè)這類問(wèn)題的實(shí)例。 在本節(jié)中，我們例舉了幾個(gè)較為典型而又時(shí)常遇到的在本節(jié)中，我們例舉了幾個(gè)較為典型而又時(shí)常遇到的P問(wèn)題。由于事實(shí)上問(wèn)題。由于事實(shí)上存在著無(wú)窮多個(gè)存在著無(wú)窮多個(gè)P問(wèn)題，而且即使某問(wèn)題是問(wèn)題，而且即使某問(wèn)題是NP完全的，它的許多特殊條完全的，它的許多特殊條件下的子問(wèn)題也仍然可以是多項(xiàng)式時(shí)間可解的，因而我們不可能對(duì)件下的子問(wèn)題也仍然可以是多項(xiàng)式時(shí)間可解的，因而我們不可能對(duì)P類作類作一完整的介紹。如果本章內(nèi)容能起到拋磚引玉的作用，使讀者看到一些一完整的介紹。如果本章內(nèi)容能起到拋磚引玉的作用，使讀者看到一些P問(wèn)題所具有的某些特征及構(gòu)

54、造算法上的某些技巧，那么，我們的目的也問(wèn)題所具有的某些特征及構(gòu)造算法上的某些技巧，那么，我們的目的也就達(dá)到了。從上述就達(dá)到了。從上述P問(wèn)題（包括第八章中的線性規(guī)劃、運(yùn)輸問(wèn)題及指派問(wèn)問(wèn)題（包括第八章中的線性規(guī)劃、運(yùn)輸問(wèn)題及指派問(wèn)題）可以看出，它們都可以用某種逐次改進(jìn)的方法來(lái)求解。每次改進(jìn)中題）可以看出，它們都可以用某種逐次改進(jìn)的方法來(lái)求解。每次改進(jìn)中的計(jì)算量是多項(xiàng)式界的，改進(jìn)的次數(shù)也是多項(xiàng)式界的。線性規(guī)劃的單純的計(jì)算量是多項(xiàng)式界的，改進(jìn)的次數(shù)也是多項(xiàng)式界的。線性規(guī)劃的單純形法例外，改進(jìn)次數(shù)可能達(dá)到指數(shù)次。但即使是線性規(guī)劃問(wèn)題，也已經(jīng)形法例外，改進(jìn)次數(shù)可能達(dá)到指數(shù)次。但即使是線性規(guī)劃問(wèn)題，也已經(jīng)找

55、到了具有這種特性的算法，如橢球算法、卡馬卡算法，雖然其結(jié)構(gòu)是找到了具有這種特性的算法，如橢球算法、卡馬卡算法，雖然其結(jié)構(gòu)是相當(dāng)復(fù)雜的，但計(jì)算量卻是多項(xiàng)式時(shí)間的。相當(dāng)復(fù)雜的，但計(jì)算量卻是多項(xiàng)式時(shí)間的。最后，我們還想強(qiáng)調(diào)幾點(diǎn)：最后，我們還想強(qiáng)調(diào)幾點(diǎn)：1、許多表面有點(diǎn)相象的問(wèn)題事實(shí)上可能具有完全不同的計(jì)算復(fù)雜性。、許多表面有點(diǎn)相象的問(wèn)題事實(shí)上可能具有完全不同的計(jì)算復(fù)雜性。 這樣的例子舉不勝舉，我們略舉一、二，以提醒讀者注意。這樣的例子舉不勝舉，我們略舉一、二，以提醒讀者注意。（1）最短路徑問(wèn)題是）最短路徑問(wèn)題是P問(wèn)題，而由一點(diǎn)出發(fā)到達(dá)每一頂點(diǎn)一次（不必返回問(wèn)題，而由一點(diǎn)出發(fā)到達(dá)每一頂點(diǎn)一次（不必返回

56、原點(diǎn)）的哈密頓路問(wèn)題及由一頂點(diǎn)出發(fā)經(jīng)所有頂點(diǎn)一次到達(dá)另一頂點(diǎn)的最原點(diǎn)）的哈密頓路問(wèn)題及由一頂點(diǎn)出發(fā)經(jīng)所有頂點(diǎn)一次到達(dá)另一頂點(diǎn)的最短路徑問(wèn)題短路徑問(wèn)題流浪的旅行商問(wèn)題（流浪的旅行商問(wèn)題（WTSP）均是）均是NP完全的。這里只增加完全的。這里只增加了每個(gè)頂點(diǎn)都要去一次的要求，但問(wèn)題發(fā)生了質(zhì)的變化，由了每個(gè)頂點(diǎn)都要去一次的要求，但問(wèn)題發(fā)生了質(zhì)的變化，由P問(wèn)題變成了問(wèn)題變成了NP完全問(wèn)題。完全問(wèn)題。（2）指派問(wèn)題與）指派問(wèn)題與TSP也有相似之處，前者求一置換而使目標(biāo)值最小，后者也有相似之處，前者求一置換而使目標(biāo)值最小，后者求一循環(huán)置換（不包含子圈）而使目標(biāo)值最小。前者是求一循環(huán)置換（不包含子圈）而使目

57、標(biāo)值最小。前者是P問(wèn)題，而后者則是問(wèn)題，而后者則是NP完全的。完全的。（3）歐拉圈問(wèn)題求由一頂點(diǎn)出發(fā)經(jīng)且僅經(jīng)過(guò)每邊一次回到原頂點(diǎn)的圈，而）歐拉圈問(wèn)題求由一頂點(diǎn)出發(fā)經(jīng)且僅經(jīng)過(guò)每邊一次回到原頂點(diǎn)的圈，而TSP則求由一頂點(diǎn)出發(fā)經(jīng)且僅經(jīng)過(guò)每個(gè)頂點(diǎn)一次返回原頂點(diǎn)的圈。前者是十則求由一頂點(diǎn)出發(fā)經(jīng)且僅經(jīng)過(guò)每個(gè)頂點(diǎn)一次返回原頂點(diǎn)的圈。前者是十分容易的分容易的P問(wèn)題，而后者是極其困難的問(wèn)題，而后者是極其困難的NP完全問(wèn)題，迄今還沒(méi)有求解它的較完全問(wèn)題，迄今還沒(méi)有求解它的較好算法。好算法。（4）線性規(guī)劃問(wèn)題、運(yùn)輸問(wèn)題及指派問(wèn)題均為）線性規(guī)劃問(wèn)題、運(yùn)輸問(wèn)題及指派問(wèn)題均為P問(wèn)題，但相應(yīng)的整數(shù)線性問(wèn)題，但相應(yīng)的整數(shù)線性

58、規(guī)劃及規(guī)劃及01規(guī)劃均為規(guī)劃均為NP完全的。完全的。 （5）無(wú)向圖中國(guó)郵路問(wèn)題是）無(wú)向圖中國(guó)郵路問(wèn)題是P問(wèn)題，而有向圖中中國(guó)郵路問(wèn)題則是問(wèn)題，而有向圖中中國(guó)郵路問(wèn)題則是NP完完全的，（容易看出，會(huì)解有向圖上的某問(wèn)題必也會(huì)解無(wú)向圖上的相同問(wèn)題，全的，（容易看出，會(huì)解有向圖上的某問(wèn)題必也會(huì)解無(wú)向圖上的相同問(wèn)題，但反之不真）。但反之不真）。 2、求最小的問(wèn)題是、求最小的問(wèn)題是P問(wèn)題，求最大的問(wèn)題可以是問(wèn)題，求最大的問(wèn)題可以是NP完全的，這樣的例子完全的，這樣的例子也不少。例如，最短路徑問(wèn)題是也不少。例如，最短路徑問(wèn)題是P問(wèn)題，而最長(zhǎng)簡(jiǎn)單路徑（不含圈的路徑）問(wèn)題，而最長(zhǎng)簡(jiǎn)單路徑（不含圈的路徑）問(wèn)題卻是

59、問(wèn)題卻是NP完全的。如若不然，我們可以利用它的有效算法如下構(gòu)造出完全的。如若不然，我們可以利用它的有效算法如下構(gòu)造出哈密頓問(wèn)題的有效算：令圖哈密頓問(wèn)題的有效算：令圖G=（V，E）的所有邊的權(quán)均為）的所有邊的權(quán)均為1，以一端點(diǎn)，以一端點(diǎn)為起點(diǎn)求到其余各頂點(diǎn)的最長(zhǎng)簡(jiǎn)單路徑。由于簡(jiǎn)單路徑不含圈，所有頂點(diǎn)為起點(diǎn)求到其余各頂點(diǎn)的最長(zhǎng)簡(jiǎn)單路徑。由于簡(jiǎn)單路徑不含圈，所有頂點(diǎn)均不會(huì)重復(fù)到達(dá)，故均不會(huì)重復(fù)到達(dá)，故G有哈密頓路當(dāng)且僅當(dāng)存在一起點(diǎn)及一終點(diǎn)，其最長(zhǎng)有哈密頓路當(dāng)且僅當(dāng)存在一起點(diǎn)及一終點(diǎn)，其最長(zhǎng)簡(jiǎn)單路徑為簡(jiǎn)單路徑為| V |1。由于哈密頓路問(wèn)題是。由于哈密頓路問(wèn)題是NP 完全的，故最長(zhǎng)簡(jiǎn)單路徑問(wèn)完全的，故

60、最長(zhǎng)簡(jiǎn)單路徑問(wèn)題的有效算法不可能存在，除非題的有效算法不可能存在，除非P=NP。所以，如果你想設(shè)計(jì)一個(gè)求圖上。所以，如果你想設(shè)計(jì)一個(gè)求圖上兩點(diǎn)間的最長(zhǎng)簡(jiǎn)單路徑的有效算法，不管你是多么努力，最終必將以失敗兩點(diǎn)間的最長(zhǎng)簡(jiǎn)單路徑的有效算法，不管你是多么努力，最終必將以失敗告終。又譬如，網(wǎng)絡(luò)流中的最大流問(wèn)題是告終。又譬如，網(wǎng)絡(luò)流中的最大流問(wèn)題是P問(wèn)題。相應(yīng)地，最小切割問(wèn)題問(wèn)題。相應(yīng)地，最小切割問(wèn)題也是也是P問(wèn)題（它是最大流問(wèn)題的對(duì)偶問(wèn)題，見(jiàn)線性規(guī)劃的對(duì)偶理論）。但問(wèn)題（它是最大流問(wèn)題的對(duì)偶問(wèn)題，見(jiàn)線性規(guī)劃的對(duì)偶理論）。但可以證明，最大切割問(wèn)題卻是可以證明，最大切割問(wèn)題卻是NP完全的。完全的?？傊谘?/p>