1、2022/7/281圖與網(wǎng)絡(luò)模型北京大學(xué)光華管理學(xué)院藍(lán)穎杰 2022/7/282內(nèi)容提要1. 圖與網(wǎng)絡(luò)的基本概念2. 最小生成樹問題3. 最短路問題的Dijkstra算法4. 旅行商（TSP）問題第一個(gè)實(shí)例5個(gè)人之間的往來關(guān)系：1與2，3與4，4與5 相互往來12354點(diǎn)邊實(shí)體關(guān)系關(guān)系對(duì)稱關(guān)系不對(duì)稱關(guān)系和文字描述比較，圖有何優(yōu)點(diǎn)？第二個(gè)實(shí)例5個(gè)人之間認(rèn)識(shí)關(guān)系：1與2，3與4，4與5 相互認(rèn)識(shí)；1認(rèn)識(shí)3，3認(rèn)識(shí)5，5認(rèn)識(shí)2，4認(rèn)識(shí)2。12354誰最愛交際？誰最有名氣？用帶箭頭的弧來表示不對(duì)稱關(guān)系。用一對(duì)弧來代替原來的一條邊。圖的小結(jié)：實(shí)體與關(guān)系點(diǎn)：表示實(shí)體、事物、對(duì)象等對(duì)稱關(guān)系用“邊”表示（無箭

2、頭為邊）不對(duì)稱關(guān)系用“弧”表示（有箭頭為?。├纾河没『忘c(diǎn)表示主謂賓起點(diǎn)為主語，弧為謂語，終點(diǎn)為賓語對(duì)稱關(guān)系：兩個(gè)對(duì)稱的“不對(duì)稱關(guān)系”組合1、2相互認(rèn)識(shí)：1認(rèn)識(shí)2、2認(rèn)識(shí)1所以：一條邊 = 兩條方向相反的對(duì)稱弧無向圖與有向圖無向圖：由點(diǎn)和邊構(gòu)成G=(V, E)鏈與圈鏈：點(diǎn)序及順序相連的邊圈：起點(diǎn)與終點(diǎn)相同的鏈點(diǎn)的度；奇點(diǎn)，偶點(diǎn)；有向圖：由點(diǎn)和弧構(gòu)成D=(V,A)路與回路點(diǎn)的入度和出度有向圖更一般12354123542022/7/287簡(jiǎn)單的圖：環(huán)與重邊簡(jiǎn)單圖：無環(huán)，無重邊環(huán)：兩端點(diǎn)為同一點(diǎn)的邊重邊：兩點(diǎn)間有多條邊相連多重圖：無環(huán)，有重邊哥尼斯堡七橋問題： 能否在一次散步中經(jīng)過每座橋恰好一次？哥

3、尼斯堡七橋問題1。嘗試散步路線2。記錄路線(必要的信息/數(shù)據(jù),精簡(jiǎn)問題)3。從流的角度看,成功路線有何特點(diǎn)?思考題:試建一個(gè)整數(shù)規(guī)劃,回答該問題?哈密爾頓回路問題歐拉回路: 經(jīng)過每條邊恰好一次. 提出：1736年。解決：歐拉。歐拉圖：有歐拉回路的圖判斷存在性：非常簡(jiǎn)單哈密爾頓回路: 經(jīng)過每個(gè)頂點(diǎn)恰好一次.提出: 1857年,哈密爾頓. 正12面體, 20名城判斷存在性: plete (最難的一類問題)旅行商(貨郎擔(dān))問題: 最短的回路(邊有長(zhǎng)短)應(yīng)用: 快遞、配送的線路規(guī)劃最常見的圖：樹連通的概念：兩點(diǎn)的連通：如果它們之間有鏈。連通圖：圖中任意兩點(diǎn)都是連通的。樹：無圈的連通圖；邊數(shù)最少的連通圖

4、；邊數(shù)最多的無圈圖。（美：增減不得，恰到好處）特點(diǎn)：無圈，連通圖，邊數(shù)點(diǎn)數(shù)1以上三特點(diǎn)，任何兩個(gè)成立第三個(gè)也成立下面的圖是樹嗎？若不是，如何變成樹？12354網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)：賦權(quán)圖給每條邊或弧賦予權(quán)重可表示長(zhǎng)度、容量、費(fèi)用、收入等例子：運(yùn)輸問題、指派問題、最小費(fèi)用流問題、最短路問題、最大流問題、最小費(fèi)用最大流問題網(wǎng)絡(luò)規(guī)劃的廣泛應(yīng)用網(wǎng)絡(luò)是一種直觀有效的模型一些問題有特殊的計(jì)算方法：網(wǎng)絡(luò)單純型法應(yīng)用問題：生產(chǎn)、運(yùn)輸、分配、項(xiàng)目計(jì)劃、網(wǎng)絡(luò)搭建、廠址選擇、資源管理、財(cái)務(wù)策劃等 2.最小支撐樹摩登公司鋪光纜問題摩登公司共有7個(gè)中心，鋪設(shè)光纜的費(fèi)用如圖所示P264，7.5節(jié)該如何鋪設(shè)光纖，既能保證通訊，又能

5、節(jié)省費(fèi)用？ABCED2144735FG52417問題的分析保證通訊（可行）：任意兩點(diǎn)之間必須連通何時(shí)可以“砍掉”某條邊而不影響連通性？有圈的時(shí)候。因此最節(jié)省的方案中必然無圈我們考慮的方案：連通無圈樹！這樣的樹我們稱為該圖的“支撐樹”這樹把所有的頂點(diǎn)都“支撐”起來了。如果它是唯一的，那必然就是最優(yōu)方案了任何一個(gè)圖只有唯一的支撐樹嗎？問題的精簡(jiǎn)表述：尋找總費(fèi)用最小的支撐樹總費(fèi)用最小的支撐樹簡(jiǎn)稱為“最小支撐樹”最小支撐樹算法（1）最小支撐樹（貪心算法）破圈法在原來圖中，找到任意一個(gè)圈，去掉圈上最長(zhǎng)的邊。ABCED2144735FG52417去掉的邊用X劃掉圈BCE，去7圈EFG，去7圈ABC，去5圈

6、CEF，去4圈CDF，去4圈ABCD，去4無圈，完成剩余邊用紅色標(biāo)出解決方法之（2）考慮選擇哪些邊搭建光纖形成支撐樹如果逐條的選擇：逐步增加邊而避免形成圈問題是：如何增加邊而使總費(fèi)用最小？ABCED2144735FG524175：EG最小支撐樹算法（2）最小支撐樹（貪心算法）避圈法在不形成圈的前提下，按從小到大的順序依次加入邊。選中6條邊，完成。結(jié)果與破圈法相同ABCED2144735FG52417進(jìn)入順序(權(quán)數(shù)遞增)1：CD1：EF2：AB2: BC3: CF4:成圈，不進(jìn)最小支撐樹是否唯一？舉例?2022/7/28183. 最短路問題對(duì)于賦權(quán)（ cij ）的有向圖，求其中一點(diǎn)（起點(diǎn)S）到另

7、一點(diǎn)（終點(diǎn)T）的最短路徑。兩點(diǎn)間最短路的長(zhǎng)度稱為這兩點(diǎn)間的距離。圖例：S=1,T=6,求點(diǎn)1到點(diǎn)6的最短路12354761191513643消息傳遞與Dijkstra算法古代城邦制的時(shí)候，某城若發(fā)生重要事情，消息靠傳信官傳達(dá)。發(fā)生事情的城市同時(shí)向鄰近的城市派遣傳信官。每個(gè)城市在第一次收到消息的時(shí)候必向其下游鄰近的所有城市同時(shí)派遣傳信官，以確保各城市在最早時(shí)刻獲得消息。模擬這個(gè)過程的關(guān)鍵：首次獲得時(shí)派遣; 判斷首次必須考慮所有在首次獲得消息前出發(fā)的傳信官因此必須先確定在前面先獲得消息的所有城市Dijkstra算法逐步確定下一個(gè)獲得消息的城市。隨時(shí)間流逝，跟據(jù)在路上的傳信官，計(jì)算下一個(gè)首先獲得消息

8、的城市。接下來首先獲得消息的可能不唯一。時(shí)間繼續(xù)流逝：首次獲得消息的城市傳信官出發(fā)。2022/7/28192022/7/2820求解最短路問題示例用Dijkstra算法求點(diǎn)1到點(diǎn)6的最短路。1235476119151364370617,321,3197,16,116,21620,219,52022/7/2821求最短路的 Dijkstra 算法1）初始化：給起點(diǎn)S永久標(biāo)號(hào)，標(biāo)值為0；其它點(diǎn)給臨時(shí)標(biāo)號(hào)，標(biāo)值為無窮。（此時(shí)集合P=S）2）調(diào)標(biāo)值：從剛得到永久標(biāo)號(hào)的點(diǎn)k(標(biāo)值為 yk)出發(fā)能直接到達(dá)的臨時(shí)標(biāo)號(hào)的點(diǎn)，如點(diǎn)j(臨時(shí)標(biāo)值為xj)，若 yk + ckj xj ，則調(diào)整臨時(shí)標(biāo)值為 xj yk

9、+ ckj （這時(shí)命j點(diǎn)的“前點(diǎn)”為k點(diǎn)）3）標(biāo)永久：從所有的臨時(shí)標(biāo)號(hào)的點(diǎn)中，選取標(biāo)值最小的，記為k，變成永久標(biāo)號(hào)。（此時(shí)集合P = Pk）4）判終止：若T沒有得到永久標(biāo)號(hào)，返回（2）；否則，T的永久標(biāo)值即最短路長(zhǎng)，追朔前點(diǎn)可得最短路。Edsger Wybe DijkstraBorn May 11, 1930Rotterdam,NetherlandsDied August 6, 2002(aged72)Nuenen,NetherlandsFields Computer science2022/7/28222022/7/2823最長(zhǎng)路問題最短路問題容易求解，但最長(zhǎng)路是NP-hard。整數(shù)規(guī)劃：若

10、沒有回路：最短路模型的目標(biāo)函數(shù)中MIN改MAX。約束條件不變。Done。若有回路：還要加約束禁止出現(xiàn)回路方法1：對(duì)每一個(gè)可能的回路，設(shè)一個(gè)約束。缺點(diǎn)：回路的數(shù)目可能極其多方法2：對(duì)每個(gè)點(diǎn)設(shè)置變量，表示訪問序數(shù)Ui: 第i點(diǎn)的訪問序數(shù)。如果路線中點(diǎn)j是點(diǎn)i的下一個(gè)，則必須 Ui + 1 Uj。當(dāng)Xi,j=1時(shí)，約束Ui + 1 Uj成立。否則該約束不要求成立。不允許重復(fù)訪問點(diǎn)。若只不允許重復(fù)訪問邊呢？2022/7/28244. 旅行商問題（TSP）經(jīng)過各點(diǎn)恰好一次的最短回路。建立模型的考慮：變量：Xi,j是否從點(diǎn)i到點(diǎn)j每個(gè)點(diǎn)恰好進(jìn)入一次每個(gè)點(diǎn)恰好離開一次滿足上述條件還不夠！2022/7/282

11、5TSP-IP模型(1)G=（V，A）的頂點(diǎn)數(shù)|V|=n：模型有2n+2n-1個(gè)約束第二類約束保證在任何S（V的真子集）內(nèi)部都沒有哈密爾頓回路。這與最長(zhǎng)路中的方法1類似。2022/7/2826TSP-IP模型（2）從點(diǎn)1出發(fā)（可隨意選），確定從1出發(fā)的訪問次序（從不同的角度描述方案）。目的：幫助排除小圈。對(duì)標(biāo)號(hào)為i=2到n的點(diǎn),設(shè)訪問順序號(hào)Ui(0到n-2).IP模型的約束個(gè)數(shù)：2n + (n-1)(n-2)2022/7/2827作 業(yè)求圖中最小支撐樹，注意給出演算步驟1。用破圈法；2。用避圈法用Dijkstra方法求解從O到G的最短路，在圖上標(biāo)號(hào)計(jì)算，如課堂演示。下周二前Email提交： 主題：HW6#姓名#學(xué)號(hào)Dijkstra算法討論任一最短路的任何一個(gè)部分都是最短路！從S到j(luò)點(diǎn)的最短路到達(dá)j點(diǎn)前的那點(diǎn)稱為j點(diǎn)的“前點(diǎn)”。到前點(diǎn)的距離 到j(luò)點(diǎn)的距離 （弧長(zhǎng)非負(fù)）對(duì)于任意非負(fù)的d，和S的距離d的所有點(diǎn)的集合設(shè)為P(d), 而V(d)是P(d)的補(bǔ)集。A(d)= (i,j): i P(d), j V(d),有點(diǎn)象截集任何到達(dá)V(d)的最短路必然經(jīng)過A(d)中的弧因?yàn)閺腟出發(fā)沿該最短路前進(jìn)，距離逐步增加2022/7/2828Dijkstra