1、廣工管理運籌學第八章 圖與網絡分析第1頁，共74頁，2022年，5月20日，7點53分，星期三引例哥尼斯堡七橋問題ABCDBDAC第2頁，共74頁，2022年，5月20日，7點53分，星期三環球旅行問題：第3頁，共74頁，2022年，5月20日，7點53分，星期三環球旅行問題的解另一個著名的問題: 中國郵路問題第4頁，共74頁，2022年，5月20日，7點53分，星期三第1節 圖與網絡的基本知識圖可以用來做什么：管理當中，事物及事物間的聯系可以用圖來描述五只球隊的比賽情況甲乙丙丁戊甲乙丙丁戊ABCD工作分配問題圖已經應用于物質結構、交通、信息傳遞等的描述第5頁，共74頁，2022年，5月20日

2、，7點53分，星期三圖與網絡的基本概念（1）圖：這里討論的圖由點以及點與點間的連線構成，與平面幾何的圖不同，這里只關心圖中有多少個點，點與點間有無連線，至于點與點間的連線是直線還是曲線，點的相對位置，則是無關緊要的。第6頁，共74頁，2022年，5月20日，7點53分，星期三圖與網絡的基本概念（2）定義1 一個圖是由點集V=vi和V中的元素的無序對的一個集合E=ek所構成的二元組，記為G=(V, E)，V中的元素vi叫做頂點，E中的元素ek叫做邊v2v1v5v3v4e2e1e3e4e5e6V=v1,v2,v3,v4,v5E=e1,e2,e3,e4,e5,e6e1=(v1,v1), e2=(v1

3、,v2)例第7頁，共74頁，2022年，5月20日，7點53分，星期三圖與網絡的基本概念（3）相鄰：圖中的兩點間存在連線（邊），則稱這兩點相鄰，并稱它們是這條邊的端點；若兩條邊有公共的端點，則稱這兩條邊相鄰，并稱它們是其公共端點的關聯邊。v2v1v5v3v4e2e1e3e4e5e6相鄰相鄰邊數：m(G)=|E|頂點數：n(G)=|V|第8頁，共74頁，2022年，5月20日，7點53分，星期三圖與網絡的基本概念（4）無向邊與無向圖：若圖中任一條邊的端點無序，即(vi, vj)與(vj, vi)是同一條邊，則稱它為無向邊，此時圖稱為無向圖。有向圖：若圖中邊(vi, vj)的端點是有序的，則稱它是

4、有向邊（或弧），vi與vj分別稱為這條有向邊的始點和終點，相應的圖稱為有向圖。第9頁，共74頁，2022年，5月20日，7點53分，星期三圖與網絡的基本概念（5）v2v1v5v3v4e2e1e3e4e5e6環(自回路)多重邊定義2 不含環和多重邊的圖稱為簡單圖。含多重邊的圖稱為多重圖。簡單圖第10頁，共74頁，2022年，5月20日，7點53分，星期三圖與網絡的基本概念（6）定義3 每一對頂點間都有邊相連的無向簡單圖稱為無向完全圖；有向完全圖是指每一對頂點間有且僅有一條有向邊的簡單圖。完全圖頂點數n與邊數m間成立如下關系:m=n(n-1)/2第11頁，共74頁，2022年，5月20日，7點53

5、分，星期三圖與網絡的基本概念（7）定義4 圖G=(V, E)的點集V可以分為兩個非空子集X，Y，即X Y =V，X Y=，使得E中的每條邊的兩個端點中必有一個屬于X，另一個屬于Y，則稱G為二部圖（偶圖），有時記為G=(X, Y, E)二部圖非二部圖第12頁，共74頁，2022年，5月20日，7點53分，星期三圖與網絡的基本概念（8）定義5 以v為端點的邊數，叫做點v的次(degree)，記作deg(v), 或簡記為d(v)。v2v1v5v3v4e2e1e3e4e5e6d(v1)=4d(v2)=3懸掛點孤立點懸掛邊偶點奇點第13頁，共74頁，2022年，5月20日，7點53分，星期三圖中頂點次的

6、性質定理1 任何圖中頂點次數的總和等于邊數的2倍。定理2 任何圖中次為奇數的頂點必有偶數個。定義6 在有向圖中，以頂點v為始點的邊數稱為頂點v的出次，記為d+(v)；以v為終點的邊數稱為v的入次，記為d-(v)。頂點v的出次與入次的和稱為點v的次。第14頁，共74頁，2022年，5月20日，7點53分，星期三圖與網絡的基本概念（9）定義7 圖G=(V, E), 若E是E的子集，若V是V的子集，且E中的邊僅與V中的頂點相關聯，則稱G = (V, E)為圖G的一個子圖，特別地，若V =V, 則稱G為G的一個生成子圖（支撐子圖）。子圖生成子圖第15頁，共74頁，2022年，5月20日，7點53分，星

7、期三圖與網絡的基本概念（10）有時需要用圖來表示事物及事物之間的定量的聯系，這時圖中除了頂點與邊外，還有與點或邊有關的某些數量指標，常稱它們為“權”，權在圖中可以表示距離、費用、通過能力等。這種點或邊帶權的圖稱為網絡（或賦權圖）313112785342516第16頁，共74頁，2022年，5月20日，7點53分，星期三連通圖（1）定義8 無向圖中一個點、邊交錯的序列，序列中的第一個和最后一個元素都是點，若其中每條邊以序列中位于它之前和之后的點為端點，則稱這個點邊序列為圖中連接其第一個點與最后一個點的鏈。鏈中所含的邊數稱為鏈長。鏈，但只是簡單鏈而非初等鏈簡單鏈：沒有重復邊；初等鏈：既無重復邊也無

8、重復點。對有向圖可類似定義鏈，如果各邊的方向一致，則稱為道路。第17頁，共74頁，2022年，5月20日，7點53分，星期三連通圖（2）定義9 若在無向圖中，一條鏈的第一個點與最后一個點重合，則稱這條鏈為圈。只有重復點而無重復邊的圈為簡單圈，既無重復點又無重復邊的圈為初等圈。初等圈非簡單的圈第18頁，共74頁，2022年，5月20日，7點53分，星期三連通圖（3）有向圖無向圖道路鏈（或道路）回路圈（或回路）道路(邊的方向一致)不是道路第19頁，共74頁，2022年，5月20日，7點53分，星期三連通圖（4）定義10 一個圖中任意兩點間至少有一條鏈相連，則稱此圖為連通圖。任何一個不連通圖總可以分

9、為若干個連通子圖，每一個稱為原圖的一個分圖（連通分支）。連通圖非連通圖第20頁，共74頁，2022年，5月20日，7點53分，星期三圖的矩陣表示鄰接矩陣對于圖G=(V, E), |V|=n, 構造一個矩陣A=(aij)nn, 其中： v1v2v3v4v5v6第21頁，共74頁，2022年，5月20日，7點53分，星期三圖的矩陣表示權矩陣對于網絡（賦權圖）G=(V, E), |V|=n, 其中邊(vi, vj)上有權wij，構造一個矩陣A=(aij)nn, 其中： 342516v1v2v3v4第22頁，共74頁，2022年，5月20日，7點53分，星期三歐拉回路（1）定義13 連通圖G中，若存在

10、一條道路，經過每邊一次且僅一次，則稱這條道路為歐拉道路。若存在一條回路經過每邊一次也僅一次，則稱這條回路為歐拉回路。具有歐拉回路的圖稱為歐拉圖（E圖）。定理3 無向連通圖G是歐拉圖，當且僅當G中無奇點第23頁，共74頁，2022年，5月20日，7點53分，星期三歐拉回路（2）推論1 無向連通圖G為歐拉圖，當且僅當G的邊集可以劃分為若干個初等回路。推論2 無向連通圖G中有歐拉道路，當且僅當G中恰好有兩個奇點。ABCD哥尼斯堡七橋問題無解一筆畫問題第24頁，共74頁，2022年，5月20日，7點53分，星期三歐拉回路（3）定理4 連通有向圖G是歐拉圖，當且僅當它的每個頂點的出次等于入次。連通有向圖

11、G有歐拉道路，當且僅當這個圖中除了兩個頂點外，其余每個頂點的出次等于入次，且這兩個頂點中，一個頂點的入次比出次多1，另一個的入次比出次少1。v1v2v3v4v5v6第25頁，共74頁，2022年，5月20日，7點53分，星期三中國郵路問題一個郵遞員，負責某一地區的信件投遞，他每天要走郵局出發，走遍該地區所有街道，再返回郵局，問應如何安排送信的路線可以使所走的總路程最短？用圖論的語言描述就是：給定一個連通圖G，每邊有非負權l(e)，要求一條回路過每邊至少一次，且滿足總權最小。第26頁，共74頁，2022年，5月20日，7點53分，星期三中國郵路問題解法（1）若G是歐拉圖，則按歐拉回路走，就是滿足

12、要求的經過每邊至少一次且總權最小的走法。abcdef若G中有奇點，則G不是歐拉圖，因此要連續地走過每邊至少一次，則必然有某些邊不止一次走過。這相當于在G中添加一些重復的邊，使得到的新圖G*沒有奇點且滿足總路程最短。第27頁，共74頁，2022年，5月20日，7點53分，星期三中國郵路問題解法（2）abcdefabcdef對增加了重復邊后得到的新圖G*，很明顯其總權的大小取決于增加的重復邊權的大小。因此中國郵路問題轉化為如下問題：在連通圖G=(V, E)中，求一個邊的集合E1E，將E1中所有邊都變成重復邊得到新圖G*，使得G*中無奇點，且 最小第28頁，共74頁，2022年，5月20日，7點53

13、分，星期三中國郵路問題解法（3）上述問題的解決依賴于以下結果：定理5 已知圖G*=G+E1無奇點，則最小的充分必要條件為：（1）每條邊最多重復一次；（2）對圖G中的每個初等圈來說，重復邊的長度不超過圈長的一半。第29頁，共74頁，2022年，5月20日，7點53分，星期三中國郵路問題解法（4）下面直觀地說明，若定理5的條件不成立，則可以得到總權比E1的更小的重復邊集。122254122254重復兩次或以上的去掉其中兩條將原來的重復邊變成非重復邊，原來的非重復邊變成重復邊第30頁，共74頁，2022年，5月20日，7點53分，星期三中國郵路問題解法（5）解法第一步：確定初始可行方案。若圖中沒有奇

14、點，則它已經是歐拉圖，按歐拉回路走即可。否則，若有奇點，奇點必有偶數個，將奇點兩兩配對，然后找出每對奇點間的一條道路，將此道路中的每條邊都變成重復邊。524363459444第31頁，共74頁，2022年，5月20日，7點53分，星期三中國郵路問題解法（6）524363459444第二步：調整可行方案。使重復邊最多重復一次524363459444第32頁，共74頁，2022年，5月20日，7點53分，星期三中國郵路問題解法（7）524363459444第三步：檢查圖中每個初等圈是否滿足定理條件（2），若不滿足則進行調整。524363459444524363459444第33頁，共74頁，202

15、2年，5月20日，7點53分，星期三第三步要求檢查每個初等圈，這一步可能是相當繁瑣的。例如上例中的圖就包括下圖所示的初等圈。第34頁，共74頁，2022年，5月20日，7點53分，星期三樹樹的概念定義14 連通且不含圈的無向圖稱為樹。樹中次為1的點稱為樹葉，次大于1的點稱為分枝點。ABCDEFGHIJKLMN廠長人事科財務科總工程師生產副廠長新產品開發科技術科生產科設備科供應科動力科經營副廠長銷售科檢驗科第35頁，共74頁，2022年，5月20日，7點53分，星期三樹樹的性質定理6 T=(V, E), |V|=n, |E|=m, 則下列關于樹的說法是等價的。（1）T是一個樹（即T是不含圈的連通

16、圖）第36頁，共74頁，2022年，5月20日，7點53分，星期三樹樹的性質（2）T無圈，且m=n-1第37頁，共74頁，2022年，5月20日，7點53分，星期三樹樹的性質（3）T連通，且m=n-1第38頁，共74頁，2022年，5月20日，7點53分，星期三樹樹的性質（4）T無圈，但每加一新邊就得到唯一的一個圈T是邊數最多的無圈圖第39頁，共74頁，2022年，5月20日，7點53分，星期三樹樹的性質（5）T連通，但任舍去一邊就不連通T是邊數最少的連通圖第40頁，共74頁，2022年，5月20日，7點53分，星期三樹樹的性質（6）T中任意兩點有唯一一條鏈相連第41頁，共74頁，2022年，

17、5月20日，7點53分，星期三生成樹概念定義15 若圖G的生成子圖是一棵樹，則稱該樹為圖G的生成樹（支撐樹），或簡稱為圖G的樹。定理7 圖G有生成樹的充分必要條件是圖G是連通的第42頁，共74頁，2022年，5月20日，7點53分，星期三生成樹解法（1）避圈法這種方法是每步從連通圖中選出一條邊，使得它與已經選出的邊不構成圈，直到選夠n-1條邊為止。一個圖的生成樹不是唯一的。第43頁，共74頁，2022年，5月20日，7點53分，星期三避圈法的另一種表述先去掉圖G中所有邊，只留下點，每次任意放回一條邊，使之與已經放回的邊不構成圈，反復進行，直到有（n-1）條邊為止。5個頂點，4條邊第44頁，共7

18、4頁，2022年，5月20日，7點53分，星期三生成樹解法（2）破圈法這種方法是每步從連通圖中選一個圈，并去掉該圈的一條邊，直到圖中不含圈為止。第45頁，共74頁，2022年，5月20日，7點53分，星期三另一種解法第46頁，共74頁，2022年，5月20日，7點53分，星期三最小生成樹概念定義16 連通圖G=(V, E), 每條邊上有非負權L(e)，一棵生成樹上各邊的權之和，稱為這棵生成樹的權，具有最小權的生成樹，稱為最小生成樹（最小支撐樹），簡稱最小樹。例如 如何用造價最省的電話線網將各有關單位連起來的問題，就歸結為求最小生成樹的問題。354367124非最小樹第47頁，共74頁，2022

19、年，5月20日，7點53分，星期三最小生成樹解法1（Kruskal算法）避圈法：這種方法每步從圖中挑選一條邊，滿足：（1）它與已經選出的邊不構成圈；（2）它是滿足條件（1）的權最小的邊，直到選夠n-1條邊為止。141213144553245214121314455324529個頂點，8條邊第48頁，共74頁，2022年，5月20日，7點53分，星期三避圈法另一種表述先去掉圖G的所有邊，只留下頂點，每次放回一條權最小的邊，使之與已經放回的邊不構成圈，反復進行，直到有（n-1）條邊為止。9482333791423316個頂點，5條邊第49頁，共74頁，2022年，5月20日，7點53分，星期三最小

20、生成樹解法（2）破圈法：這種方法每步從圖中任選一個圈，然后去掉該圈中權最大的邊，直到圖中沒有圈為止。14121314455324529個頂點，8條邊第50頁，共74頁，2022年，5月20日，7點53分，星期三破圈法舉例948233379194823337916個頂點，5條邊第51頁，共74頁，2022年，5月20日，7點53分，星期三破圈法舉例v4v2v3v16215846最小生成樹的權= 9/v4v2v3v1621546v4v2v3v162154/v4v2v3v16214/v4v2v3v1621第52頁，共74頁，2022年，5月20日，7點53分，星期三根樹定義17 若一個有向圖在不考慮

21、邊的方向時是一顆樹，則稱這個圖是有向樹。定義18 若有向樹T恰有一個頂點的入次為0，其余頂點的入次為1，則稱T為根樹有向樹根樹葉根分枝點第53頁，共74頁，2022年，5月20日，7點53分，星期三根樹的應用根樹常用來表示指揮系統上下級的隸屬關系，系統的分類、溯源與繼承等關系。如管理系統的組織結構，家族譜系，計算機文件目錄結構，數據結構等等。第54頁，共74頁，2022年，5月20日，7點53分，星期三二叉樹定義19 在根樹中，若每個頂點的出次小于或等于m，稱這棵樹為m叉樹。若每個頂點的出次恰好等于m或0，則稱它為完全m叉樹。當上述的m=2時，該樹分別稱為二叉樹、完全二叉樹。三叉樹完全二叉樹第

22、55頁，共74頁，2022年，5月20日，7點53分，星期三最優二叉樹（霍夫曼樹）實際問題中常需用到葉子上帶權的二叉樹，如信息處理中的最優檢索、數據結構等問題。令有s個葉子的二叉樹T各個葉子的權分別為pi，根到各葉子的距離（層次，即根到葉子的邊數）為li (i=1, 2, , s)，則二叉樹的總權數為滿足總權最小的二叉樹稱為最優二叉樹，也稱為霍夫曼樹。第56頁，共74頁，2022年，5月20日，7點53分，星期三霍夫曼算法步驟：（1）將s個葉子按權由小到大排列，不失一般性，設p1p2 ps（2）將二個具有最小權的葉子合并成一個分枝點。然后令ss-1, 若s=1停止，否則轉（1）。第57頁，共7

23、4頁，2022年，5月20日，7點53分，星期三1223343122334351223343596122334359615例 s=6，權分別為4, 3, 3, 2, 2, 1. 構造最小二叉樹。按霍夫曼算法構造最優二叉樹如下：總權為：14+2 4+2 3+4 2+3 2+3 2=38第58頁，共74頁，2022年，5月20日，7點53分，星期三例 最優檢索（p270）510152050CDEBA153050100A?B?E?D?ABEDCYYYYNNNN最優二叉樹最優檢索流程m（T*）= 54 + 10 4 + 15 3 + 20 2 + 50 1 = 195第59頁，共74頁，2022年，5

24、月20日，7點53分，星期三最短路問題最短路問題是網絡理論中應用最廣泛的問題之一，許多優化問題，如設備更新、管道鋪設、線路安排等都可以化為最短路問題求解。最短路問題的提法：設G=(V, E)為連通圖，圖中的各邊(vi, vj)有非負權lij (lij=表示vi, vj間無邊), vs, vt是圖中任意兩點，求一條道路，使它是從vs到vt的所有道路中總權最小的道路。第60頁，共74頁，2022年，5月20日，7點53分，星期三Dijkstra算法原理：若(vs, v1, , vn-1, vn)是vs到vn的最短路，則(vs, v1, , vn-1)是vs到vn-1的最短路。思路：采用標號法。使用

25、兩種標號，T標號和P標號，一個點的P標號是永久性標號，表示起點到該點最短路的權，它一旦給出就不再改變；而點的T標號是臨時性的標號，表示對起點到該點最短路的權的估計值，當得到更精確的估計值時要修改原來的T標號，此外算法的每一步要把某一個點的T標號改成P標號，當得到終點vt的P標號時算法結束。第61頁，共74頁，2022年，5月20日，7點53分，星期三Dijkstra算法步驟第一步：給vs點P標號P(vs )=0, 其余點T標號T(vi)=+ 第二步：若vi為剛獲得P標號的點，則修改以vi為起點的各邊終點的T標號為下兩個數中的較小者：一個是vi的P標號與該邊權之和，另一個是該終點原來的T標號。第

26、三步：取所有具有T標號的點中T標號值最小的點，將其T標號改為P標號。若本次得到P標號的點為終點，算法終止，否則返回上一步。第62頁，共74頁，2022年，5月20日，7點53分，星期三例（p251）465447796554104654477965541046給起點P標號0，其余點T標號（在下面的求解過程中，粉色的數字為P標號）修改以剛獲得P標號的點為起點的邊的終點的T標號；然后將最小的T標號改成P標號第63頁，共74頁，2022年，5月20日，7點53分，星期三465447796554104968465447796554104968第64頁，共74頁，2022年，5月20日，7點53分，星期三4654477965541049681314465447796554104968131417第65頁，共74頁，2022年，5月20日，7點53分，星期三465447796554104968131415465447796554104968131415最短路線見圖第66頁，共74頁，2022年，5月20日，7點53分，星期三v1v2v3v4v6v5v7v838422433123340T(v2)=min(,0+4)=4, T(v3)=min(,0+8)=8黃色數字表示P標號最短路問題舉例第67頁，共74頁，2022年，5月20日，7點53分，星