數(shù)模培訓資料課件

全國數(shù)學建模競賽培訓這是一場艱苦的戰(zhàn)役。需要不怕苦和不怕累的精神，要有堅忍不拔的毅力。1/5/2023全國數(shù)學建模競賽培訓這是一場艱苦的戰(zhàn)役。需要不怕苦和1可能面臨酷暑、內(nèi)容多、強度大的困難。1/5/2023可能面臨酷暑、內(nèi)容多、強度大的困難。12/28/20222數(shù)學建模暑期培訓紀律不允許缺課，遲到和早退的現(xiàn)象發(fā)生。每一個隊每一次培訓或講評，必須是三人到齊。教練會對每一次活動考勤，并與相關(guān)學院聯(lián)系，對缺課學生予以相應處罰。1/5/2023數(shù)學建模暑期培訓紀律不允許缺課，遲到和早退的現(xiàn)象發(fā)生。12/3圖論算法參考教材：數(shù)學建模與數(shù)學實驗（趙靜、但琦編）數(shù)學建模導論（陳理榮編）圖論及其算法（殷劍宏、吳開亞編）集合論與圖論（耿素云編）1/5/2023圖論算法參考教材：12/28/20224圖論算法１.最短路問題２.中國郵遞員問題和ＴＳＰ問題３.匹配1/5/2023圖論算法１.最短路問題12/28/20225圖論算法（１）－最短路問題1．圖論的基本概念2．最短路問題及其算法3．最短路的應用4．建模案例：最優(yōu)截斷切割問題5．實例應用1/5/2023圖論算法（１）－最短路問題1．圖論的基本概念2．6圖論的基本概念一、圖的概念1．圖的定義2．頂點的次數(shù)

3．子圖二、圖的矩陣表示1．關(guān)聯(lián)矩陣2．鄰接矩陣返回1/5/2023圖論的基本概念一、圖的概念1．圖的定義27定義有序三元組G=(V,E,)稱為一個圖,如果：圖的定義1/5/2023定義有序三元組G=(V,E,)稱為一個圖,如果：8定義定義1/5/2023定義定義12/28/202291/5/202312/28/202210返回1/5/2023返回12/28/202211頂點的次數(shù)（度數(shù)）1/5/2023頂點的次數(shù)（度數(shù)）12/28/202212例

在一次聚會中，認識奇數(shù)個人的人數(shù)一定是偶數(shù).返回1/5/2023例在一次聚會中，認識奇數(shù)個人的人數(shù)一定是偶數(shù).返回1213子圖返回1/5/2023子圖返回12/28/202214關(guān)聯(lián)矩陣注：假設(shè)圖為簡單圖返回1/5/2023關(guān)聯(lián)矩陣注：假設(shè)圖為簡單圖返回12/28/202215鄰接矩陣注：假設(shè)圖為簡單圖1/5/2023鄰接矩陣注：假設(shè)圖為簡單圖12/28/202216返回1/5/2023返回12/28/202217最短路問題及其算法一、基本概念二、固定起點的最短路三、每對頂點之間的最短路返回1/5/2023最短路問題及其算法一、基本概念二、固定起點的最短路三、每對18基本概念1/5/2023基本概念12/28/202219返回1/5/2023返回12/28/202220固定起點的最短路-Dijkstra算法最短路是一條路徑，且最短路的任一段也是最短路．假設(shè)在u0-v0的最短路中只取一條，則從u0到其余頂點的最短路將構(gòu)成一棵以u0為根的樹．因此,可采用樹生長的過程來求指定頂點到其余頂點的最短路．1/5/2023固定起點的最短路-Dijkstra算法最短路是一條路徑，且最21Dijkstra算法思想Dijkstra算法:這是荷蘭計算機科學教授EdsgerW.Dijkstra(1930-)在1959年發(fā)現(xiàn)的一個算法.他在1972年獲得計算機協(xié)會授予的圖靈獎,這是計算機科學中最具聲望的獎項.Dijkstra算法是求出一個連通加權(quán)簡單圖中從結(jié)點a到結(jié)點z的最短路.邊{i,j}的權(quán)(i,j)>0,且結(jié)點x的標號為L(x),結(jié)束時,L(z)是從x到z的最短路的長度.1/5/2023Dijkstra算法思想Dijkstra算法:這是荷蘭計算機221/5/202312/28/202223算法步驟：1/5/2023算法步驟：12/28/202224

TOMATLAB(road1)1/5/2023TOMATLAB(road1)12/28/2022251/5/202312/28/202226

12

34

5

6

7

8返回1/5/202312345678返回12/27每對頂點之間的最短路-Floyd算法1．求距離矩陣的方法2．求路徑矩陣的方法3．查找最短路路徑的方法（一）算法的基本思想（三）算法步驟返回1/5/2023每對頂點之間的最短路-Floyd算法1．求距離矩陣的方法2．28算法的基本思想返回1/5/2023算法的基本思想返回12/28/202229算法原理——求距離矩陣的方法返回1/5/2023算法原理——求距離矩陣的方法返回12/28/202230算法原理——求路徑矩陣的方法在建立距離矩陣的同時可建立路徑矩陣R．即當k被插入任何兩點間的最短路徑時，被記錄在R(k)中，依次求時求得，可由來查找任何點對之間最短路的路徑．返回)(nR1/5/2023算法原理——求路徑矩陣的方法在建立距離矩陣的同時可建立路徑31i

j算法原理——

查找最短路路徑的方法pkp2p1p3q1q2qm則由點i到j(luò)的最短路的路徑為：返回1/5/2023ij算法原理——查找最短路路徑的方法pkp2p1p3q32算法步驟1/5/2023算法步驟12/28/202233

TOMATLAB(road2(floyd))返回

1/5/2023TOMATLAB(road2(floyd))返回1234一、可化為最短路問題的多階段決策問題二、選址問題1．中心問題2．重心問題返回1/5/2023一、可化為最短路問題的多階段決策問題二、選址問題135可化為最短路問題的多階段決策問題1/5/2023可化為最短路問題的多階段決策問題12/28/2022361/5/202312/28/2022371/5/202312/28/202238返回1/5/2023返回12/28/202239

選址問題--中心問題

TOMATLAB(road3(floyd))1/5/2023選址問題--中心問題TOMATLAB(road340S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故應將消防站設(shè)在v3處.返回1/5/2023S(v1)=10,S(v2)=7,S(v3)=6,S(41

選址問題--重心問題返回1/5/2023選址問題--重心問題返回12/28/202242圖論算法（２）－中國郵遞員問題和ＴＳＰ問題1/5/2023圖論算法（２）12/28/202243郵路問題及ＴＳＰ問題一、中國郵遞員問題二、推銷員問題三、建模案例：最佳災情巡視路線（一）歐拉圖（二）中國郵遞員問題（一）哈密爾頓圖（二）推銷員問題1/5/2023郵路問題及ＴＳＰ問題一、中國郵遞員問題二、推銷員問題三、建模44

7

3

1

2

3

4

1

2

4

5

5

6

6

7

8

9割邊G的邊是割邊的充要條件是不含在G的圈中．

割邊的定義：設(shè)G連通，E(G),若從G中刪除邊后，圖G-{}不連通，則稱邊為圖G的割邊．1/5/2023731234124556645

e3

v1

v2

v3

v4e1e2e4

e5e6歐拉圖

e3

v1

v2

v3

v4

e1e

2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1歐拉道路：v1e1v2e2v3e5v1e4v4e3v3歐拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v11/5/2023e3v1v2v3v4e1e2e4e5e6歐拉圖46e3

v1

v2

v3v4e1e2e4

e5e3

v1

v2

v3v

4

e1

e2e4

e5e6歐拉圖非歐拉圖返回1/5/2023e3v1v2v3v4e1e2e4e5e3v147中國郵遞員問題-定義1/5/2023中國郵遞員問題-定義12/28/202248中國郵遞員問題-算法

Fleury算法基本思想：從任一點出發(fā)，每當訪問一條邊時，先要進行檢查．如果可供訪問的邊不只一條，則應選一條不是未訪問的邊集的導出子圖的割邊作為訪問邊，直到?jīng)]有邊可選擇為止.1/5/2023中國郵遞員問題-算法Fleury算法基本思想：從任49

v7e3

v1v2

v3v4e1

e2e4

e5

v5

e6e6

e7

e8

e9e101/5/2023v7e3v1v2v3v4e1e2e4e5v550若G不是歐拉圖，則G的任何一個巡回經(jīng)過某些邊必定多于一次．解決這類問題的一般方法是：在一些點對之間引入重復邊（重復邊與它平行的邊具有相同的權(quán)），使原圖成為歐拉圖，但希望所有添加的重復邊的權(quán)的總和為最?。?/p>

1/5/2023若G不是歐拉圖，則G的任何一個巡回經(jīng)過某些邊必51v7e3v1v2v3v4e1e2e4e5v5v6e6e7e8e91/5/2023v7e3v1v2v3v4e1e2e4e5v5v6e6e7e8521/5/202312/28/202253（３）求出G1的最小權(quán)理想匹配M，得到奇次頂點的最佳配對．1/5/2023（３）求出G1的最小權(quán)理想匹配M，得到奇次頂點的最佳配對．154返回1/5/2023返回12/28/202255哈密爾頓圖返回1/5/2023哈密爾頓圖返回12/28/202256推銷員問題-定義流動推銷員需要訪問某地區(qū)的所有城鎮(zhèn)，最后回到出發(fā)點．問如何安排旅行路線使總行程最?。@就是推銷員問題．若用頂點表示城鎮(zhèn)，邊表示連接兩城鎮(zhèn)的路，邊上的權(quán)表示距離（或時間、或費用），于是推銷員問題就成為在加權(quán)圖中尋找一條經(jīng)過每個頂點至少一次的最短閉通路問題．1/5/2023推銷員問題-定義流動推銷員需要訪問某地區(qū)的所有城57定義在加權(quán)圖G=(V,E)中，（１）權(quán)最小的哈密爾頓圈稱為最佳H圈(Hamilton圈)．（２）經(jīng)過每個頂點至少一次的權(quán)最小的閉通路稱為最佳推銷員回路．一般說來，最佳哈密爾頓圈不一定是最佳推銷員回路，同樣最佳推銷員回路也不一定是最佳哈密爾頓圈．H回路，長22最佳推銷員回路，長41/5/2023定義在加權(quán)圖G=(V,E)中，一般說來，最佳哈581/5/202312/28/202259推銷員問題近似算法：二邊逐次修正法：1/5/2023推銷員問題近似算法：二邊逐次修正法：12/28/202260例對以下完備圖，用二邊逐次修正法求較優(yōu)H圈．1/5/2023例對以下完備圖，用二邊逐次修正法求較優(yōu)H圈．12/28/261返回1/5/2023返回12/28/202262圖論算法（３）－匹配

匹配問題是運籌學的重要問題之一,也是圖論研究的重點內(nèi)容,它提供了解決“人員分配問題”和“最優(yōu)分配問題”一種新的思想.定義1.設(shè)G=<V,E>是無環(huán)圖,ME(G),M,若M中任意兩條邊都不相鄰,則稱M是圖G的一個匹配.若對圖G的任何匹配M’,均有M’<M,則稱M是圖G的最大匹配,記作’(G).定義2.設(shè)M是圖G的匹配,G中與M中的邊關(guān)聯(lián)的頂點稱為M飽和點.若圖G的頂點都是M飽和,則稱為G的完美匹配.1/5/2023圖論算法（３）－匹配匹配問題是運籌學的重要問題之63說明:(1)完美匹配是最大匹配,反之未然;(2)匹配的定義與邊的方向無關(guān),故匹配是針對無向圖而言.定義3.(可增廣路):設(shè)M是圖G的匹配,P是G的一條路,且在P中,M的邊和E(G)-M的邊交替出現(xiàn),則稱P是G的一條交錯路.若M交錯路P的兩個端點為M非飽和點,則稱P為M可增廣路.例1.求下圖G的一條交錯路和一條可增廣路.623415871/5/2023說明:(1)完美匹配是最大匹配,反之未然;62341587164匹配的幾個性質(zhì)定理定理1.設(shè)M1和M2是圖G的兩個不同匹配,由M1M2導出的G的邊導出子圖,記作H,則H的任意連通分支是下列情況之一:(1)邊在M1和M2中交錯出現(xiàn)的偶圈.(2)邊在M1和M2中交錯出現(xiàn)的路.定理2.M是圖G的最大匹配,當且僅當G中不存在M可增廣路.定義:設(shè)S是圖G的任意頂點子集,G中與S的頂點鄰接的所有頂點的集合,稱為S的鄰集,記做NG(S).1/5/2023匹配的幾個性質(zhì)定理定理1.設(shè)M1和M2是圖G的兩個不同匹配,65定理3(Hall定理,1935)設(shè)G是有二部劃分(V1,V2)的二分圖,則G含有飽和V1的每個頂點的匹配M的充要條件是,對SV1,有N(S)S.推論1具有二部劃分(V1,V2)的二分圖G有完美匹配V1=V2,且對SV1(或V2),有N(S)S.推論2.

設(shè)G是k(>0)正則二分圖,則G有完美匹配.由定理3可知,G有飽和V1的匹配M,再據(jù)V1=V2和推論1即知M是完美匹配.推論3.設(shè)G是二部劃分(V1,V2)的簡單二分圖，且V1=V2=n，若(G)n/2，則G有完美匹配.1/5/2023定理3(Hall定理,1935)設(shè)G是有二部劃分(V1,V266定理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,V2,E>,其中V1={1,2,…,n}，V2={y1,y2,…,yn}表示這n張紙牌.i與yi之間連接的邊數(shù)等于數(shù)i在紙牌yj中出現(xiàn)的次數(shù),這樣得到的圖G是一個2-正則二分圖,因此圖G中有完美匹配,設(shè)為M={1yi1,2yi2,…,nyin}

則只要把紙牌yi1中的1朝上,yi2中的2朝上,…,yin的n朝上,這樣攤開,這樣攤開的紙牌就能使上面中1,2,…,n都出現(xiàn).1/5/202312/28/202267例2.某工廠生產(chǎn)由6種不同顏色的紗布織成的雙色布,由該廠所生產(chǎn)的雙色布中,每一種顏色至少和其他三種顏色搭配.證明可以挑選出三種不同的雙色布,它們含有所有的6種顏色.證明:構(gòu)造圖G=<V,E>,其中V={v1,v2,v3,v4,v5,v6}表示6種顏色,工廠生產(chǎn)出一種顏色vi與vj搭配而成的雙色布邊{vi,vj}E(G).由題意知,G為簡單圖,且每個結(jié)點的度數(shù)至少為3,下證G中含有一個完美匹配.今設(shè){v1,v2}E(G),由于d(v3)≥3,所以存在一個不同于v1和v2的頂點vi(4≤i≤6),使{v3,vi}E(G),不妨設(shè)vi=4,即{v3,v4}E(G).1/5/2023例2.某工廠生產(chǎn)由6種不同顏色的紗布織成的雙色布,由該12/68

如果邊{v5,v6}E(G),由于d(v5)≥3,v1,v2,v3,v4中至少有3個頂點與v5相鄰,即v5與邊{v1,v2},{v3,v4}中的每一邊的某一個端點相鄰,不妨設(shè){v1,v5}E(G)和{v3,v5}E(G).對于頂點v6,同樣與v1,v2,v3,v4中至少3個頂點相鄰,即在v2和v4中至少有一個頂點與v6相鄰.如果{v2,v6}E(G),則邊{v1,v5},{v3,v4},{v2,v6}是G的一個完美匹配;如果{v4,v6}E(G),則{v1,v2},{v3,v5},{v4,v6}是G的一個完美匹配.綜上所述,G總存在完美匹配,完美匹配中的三條邊所對應的三種雙色布即為所求.1/5/2023如果邊{v5,v6}E(G),由于d(v5)≥3,v69最大匹配的生成算法-匈牙利算法定義1.根在x的M交錯子圖:設(shè)M是圖G的匹配,x是G中非M飽和點.G中由起點為x的M交錯路所能連接的頂點集所導出的G的導出子圖稱為根在x的M交錯子圖.定理1.設(shè)M是具有二部劃分(V1,V2)的二分圖G的匹配,xV1是非M飽和點,H是G中根在x的M交錯子圖的頂點集S=H∩V1,T=H∩V2,則:(1)TNG(S);(2)下述三條等價:(a)G中不存在以x為端點的M可增廣路;(b)x是H中唯一的非M飽和點;(c)T=NG(S),且T=S-1.(不證)1/5/2023最大匹配的生成算法-匈牙利算法定義1.根在x的M交錯子圖:70匈牙利算法基本思想:設(shè)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可增廣路,此時稱x為檢驗過的非M飽和點.對V1中其它未檢驗過的非M飽和點重復該過程,直到V1中的所有非M飽和點全部檢驗過為止.當整個過程結(jié)束時,由于G中不存在M可增廣路,從而M為G的最大匹配.1/5/2023匈牙利算法基本思想:設(shè)G是具有二部劃分(V1,V2)的二分圖71匈牙利算法步驟:設(shè)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=S{u},T=T{y},轉(zhuǎn)(4).1/5/2023匈牙利算法步驟:12/28/202272例1.如圖G所示,V1={x1,x2,x3,x4,x5},V2={y1,y2,y3,y4,y5}，試求圖G的最大匹配.x1,,x2x3x4x5y1y2y3y4y5圖ax1x2x3x4x5y1y2y3y4y5圖b1/5/2023例1.如圖G所示,V1={x1,x2,x3,x4,x5},73解:任取初始匹配M={x2y2,x3y3,x5y5},如圖(a)中虛線所示.解題過程如下表:MxSTN(S)yN(S)-T{y,u}MP{x2y2,x3y3,x5y5}x1{x1}{y2,y3}y2飽和{y2,x2}{x1,x2}{y2}{y1,y2,y3,y4,y5}y1非飽和(x1y2x2y1){x1y2,x2y1,x3y3x5y5}x4{x4}{y2,x3}y2飽和{y2,x1}{x4,x1}{y2}{y2,y3}y3飽和{y3,x3}{x4,x1,x3}{y2,y3}{y2,y3}N(S)=T,停止1/5/2023解:任取初始匹配M={x2y2,x3y3,x5y5},如圖(74因此,M={x1y2,x2y1,x3y3,x5y5}即為圖G的最大匹配,如圖(b)虛線所示.1/5/2023因此,M={x1y2,x2y1,x3y3,x5y5}即為圖G75最優(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(x)+L(y)(x,y),其中(x,y)表示邊{x,y}的權(quán),則稱L為G的可行頂標.令EL={{x,y}{x,y}E(G),L(x)+L(y)=(x,y),GL為以EL為邊集的G的生成子圖,則稱GL為L等子圖.說明:可行頂標總是存在的,例如:1/5/2023最優(yōu)匹配定義1.最優(yōu)匹配:在加權(quán)圖中求一個總權(quán)最大的完美76定理1.設(shè)L是G的可行頂標.若L等子圖GL有完美匹配M,則M是G的最優(yōu)匹配.基于定理1的在一個加權(quán)二分圖(Km,n,)中求最優(yōu)匹配的有效算法Kuhn-munkres算法:(1)從任意可行頂標(如平凡標號)L開始,確定L等子圖GL,并且在GL中選取匹配M.若M飽和V1,則M是完美匹配,也即M是最優(yōu)匹配,算法終止,否則轉(zhuǎn)入(2)步.(2)匈牙利算法終止于SV1,TV2且使NGL(S)=T,計算aL,確定新的可行頂標L’,并以L’替代L,以GL’替代GL轉(zhuǎn)入(1)步.1/5/2023定理1.設(shè)L是G的可行頂標.若L等子圖GL有完美匹配77例1.已知完全二分圖k5,5,其中V1={x1,x2,x3,x4,x5},V2={y1,y2,y3,y4,y5,},且k5,5的權(quán)矩陣為A,求k5,5的最優(yōu)匹配.1/5/2023例1.已知完全二分圖k5,5,其中V1={x1,x2,x3,78全國數(shù)學建模競賽培訓這是一場艱苦的戰(zhàn)役。需要不怕苦和不怕累的精神，要有堅忍不拔的毅力。1/5/2023全國數(shù)學建模競賽培訓這是一場艱苦的戰(zhàn)役。需要不怕苦和79可能面臨酷暑、內(nèi)容多、強度大的困難。1/5/2023可能面臨酷暑、內(nèi)容多、強度大的困難。12/28/202280數(shù)學建模暑期培訓紀律不允許缺課，遲到和早退的現(xiàn)象發(fā)生。每一個隊每一次培訓或講評，必須是三人到齊。教練會對每一次活動考勤，并與相關(guān)學院聯(lián)系，對缺課學生予以相應處罰。1/5/2023數(shù)學建模暑期培訓紀律不允許缺課，遲到和早退的現(xiàn)象發(fā)生。12/81圖論算法參考教材：數(shù)學建模與數(shù)學實驗（趙靜、但琦編）數(shù)學建模導論（陳理榮編）圖論及其算法（殷劍宏、吳開亞編）集合論與圖論（耿素云編）1/5/2023圖論算法參考教材：12/28/202282圖論算法１.最短路問題２.中國郵遞員問題和ＴＳＰ問題３.匹配1/5/2023圖論算法１.最短路問題12/28/202283圖論算法（１）－最短路問題1．圖論的基本概念2．最短路問題及其算法3．最短路的應用4．建模案例：最優(yōu)截斷切割問題5．實例應用1/5/2023圖論算法（１）－最短路問題1．圖論的基本概念2．84圖論的基本概念一、圖的概念1．圖的定義2．頂點的次數(shù)

3．子圖二、圖的矩陣表示1．關(guān)聯(lián)矩陣2．鄰接矩陣返回1/5/2023圖論的基本概念一、圖的概念1．圖的定義285定義有序三元組G=(V,E,)稱為一個圖,如果：圖的定義1/5/2023定義有序三元組G=(V,E,)稱為一個圖,如果：86定義定義1/5/2023定義定義12/28/2022871/5/202312/28/202288返回1/5/2023返回12/28/202289頂點的次數(shù)（度數(shù)）1/5/2023頂點的次數(shù)（度數(shù)）12/28/202290例

在一次聚會中，認識奇數(shù)個人的人數(shù)一定是偶數(shù).返回1/5/2023例在一次聚會中，認識奇數(shù)個人的人數(shù)一定是偶數(shù).返回1291子圖返回1/5/2023子圖返回12/28/202292關(guān)聯(lián)矩陣注：假設(shè)圖為簡單圖返回1/5/2023關(guān)聯(lián)矩陣注：假設(shè)圖為簡單圖返回12/28/202293鄰接矩陣注：假設(shè)圖為簡單圖1/5/2023鄰接矩陣注：假設(shè)圖為簡單圖12/28/202294返回1/5/2023返回12/28/202295最短路問題及其算法一、基本概念二、固定起點的最短路三、每對頂點之間的最短路返回1/5/2023最短路問題及其算法一、基本概念二、固定起點的最短路三、每對96基本概念1/5/2023基本概念12/28/202297返回1/5/2023返回12/28/202298固定起點的最短路-Dijkstra算法最短路是一條路徑，且最短路的任一段也是最短路．假設(shè)在u0-v0的最短路中只取一條，則從u0到其余頂點的最短路將構(gòu)成一棵以u0為根的樹．因此,可采用樹生長的過程來求指定頂點到其余頂點的最短路．1/5/2023固定起點的最短路-Dijkstra算法最短路是一條路徑，且最99Dijkstra算法思想Dijkstra算法:這是荷蘭計算機科學教授EdsgerW.Dijkstra(1930-)在1959年發(fā)現(xiàn)的一個算法.他在1972年獲得計算機協(xié)會授予的圖靈獎,這是計算機科學中最具聲望的獎項.Dijkstra算法是求出一個連通加權(quán)簡單圖中從結(jié)點a到結(jié)點z的最短路.邊{i,j}的權(quán)(i,j)>0,且結(jié)點x的標號為L(x),結(jié)束時,L(z)是從x到z的最短路的長度.1/5/2023Dijkstra算法思想Dijkstra算法:這是荷蘭計算機1001/5/202312/28/2022101算法步驟：1/5/2023算法步驟：12/28/2022102

TOMATLAB(road1)1/5/2023TOMATLAB(road1)12/28/20221031/5/202312/28/2022104

12

34

5

6

7

8返回1/5/202312345678返回12/105每對頂點之間的最短路-Floyd算法1．求距離矩陣的方法2．求路徑矩陣的方法3．查找最短路路徑的方法（一）算法的基本思想（三）算法步驟返回1/5/2023每對頂點之間的最短路-Floyd算法1．求距離矩陣的方法2．106算法的基本思想返回1/5/2023算法的基本思想返回12/28/2022107算法原理——求距離矩陣的方法返回1/5/2023算法原理——求距離矩陣的方法返回12/28/2022108算法原理——求路徑矩陣的方法在建立距離矩陣的同時可建立路徑矩陣R．即當k被插入任何兩點間的最短路徑時，被記錄在R(k)中，依次求時求得，可由來查找任何點對之間最短路的路徑．返回)(nR1/5/2023算法原理——求路徑矩陣的方法在建立距離矩陣的同時可建立路徑109i

j算法原理——

查找最短路路徑的方法pkp2p1p3q1q2qm則由點i到j(luò)的最短路的路徑為：返回1/5/2023ij算法原理——查找最短路路徑的方法pkp2p1p3q110算法步驟1/5/2023算法步驟12/28/2022111

TOMATLAB(road2(floyd))返回

1/5/2023TOMATLAB(road2(floyd))返回12112一、可化為最短路問題的多階段決策問題二、選址問題1．中心問題2．重心問題返回1/5/2023一、可化為最短路問題的多階段決策問題二、選址問題1113可化為最短路問題的多階段決策問題1/5/2023可化為最短路問題的多階段決策問題12/28/20221141/5/202312/28/20221151/5/202312/28/2022116返回1/5/2023返回12/28/2022117

選址問題--中心問題

TOMATLAB(road3(floyd))1/5/2023選址問題--中心問題TOMATLAB(road3118S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故應將消防站設(shè)在v3處.返回1/5/2023S(v1)=10,S(v2)=7,S(v3)=6,S(119

選址問題--重心問題返回1/5/2023選址問題--重心問題返回12/28/2022120圖論算法（２）－中國郵遞員問題和ＴＳＰ問題1/5/2023圖論算法（２）12/28/2022121郵路問題及ＴＳＰ問題一、中國郵遞員問題二、推銷員問題三、建模案例：最佳災情巡視路線（一）歐拉圖（二）中國郵遞員問題（一）哈密爾頓圖（二）推銷員問題1/5/2023郵路問題及ＴＳＰ問題一、中國郵遞員問題二、推銷員問題三、建模122

7

3

1

2

3

4

1

2

4

5

5

6

6

7

8

9割邊G的邊是割邊的充要條件是不含在G的圈中．

割邊的定義：設(shè)G連通，E(G),若從G中刪除邊后，圖G-{}不連通，則稱邊為圖G的割邊．1/5/20237312341245566123

e3

v1

v2

v3

v4e1e2e4

e5e6歐拉圖

e3

v1

v2

v3

v4

e1e

2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1歐拉道路：v1e1v2e2v3e5v1e4v4e3v3歐拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v11/5/2023e3v1v2v3v4e1e2e4e5e6歐拉圖124e3

v1

v2

v3v4e1e2e4

e5e3

v1

v2

v3v

4

e1

e2e4

e5e6歐拉圖非歐拉圖返回1/5/2023e3v1v2v3v4e1e2e4e5e3v1125中國郵遞員問題-定義1/5/2023中國郵遞員問題-定義12/28/2022126中國郵遞員問題-算法

Fleury算法基本思想：從任一點出發(fā)，每當訪問一條邊時，先要進行檢查．如果可供訪問的邊不只一條，則應選一條不是未訪問的邊集的導出子圖的割邊作為訪問邊，直到?jīng)]有邊可選擇為止.1/5/2023中國郵遞員問題-算法Fleury算法基本思想：從任127

v7e3

v1v2

v3v4e1

e2e4

e5

v5

e6e6

e7

e8

e9e101/5/2023v7e3v1v2v3v4e1e2e4e5v5128若G不是歐拉圖，則G的任何一個巡回經(jīng)過某些邊必定多于一次．解決這類問題的一般方法是：在一些點對之間引入重復邊（重復邊與它平行的邊具有相同的權(quán)），使原圖成為歐拉圖，但希望所有添加的重復邊的權(quán)的總和為最?。?/p>

1/5/2023若G不是歐拉圖，則G的任何一個巡回經(jīng)過某些邊必129v7e3v1v2v3v4e1e2e4e5v5v6e6e7e8e91/5/2023v7e3v1v2v3v4e1e2e4e5v5v6e6e7e81301/5/202312/28/2022131（３）求出G1的最小權(quán)理想匹配M，得到奇次頂點的最佳配對．1/5/2023（３）求出G1的最小權(quán)理想匹配M，得到奇次頂點的最佳配對．1132返回1/5/2023返回12/28/2022133哈密爾頓圖返回1/5/2023哈密爾頓圖返回12/28/2022134推銷員問題-定義流動推銷員需要訪問某地區(qū)的所有城鎮(zhèn)，最后回到出發(fā)點．問如何安排旅行路線使總行程最?。@就是推銷員問題．若用頂點表示城鎮(zhèn)，邊表示連接兩城鎮(zhèn)的路，邊上的權(quán)表示距離（或時間、或費用），于是推銷員問題就成為在加權(quán)圖中尋找一條經(jīng)過每個頂點至少一次的最短閉通路問題．1/5/2023推銷員問題-定義流動推銷員需要訪問某地區(qū)的所有城135定義在加權(quán)圖G=(V,E)中，（１）權(quán)最小的哈密爾頓圈稱為最佳H圈(Hamilton圈)．（２）經(jīng)過每個頂點至少一次的權(quán)最小的閉通路稱為最佳推銷員回路．一般說來，最佳哈密爾頓圈不一定是最佳推銷員回路，同樣最佳推銷員回路也不一定是最佳哈密爾頓圈．H回路，長22最佳推銷員回路，長41/5/2023定義在加權(quán)圖G=(V,E)中，一般說來，最佳哈1361/5/202312/28/2022137推銷員問題近似算法：二邊逐次修正法：1/5/2023推銷員問題近似算法：二邊逐次修正法：12/28/2022138例對以下完備圖，用二邊逐次修正法求較優(yōu)H圈．1/5/2023例對以下完備圖，用二邊逐次修正法求較優(yōu)H圈．12/28/2139返回1/5/2023返回12/28/2022140圖論算法（３）－匹配

匹配問題是運籌學的重要問題之一,也是圖論研究的重點內(nèi)容,它提供了解決“人員分配問題”和“最優(yōu)分配問題”一種新的思想.定義1.設(shè)G=<V,E>是無環(huán)圖,ME(G),M,若M中任意兩條邊都不相鄰,則稱M是圖G的一個匹配.若對圖G的任何匹配M’,均有M’<M,則稱M是圖G的最大匹配,記作’(G).定義2.設(shè)M是圖G的匹配,G中與M中的邊關(guān)聯(lián)的頂點稱為M飽和點.若圖G的頂點都是M飽和,則稱為G的完美匹配.1/5/2023圖論算法（３）－匹配匹配問題是運籌學的重要問題之141說明:(1)完美匹配是最大匹配,反之未然;(2)匹配的定義與邊的方向無關(guān),故匹配是針對無向圖而言.定義3.(可增廣路):設(shè)M是圖G的匹配,P是G的一條路,且在P中,M的邊和E(G)-M的邊交替出現(xiàn),則稱P是G的一條交錯路.若M交錯路P的兩個端點為M非飽和點,則稱P為M可增廣路.例1.求下圖G的一條交錯路和一條可增廣路.623415871/5/2023說明:(1)完美匹配是最大匹配,反之未然;623415871142匹配的幾個性質(zhì)定理定理1.設(shè)M1和M2是圖G的兩個不同匹配,由M1M2導出的G的邊導出子圖,記作H,則H的任意連通分支是下列情況之一:(1)邊在M1和M2中交錯出現(xiàn)的偶圈.(2)邊在M1和M2中交錯出現(xiàn)的路.定理2.M是圖G的最大匹配,當且僅當G中不存在M可增廣路.定義:設(shè)S是圖G的任意頂點子集,G中與S的頂點鄰接的所有頂點的集合,稱為S的鄰集,記做NG(S).1/5/2023匹配的幾個性質(zhì)定理定理1.設(shè)M1和M2是圖G的兩個不同匹配,143定理3(Hall定理,1935)設(shè)G是有二部劃分(V1,V2)的二分圖,則G含有飽和V1的每個頂點的匹配M的充要條件是,對SV1,有N(S)S.推論1具有二部劃分(V1,V2)的二分圖G有完美匹配V1=V2,且對SV1(或V2),有N(S)S.推論2.

設(shè)G是k(>0)正則二分圖,則G有完美匹配.由定理3可知,G有飽和V1的匹配M,再據(jù)V1=V2和推論1即知M是完美匹配.推論3.設(shè)G是二部劃分(V1,V2)的簡單二分圖，且V1=V2=n，若(G)n/2，則G有完美匹配.1/5/2023定理3(Hall定理,1935)設(shè)G是有二部劃分(V1,V2144定理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,V2,E>,其中V1={1,2,…,n}，V2={y1,y2,…,yn}表示這n張紙牌.i與yi之間連接的邊數(shù)等于數(shù)i在紙牌yj中出現(xiàn)的次數(shù),這樣得到的圖G是一個2-正則二分圖,因此圖G中有完美匹配,設(shè)為M={1yi1,2yi2,…,nyin}

則只要把紙牌yi1中的1朝上,yi2中的2朝上,…,yin的n朝上,這樣攤開,這樣攤開的紙牌就能使上面中1,2,…,n都出現(xiàn).1/5/202312/28/2022145例2.某工廠生產(chǎn)由6種不同顏色的紗布織成的雙色布,由該廠所生產(chǎn)的雙色布中,每一種顏色至少和其他三種顏色搭配.證明可以挑選出三種不同的雙色布,它們含有所有的6種顏色.證明:構(gòu)造圖G=<V,E>,其中V={v1,v2,v3,v4,v5,v6}表示6種顏色,工廠生產(chǎn)出一種顏色vi與vj搭配而成的雙色布邊{vi,vj}E(G).由題意知,G為簡單圖,且每個結(jié)點的度數(shù)至少為3,下證G中含有一個完美匹配.今設(shè){v1,v2}E(G),由于d(v3)≥3,所以存在一個不同于v1和v2的頂點vi(4≤i≤6),使{v3,vi}E(G),不妨設(shè)vi=4,即{v3,v4}E(G).1/5/2023例2.某工廠生產(chǎn)由6種不同顏色的紗布織成的雙色布,由該12/146

如果邊{v5,v6}E(G),由于d(v5)≥3,v1,v2,v3,v4中至少有3個頂點與v5相鄰,即v5與邊{v1,v2},{v3,v4}中的每一邊的某一個端點相鄰,不妨設(shè){v1,v5}E(G)和{v3,v5}E(G).對于頂點v6,同樣與v1,v2,v3,v4中至少3個頂點相鄰,即在v2和v4中至少有一個頂點與v6相鄰.如果{v2,v6}E(G),則邊{v1,v5},{v3,v4},{v2,v6}是G的一個完美匹配;如果{v4,v6}E(G),則{v1,v2},{v3,v5},{v4,v6}是G的一個完美匹配.綜上所述,G總存在完美匹配,完美匹配中的三條邊所對應的三種雙色布即為所求.1/5/2023如果邊{v5,v6}E(G),由于d(v5)≥3,v147最大匹配的生成算法-匈牙利算法定義1.根在x的M交錯子圖:設(shè)M是圖G的匹配,x是G中非M飽和點.G中由起點為x的M交錯路所能連接的頂點集所導出的G的導出子圖稱為根在x的M交錯子圖.定理1.設(shè)M是具有二部劃分(V1,V2)的二分圖G的匹配,xV1是非M飽和點,H是G中根在x的M交錯子圖的頂點集S=H∩V1,T=H∩V2,則:(1)TNG(S);(2)下述三條等價:(a)G中不存在以x為端點的M可增廣路;(b)x是H中唯一的非M飽和點;(c)T=NG(S),且T=S-1.(不證)1/5/2023最大匹配的生成算法-匈牙利算法定義1.根在x的M交錯子圖:148匈牙利算法基本思想:設(shè)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(