1、1.圖論問題的起源 18世紀東普魯士哥尼斯堡被普列戈爾河分為四塊,它們通過七座橋相互連接,如下圖.當時該城的市民熱衷于這樣一個游戲:“一個散步者怎樣才能從某塊陸地出發(fā)，經(jīng)每座橋一次且僅一次回到出發(fā)點？”SNAB七橋問題的分析 七橋問題看起來不難，很多人都想試一試，但沒有人找到答案 .后來有人寫信告訴了當時的著名數(shù)學家歐拉.千百人的失敗使歐拉猜想,也許那樣的走法根本不可能.1876年,他證明了自己的猜想. Euler把南北兩岸和四個島抽象成四個點,將連接這些陸地的橋用連接相應兩點的一條線來表示,就得到如下一個簡圖:SNAB歐拉的結(jié)論歐拉指出:一個線圖中存在通過每邊一次僅一次回到出發(fā)點的路線的充要

2、條件是:1)圖是連通的,即任意兩點可由圖中的一些邊連接起來;2)與圖中每一頂點相連的邊必須是偶數(shù).由此得出結(jié)論:七橋問題無解. 歐拉由七橋問題所引發(fā)的研究論文是圖論的開篇之作,因此稱歐拉為圖論之父.4.圖的作用 圖是一種表示工具.改變問題的描述方式,往往是創(chuàng)造性的啟發(fā)式解決問題的手段.一種描述方式就好比我們站在一個位置和角度觀察目標,有的東西被遮擋住了,但如果換一個位置和角度,原來隱藏著的東西就可能被發(fā)現(xiàn).采用一種新的描述方式,可能會產(chǎn)生新思想.圖論中的圖提供了一種直觀,清晰表達已知信息的方式.它有時就像小學數(shù)學應用題中的線段圖一樣,能使我們用語言描述時未顯示的或不易觀察到的特征、關(guān)系,直觀地

3、呈現(xiàn)在我們面前,幫助我們分析和思考問題,激發(fā)我們的靈感.5.圖的廣泛應用 圖的應用是非常廣泛的,在工農(nóng)業(yè)生產(chǎn)、交通運輸、通訊和電力領域經(jīng)常都能看到許多網(wǎng)絡,如河道網(wǎng)、灌溉網(wǎng)、管道網(wǎng)、公路網(wǎng)、鐵路網(wǎng)、電話線網(wǎng)、計算機通訊網(wǎng)、輸電線網(wǎng)等等.還有許多看不見的網(wǎng)絡,如各種關(guān)系網(wǎng),像狀態(tài)轉(zhuǎn)移關(guān)系、事物的相互沖突關(guān)系、工序的時間先后次序關(guān)系等等,這些網(wǎng)絡都可以歸結(jié)為圖論的研究對象圖.其中存在大量的網(wǎng)絡優(yōu)化問題需要我們解決.還有象生產(chǎn)計劃、投資計劃、設備更新等問題也可以轉(zhuǎn)化為網(wǎng)絡優(yōu)化的問題.6.基本的網(wǎng)絡優(yōu)化問題 基本的網(wǎng)絡優(yōu)化問題有:最短路徑問題、最小生成樹問題、最大流問題和最小費用問題.圖論作為數(shù)學的一

4、個分支,已經(jīng)有有效的算法來解決這些問題.當然這當中的有些問題也可以建立線性規(guī)劃的模型,但有時若變量特別多,約束也特別多,用線性規(guī)劃的方法求解效率不高甚至不能在可忍受的時間內(nèi)解決.而根據(jù)這些問題的特點,采用網(wǎng)絡分析的方法去求解可能會非常有效. 例如,在1978年,美國財政部的稅務分析部門在對卡特爾稅制改革做評估的過程中,就有一個100,000個約束以上,25,000,000個變量的問題,若用普通的線性規(guī)劃求解,預計要花7個月的時間.他們利用網(wǎng)絡分析的方法,將其分解成6個子問題,利用特殊的網(wǎng)絡計算機程序,花了大約7個小時問題就得到了解決. 數(shù)學建模與數(shù)學實驗主講：陳六新最短路徑與最優(yōu)匹配問題實驗目

5、的實驗內(nèi)容2會用MATLAB軟件求最短路與最優(yōu)匹配1了解最短路與最優(yōu)匹配的算法及其應用1圖 論 的 基 本 概 念2最 短 路 問 題 及 其 算 法3最 短 路 的 應 用5建模案例：最優(yōu)截斷切割問題6實驗作業(yè)4最優(yōu)匹配及算法 圖 論 的 基 本 概 念一、 圖 的 概 念1圖的定義2頂點的次數(shù) 3子圖二、 圖 的 矩 陣 表 示1 關(guān)聯(lián)矩陣2 鄰接矩陣返回定義有序三元組G=(V,E, )稱為一個圖,如果：圖的定義定義定義返回頂點的次數(shù)例 在一次聚會中，認識奇數(shù)個人的人數(shù)一定是偶數(shù).返回子圖返回關(guān)聯(lián)矩陣注：假設圖為無向簡單圖返回鄰接矩陣注：假設圖為簡單無向圖返回最 短 路 問 題 及 其 算

6、 法一、 基 本 概 念二、固 定 起 點 的 最 短 路三、每 對 頂 點 之 間 的 最 短 路返回基 本 概 念返回固 定 起 點 的 最 短 路最短路是一條路徑，且最短路的任一段也是最短路 假設在u0-v0的最短路中只取一條，則從u0到其余頂點的最短路將構(gòu)成一棵以u0為根的樹 因此, 可采用樹生長的過程來求指定頂點到其余頂點的最短路62341587算法步驟： TO MATLAB(road1) 1 2 34 5 6 7 8返回每 對 頂 點 之 間 的 最 短 路1求距離矩陣的方法2求路徑矩陣的方法3查找最短路路徑的方法（一）算法的基本思想（三）算法步驟返回算法的基本思想返回算法原理 求

7、距離矩陣的方法返回算法原理 求路徑矩陣的方法在建立距離矩陣的同時可建立路徑矩陣R 即當k被插入任何兩點間的最短路徑時，被記錄在R(k)中，依次求 時求得 ，可由 來查找任何點對之間最短路的路徑返回)(nRi j算法原理 查找最短路路徑的方法pkp2p1p3q1q2qm則由點i到j的最短路的路徑為：返回算法步驟 TOMATLAB(road2(floyd)返回一、 可化為最短路問題的多階段決策問題二、 選 址 問 題1 中心問題2 重心問題返回可化為最短路問題的多階段決策問題返回 選址問題-中心問題 TO MATLAB(road3(floyd)S(v1)=10, S(v2)=7, S(v3)=6,

8、 S(v4)=10, S(v5)=7, S(v6)=7, S(v7)=8.5S(v3)=6,故應將消防站設在v3處. 返回 選址問題-重心問題返回匹配 匹配問題是運籌學的重要問題之一,也是圖論研究的重點內(nèi)容,它提供了解決“人員分配問題”和“最優(yōu)分配問題”一種新的思想.定義1.設G=是無環(huán)圖,ME(G),M,若M中任意兩條邊都不相鄰,則稱M是圖G的一個匹配.若對圖G的任何匹配M ,均有M |M|,矛盾.()若M不是G的最大匹配,則存在匹配M,使得|M|M|,作H=MM,由定理1,H的任意邊導出子圖Q是下列兩種情況之一:(1)交錯偶圈:Q中每個結(jié)點度數(shù)為2.(2)交錯路.Q中除端點外,其余結(jié)點度數(shù)

9、均為2. 因為|M|M|,故|E(H)M|E(H)M|,因而H中必有一條起始于M且終止于M的連通分支P,故P是M可增廣路,矛盾,所以命題正確. 定義:NG(S):設S是圖G的任意頂點子集,G中與S的頂點鄰接的所有頂點的集合,稱為S的鄰集,記做NG(S).定理3(Hall定理,1935)設G是有二部劃分(V1,V2)的二分圖,則G含有飽和V1的每個頂點的匹配M的充要條件是,對SV1,有N(S)S.證明:()對SV1,匹配M將S中的每個頂點與N(S)中的頂點配對,所以N(S)S. ()當對SV1,有N(S)S時.可按下述方法作出飽和V1的匹配M. 先作一初始匹配M1,若已經(jīng)飽和V1,定理得證.否則

10、,V1中至少有一非飽和點x1,檢查以x1為起點,終點在V2中的交錯路.考慮下面兩種情形:(1)不存在任何一條交錯路可以到達V2的非飽和點.此時從X1開始的一切交錯路的終點還是在V1中.故存在AV1,使得N(A)M1,因此,重復該過程就可以找到飽和V1的全部頂點的匹配M.推論1 具有二部劃分(V1,V2)的二分圖G有完美匹配 V1=V2,且對SV1(或V2),有N(S)S.證明:必要性.若二分圖G有完美匹配,由定理3有V2=N(V1)V1,即V2V1,同理V1V2,因此V1=V2.充分性:因為對SV1,有N(S)S,由定理1,G中存在飽和V1的每個頂點匹配M,又G是二分圖,故匹配M的每一邊的兩個

11、端點分別屬于V1和V2,據(jù)V1=V2即知M飽和V2,所以M為完美匹配.推論2. 設G是k(0)正則二分圖,則G有完美匹配.證明:因為G是二部劃分(V1,V2)的k正則二分圖,故 kV1=E(G)=kV2 又k0,所以V1=V2.任取SV1,并用E1和E2分別表示G中與S和N(S)中關(guān)聯(lián)的邊集,則E1E2,則 kN(S)=E2E1=kS即N(S)S, SV1, 由定理3可知,G有飽和V1的匹配M,再據(jù)V1=V2和推論1即知M是完美匹配.推論3. 設G是二部劃分(V1,V2)的簡單二分圖,且V1=V2=n,若(G)n/2,則G有完美匹配.證明:SV1,(1)若S中至少有兩個頂點,由(G)n/2可知

12、N(S)n/2+n/2=n=V1S(2)若S中只有一個頂點,由(G)n/2可知N(S)n/2,所以 N(S)1S=1.綜上,對SV1,均有N(S)S,所以G中有完美匹配.定理4. G有完美匹配O(G-S)S,SV(G),其中O(G-S)是G-S的奇數(shù)階連通分支數(shù)目.(不證)例1.有n張紙牌,每張紙牌的正反兩面都寫上1,2,n的某一個數(shù).證明:如果每個數(shù)字恰好出現(xiàn)兩次,則這些紙牌一定可以這樣攤開,使朝上的面中1,2,n都出現(xiàn).證明:作一個二分圖G=,其中V1=1,2,n,V2=y1,y2,yn表示這n張紙牌.i與yi之間連接的邊數(shù)等于數(shù)i在紙牌yj中出現(xiàn)的次數(shù),這樣得到的圖G是一個2-正則二分圖

13、,因此圖G中有完美匹配,設為M=1yi1,2yi2,nyin 則只要把紙牌yi1中的1朝上,yi2中的2朝上,yin的n朝上,這樣攤開,這樣攤開的紙牌就能使上面中1,2,n都出現(xiàn).例2.某工廠生產(chǎn)由6種不同顏色的紗布織成的雙色布,由該廠所生產(chǎn)的雙色布中,每一種顏色至少和其他三種顏色搭配.證明可以挑選出三種不同的雙色布,它們含有所有的6種顏色.證明:構(gòu)造圖G=,其中V=v1,v2,v3,v4,v5,v6表示6種顏色,工廠生產(chǎn)出一種顏色vi與vj搭配而成的雙色布邊vi,vjE(G).由題意知,G為簡單圖,且每個結(jié)點的度數(shù)至少為3,下證G中含有一個完美匹配. 今設v1,v2E(G),由于d(v3)

14、3,所以存在一個不同于v1和v2的頂點vi(4i6),使v3,viE(G),不妨設vi=4,即v3,v4E(G). 如果邊v5,v6E(G),由于d(v5)3,v1,v2,v3,v4中至少有3個頂點與v5相鄰,即v5與邊v1,v2,v3,v4中的每一邊的某一個端點相鄰,不妨設v1,v5E(G)和v3,v5E(G). 對于頂點v6,同樣與v1,v2,v3,v4中至少3個頂點相鄰,即在v2和v4中至少有一個頂點與v6相鄰.如果v2,v6E(G),則邊v1,v5,v3,v4,v2,v6是G的一個完美匹配;如果v4,v6E(G),則v1,v5,v3,v5,v4,v6是G的一個完美匹配. 綜上所述,G總

15、存在完美匹配,完美匹配中的三條邊所對應的三種雙色布即為所求.最大匹配的生成算法-匈牙利算法定義1. 根在x的M交錯子圖:設M是圖G的匹配，x是G中非M飽和點。G中由起點為x的M交錯路所能連接的頂點集所導出的G的導出子圖稱為根在x的M交錯子圖.定理1. 設M是具有二部劃分(V1,V2)的二分圖G的匹配,xV1是非M飽和點,H是G中根在x的M交錯子圖的頂點集S=HV1,T=HV2,則:(1)TNG(S);(2)下述三條等價:(a)G中不存在以x為端點的M可增廣路;(b)x是H中唯一的非M飽和點;(c) T=NG(S),且T=S-1.證明:(1)yT,則G中存在以x和y為端點的M交錯路P.令uNp(

16、y),由于G是二分圖且yTV2,所以uHV1=S,即yNG(S),因而T NG(S),.(2)(a)(b)設y是H中異于x的非M飽和點,則G中存在以x和y為端點的M交錯路P。P是G中以x為端點的M可增廣路,與(a)矛盾.(b)(c)任取yNG(S)V2,則存在uS=H V1和邊eE(G)使G(e)=u,y.若u=x,顯然有yT.若ux,則G中存在以x和u為端點的交錯路P.因為x是唯一非M飽和點,所以u為M飽和點.若P不含y,則eM.由H的定義知,y HV2=T,所以NG(S)T,再由(1),T= NG(S).顯然yT(交錯路中不可能含有兩個非M飽和點),與T=NG(S)矛盾.若yS,則顯然有T

17、=S-2.矛盾. 所以G中不存在以x為端點的M可增廣路.(3) (c)(a)反設G中存在以x為端點的M可增廣路,則G中至少還存在一個異于x的非M飽和點y,若yS,則yT NG(S),匈牙利算法基本思想:設G是具有二部劃分(V1,V2)的二分圖,從圖G的任意匹配M開始.若M飽和V1,則M是G的匹配.若M不能飽和V1,則在V1中選擇一個非M飽和點x,若G中存在以x為起點的M可增廣路P,則M=MP就是比M更大的匹配,利用M代替M,并重復這個過程.若G中不存在以x為起點的M可增廣路,則令H是根在x的M交錯子圖的頂點集,并令S=HV1,T=HV2, 由定理1,T=NG(S),且G中不存在以x為起點的M可

18、增廣路,此時稱x為檢驗過的非M飽和點.對V1中其它未檢驗過的非M飽和點重復該過程,直到V1中的所有非M飽和點全部檢驗過為止.當整個過程結(jié)束時,由于G中不存在M可增廣路,從而M為G的最大匹配.匈牙利算法步驟:設G是具有二部劃分(V1,V2)的二分圖.(1)任給初始匹配M;(2)若M飽和V1則結(jié)束.否則轉(zhuǎn)(3);(3)在V1中找一非M飽和點x,置S=x,T=;(4)若N(S)=T,則停止,否則任選一點yN(S)-T;(5)若y為M飽和點轉(zhuǎn)(6),否則作求一條從x到y(tǒng)的M可增廣路P,置M=MP,轉(zhuǎn)(2)(6)由于y是M飽和點,故M中有一邊y,u,置S=Su,T=Ty,轉(zhuǎn)(4).例1 如圖G所示，V1

19、=x1,x2,x3,x4,x5，V2=y1,y2,y3,y4,y5，試求圖G的最大匹配。x1, x2 x3 x4 x5y1 y2 y3 y4 y5圖ax1 x2 x3 x4 x5y1 y2 y3 y4 y5圖bx1 x2 x3 x4 x5y1 y2 y3 y4 y5解：任取初始匹配M=x2y2,x3y3,x5y5，如圖(a)中虛線所示.解題過程如下表:MxSTN(S)yN(S)-Ty,u MPx2y2,x3y3,x5y5x1x1y2,y3y2飽和y2,x2x1,x2y2y1,y2,y3,y4,y5y1非飽和(x1y2x2y1)x1y2,x2y1,x3y3 x5y5x4x4y2,x3y2飽和y2

20、,x1x4,x1y2y2,y3y3飽和y3,x3x4,x1,x3y2,y3y2,y3N(S)=T,停止因此,M=x1y2,x2y1,x3y3,x5y5即為圖G的最大匹配,如圖(b)虛線所示.匈牙利算法的時間復雜度分析:設二分圖G有n個結(jié)點,m條邊,利用匈牙利算法求G的最大匹配時,初始匹配可為空,因此算法最多可找n條可增廣路,每找一條可增廣路,最多比較m條邊,從而算法的時間復雜度為O(mn),故匈牙利算法為有效算法.最優(yōu)匹配定義1.最優(yōu)匹配:在加權(quán)圖中求一個總權(quán)最大的完美匹配,這種匹配稱為最優(yōu)匹配.定義2.已知G是具有二部劃分(V1,V2)的完全加權(quán)二分圖,映射l:V(G)R,滿足對G的每條邊e=x,y,均有l(wèi)(x)+l(y)(x,y),其中(x,y)表示邊x,y的權(quán),則稱l為G的可行頂標.令El=x,yx,yE(G),l(x)+l(y)=(x