【正文】 a~=0)amp。b39。result=[]。 v1=data(1,flag)。 else index(find(index==v2))=v1。5 匹配問題定義 若，與無公共端點(diǎn)（），則稱為圖的一個(gè)對(duì)集；中的一條邊的兩個(gè)端點(diǎn)叫做在對(duì)集中相配；中的端點(diǎn)稱為被許配；中每個(gè)頂點(diǎn)皆被許配時(shí)，稱為完美對(duì)集；中已無使的對(duì)集，則稱為最大對(duì)集；若中有一軌，其邊交替地在對(duì)集內(nèi)外出現(xiàn)，則稱此軌為的交錯(cuò)軌，交錯(cuò)軌的起止頂點(diǎn)都未被許配時(shí)，此交錯(cuò)軌稱為可增廣軌。由上述定理可以得出：推論1：若是（正則2分圖，則有完美對(duì)集。人員分派問題：工作人員去做件工作，每人適合做其中一件或幾件，問能否每人都有一份適合的工作？如果不能，最多幾人可以有適合的工作？這個(gè)問題的數(shù)學(xué)模型是：是二分圖，頂點(diǎn)集劃分為，當(dāng)且僅當(dāng)適合做工作時(shí)，求中的最大對(duì)集。（iii）若，停止，無完美對(duì)集；否則取。這個(gè)問題的數(shù)學(xué)模型是：在人員分派問題的模型中，圖的每邊加了權(quán)，表示干工作的效益，求加權(quán)圖上的權(quán)最大的完美對(duì)集。令，稱以為邊集的的生成子圖為相等子圖，記作。KuhnMunkres算法（i）選定初始可行頂點(diǎn)標(biāo)號(hào)，確定，在中選取一個(gè)對(duì)集。其中是中的相鄰頂點(diǎn)集。定理7 （i）是Euler圖的充分必要條件是連通且每頂點(diǎn)皆偶次。直觀地講，Hamilton圖就是從一頂點(diǎn)出發(fā)每頂點(diǎn)恰通過一次能回到出發(fā)點(diǎn)的那種圖，即不重復(fù)地行遍所有的頂點(diǎn)再回到出發(fā)點(diǎn)。(所謂割邊是一條刪除后使連通圖不再連通的邊)。顯然，若此連通賦權(quán)圖是Euler圖，則可用Fleury算法求Euler回路，此回路即為所求。（iii）構(gòu)造完全賦權(quán)圖，以為頂點(diǎn)集，以為邊的權(quán)。（vii）在（vi）中得的圖上求Euler回路即為中國郵遞員問題的解。用圖論的術(shù)語說，就是在一個(gè)賦權(quán)完全圖中，找出一個(gè)有最小權(quán)的Hamilton圈。一個(gè)可行的辦法是首先求一個(gè)Hamilton圈，然后適當(dāng)修改以得到具有較小權(quán)的另一個(gè)Hamilton圈。若，則以代替，叫做的改良圈。這個(gè)算法的優(yōu)劣程度有時(shí)能用Kruskal算法加以說明。這里介紹的方法已被進(jìn)一步發(fā)展。a(1,4)=21。a(2,4)=57。a(3,5)=68。a(5,6)=13。L=length(c1)。 c1(m+1:n)=c1(n:1:m+1)。sum=sum1。 for m=1:L3 for n=m+2:L1 if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))... a(c1(m),c1(m+1))+a(c1(n),c1(n+1)) flag=1。endif sum1sum sum=sum1。 由于我們只討論為有限集合的情況，所以對(duì)于弧上的權(quán)函數(shù)和頂點(diǎn)上的權(quán)函數(shù)，可以直接用所有孤上對(duì)應(yīng)的權(quán)組成的有限維向量表示，因此有時(shí)直接稱為權(quán)向量，或簡稱權(quán)。下面我們給出嚴(yán)格定義。 可見，當(dāng)時(shí)，表示有個(gè)單位的流量從該項(xiàng)點(diǎn)流出，因此頂點(diǎn)稱為供應(yīng)點(diǎn)（supply node）或源（source），有時(shí)也形象地稱為起始點(diǎn)或發(fā)點(diǎn)等；當(dāng)時(shí)，表示有個(gè)單位的流量流入該點(diǎn)（或說被該頂點(diǎn)吸收），因此頂點(diǎn)稱為需求點(diǎn)（demand node）或匯（sink），有時(shí)也形象地稱為終止點(diǎn)或收點(diǎn)等；當(dāng)時(shí)，頂點(diǎn)稱為轉(zhuǎn)運(yùn)點(diǎn)（transshipment node）或平衡點(diǎn)、中間點(diǎn)等。此時(shí)，相應(yīng)的容量約束（2）為 。如果網(wǎng)絡(luò)中存在可行流，此時(shí)稱流的流量（或流值，flow value）為（根據(jù)（3），它自然也等于），通常記為或，即 。也就是說，當(dāng)我們解決了最大流問題以后，對(duì)于在流量給定的網(wǎng)絡(luò)中尋找可行流的問題，通常也就可以解決了。最大流問題是一個(gè)特殊的線性規(guī)劃問題。（ii）用一條容量為的弧把連接到中的每個(gè)頂點(diǎn)。反之，中的流在的弧集上的限制就是中具有相同值的流。在網(wǎng)絡(luò)中，從到的軌上，若對(duì)所有的前向弧都有，對(duì)所有的后向弧恒有，則稱這條軌為從到的關(guān)于的可增廣軌。用標(biāo)號(hào)法尋求網(wǎng)絡(luò)中最大流的基本思想是尋找可增廣軌，使網(wǎng)絡(luò)的流量得到增加，直到最大為止?？傊?，網(wǎng)絡(luò)中可增廣軌的存在是有意義的，因?yàn)檫@意味著不是最大流。定理9 是最大流，是容量最小的割的充要條件是。和中的流以一個(gè)簡單的方式相互對(duì)應(yīng)。 單源和單匯運(yùn)輸網(wǎng)絡(luò)實(shí)際問題往往是多源多匯網(wǎng)絡(luò)，為了計(jì)算的規(guī)格化，可將多源多匯網(wǎng)絡(luò)化成單源單匯網(wǎng)絡(luò)。定理8（整流定理） 最大流問題所對(duì)應(yīng)的約束矩陣是全幺模矩陣。最大流問題（maximum flow problem）就是在中找到流值最大的可行流（即最大流）。如果某條弧上的流量等于其容量（），則稱該弧為飽和?。╯aturated arc）；如果某條弧上的流量小于其容量（），則稱該弧為非飽和??；如果某條弧上的流量為 0（），則稱該弧為空?。╲oid arc）。 一般來說，我們總是可以把的流網(wǎng)絡(luò)轉(zhuǎn)化為的流網(wǎng)絡(luò)進(jìn)行研究。如果流滿足 （1）， （2）則稱為可行流（feasible flow）。 在流網(wǎng)絡(luò)中，弧的容量下界和容量上界表示的物理意義分別是：通過該弧發(fā)送某種“物質(zhì)”時(shí)，必須發(fā)送的最小數(shù)量為，而發(fā)送的最大數(shù)量為。endcircle,sum167。 end end endendsum1=0。%改變初始圈，該算法的最后一個(gè)頂點(diǎn)不動(dòng)flag=1。for i=1:L1 sum1=sum1+a(c1(i),c1(i+1))。while flag0 flag=0。a=a+a39。a(4,5)=51。a(2,6)=70。a(1,6)=60。例13 從北京（Pe）乘飛機(jī)到東京(T)、紐約(N)、墨西哥城(M)、倫敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，應(yīng)如何安排旅游線，使旅程最短？各城市之間的航線距離如下表：LMNPaPeTL5635215160M5621577870N3521366868Pa2157365161Pe5178685113T6070686113解：編寫程序如下：clc,cleara(1,2)=56。則對(duì)于任何頂點(diǎn)，是在中的Hamilton軌，因而也是的生成樹。用改良圈算法得到的結(jié)果幾乎可以肯定不是最優(yōu)的。設(shè)初始圈。與最短路問題及連線問題相反，目前還沒有求解旅行商問題的有效算法。kPP的數(shù)學(xué)模型如下：是連通圖，求的回路，使得（i），（ii），（iii） 旅行商（TSP）問題一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品，然后回到他的出發(fā)地。（v）求中邊的端點(diǎn)之間的在中的最短軌。（i）求。 應(yīng)用 郵遞員問題中國郵遞員問題一位郵遞員從郵局選好郵件去投遞，然后返回郵局，當(dāng)然他必須經(jīng)過他負(fù)責(zé)投遞的每條街道至少一次，為他設(shè)計(jì)一條投遞路線，使得他行程最短。Fleury算法：1o. ，令。（iii）中有Euler跡的充要條件是連通且至多有兩個(gè)奇次點(diǎn)。6 Euler圖和Hamilton圖 基本概念定義 經(jīng)過的每條邊的跡叫做的Euler跡；閉的Euler跡叫做Euler回路或回路；含Euler回路的圖叫做Euler圖。(iii)若，轉(zhuǎn)（iv）；若，取 ， ， 。例如 。為此，我們要引入可行頂點(diǎn)標(biāo)號(hào)與相等子圖的概念。把以上算法稍加修改就能夠用來求二分圖的最大對(duì)集。匈牙利算法：（i）從中任意取定一個(gè)初始對(duì)集。由此推論得出下面的婚配定理：定理4 每個(gè)姑娘都結(jié)識(shí)位小伙子，每個(gè)小伙子都結(jié)識(shí)位姑娘，則每位姑娘都能和她認(rèn)識(shí)的一個(gè)小伙子結(jié)婚，并且每位小伙子也能和他認(rèn)識(shí)的一個(gè)姑娘結(jié)婚。1957年，貝爾熱(Berge)得到最大對(duì)集的充要條件：定理2 是圖中的最大對(duì)集當(dāng)且僅當(dāng)中無可增廣軌。 index(:,flag)=[]。 if index(1,flag)~=index(2,flag) result=[result,data(:,flag)]。 flag=find(data(3,:)==temp)。index=data(1:2,:)。data=[i39。 [i,j]=find((a~=