第一節：引論第二節：圖的基本概念第三節：樹圖第四節：最短路問題第五節：最大流問題第六節：中國郵路問題第七節：網絡計劃第九章圖與網絡計劃編輯ppt圖論編輯ppt引論1.Euler回路問題2.Ramsey問題編輯ppt近代圖論的歷史可追溯到18世紀的七橋問題—穿過K?nigsberg城的七座橋，要求每座橋通過一次且僅通過一次。這就是著名的“哥尼斯堡7橋”難題。Euler1736年證明了不可能存在這樣的路線。圖的基本概念與模型K?nigsberg橋對應的圖編輯pptEuler回路問題Pregel“哥尼斯堡7橋”難題最終在1736年由數學家Euler的一篇論文給予了完滿的解決，這是圖論的第一篇論文。在后來的兩百年間圖論的發展是緩慢的，直到1936年匈牙利數學家O.K?nig寫出了圖論的第一本專著《有限圖與無限圖的理論》。編輯ppt四色猜想圖論的歷史上最具有傳奇色彩的問題也許要數著名的“四色猜想”了——歷史上許許多多數學猜想之一。世界近代三大數學難題：費馬最后猜想、哥德巴赫猜想和“四色”猜想。它描述對一張地圖著色的問題，在一維直線上用兩種顏色可以區分任意多不同線段，在二維平面內至少需要四種顏色可以區分任意多區域（當然最簡單的情況是二色，如國際象棋棋盤）；在三維空間內至少需要八種顏色可以區分任意多的立體，（最簡單的情況還是二色，如NaCl）編輯pptEuler回路問題

ACDB編輯pptRamsey問題

vjvtvkvi編輯ppt

vjvtvkRamsey問題vi編輯ppt

vjvtvkRamsey問題vi編輯ppt

vjvtvkRamsey問題vi編輯ppt第一節：圖的基本概念1.圖的概念2.關聯的概念3.簡單圖、完全圖和二分圖4.連通與回路5.部分圖與子圖編輯ppt1.圖的概念（1）圖：圖是點和邊的集合，記作

G=（V，E）；其中V是點的集合，E是邊的集合。（2）有向圖：有向圖是點和弧的集合，記作G=（V，U）；U是弧的集合，弧是兩點的有序偶對。（3）賦權圖：圖中的每一條邊均有一個權數wij相對應的圖稱為賦權圖。編輯ppt圖的基本概念(v1)趙(v2)錢孫(v3)李(v4)周(v5)吳(v6)陳(v7)e2e1e3e4e5(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e5可見圖論中的圖與幾何圖、工程圖是不一樣的。例如：在一個人群中，對相互認識這個關系我們可以用圖來表示。編輯ppt1.圖的概念298653圖有向圖賦權圖編輯ppt2.關聯的概念端點和關聯邊：若有邊e可表示為e=(vi,vj),則稱vi和vj為邊e的兩個端點；邊e為vi和vj的關聯邊。(2)相鄰：若點vi和vj與同一條邊相關聯，則稱vi和vj相鄰；若邊ei和ej具有一個公共的端點，則稱ei和ej相鄰。(3)環：若邊ei的兩個端點相互重合，則稱ei為環。編輯ppt如圖9-5中，v2和v5是邊e4的兩個端點，e4為v2和v5的關聯邊；v2和v5是邊e4的兩個端點，邊e8是v4和v5的關聯邊。圖9-5v1e2e4v2e6e5v3e7v4v5e3e1e8編輯pptv4和v5均與e8相關聯，所以v4和v5相鄰。e6和e7有一個公共的端點v3

，e6和e7相鄰。e1即為一個環

圖9-5v1e2e4v2e6e5v3e7v4v5e3e1e8編輯ppt2.關聯的概念(4)多重邊：若vi,和vj兩點之間有兩條或兩條以上的邊存在,則稱vi,和vj兩點之間有多重邊。(5)點的度（或次）：與點vi相關聯的邊的數量稱為點vi的度（或次）；度（或次）為偶數的點稱為偶點，度（或次）為奇數的點稱為奇點；度（或次）為1的點稱為懸掛點；度（或次）為0的點稱為孤立點。圖的度:

一個圖的度等于各點的度之和。v3e7e4e8e5e6e1e2e3v1v2v4v5編輯pptv2和v5之間存在e4和e5二條邊，所以稱v2和v5之間具有二重邊d(v1)=4、d(v2)=4、d(v5)=5、d(v4)=1。v5和v4為奇點,v4為懸掛點,v1、v2、v3為偶點圖9-5v1e2e4v2e6e5v3e7v4v5e3e1e8編輯ppt2.關聯的概念圖9-5v1e2e4v2e6e5v3e7v4v5e3e1e8定理1任何圖中，頂點度數之和等于所有邊數的2倍。定理2任何圖中，度為奇數的頂點必為偶數個。編輯ppt3.簡單圖、完全圖和二分圖(1)簡單圖：無環無多重邊的圖稱為簡單圖。(2)完全圖：任意一對頂點均相鄰的簡單圖稱為完全圖。(3)二分圖：若圖的點集V能被分成二個不相交的子集V1和V2，使得同一個集合中的任何兩點均不相鄰，則稱此圖為二分圖。編輯ppt簡單圖、完全圖和二分圖簡單圖二分圖完全圖編輯ppt圖的基本概念二分圖（偶圖）圖G=(V,E)的點集V可以分為兩各非空子集X，Y，集X∪Y=V,X∩Y=?,使得同一集合中任意兩個頂點均不相鄰，稱這樣的圖為偶圖。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明顯為二分圖，(b)也是二分圖，但不明顯，改畫為(c)時可以清楚看出。編輯ppt4.連通與回路(1)鏈：鏈是相關聯的點和邊的交替序列；邊不重復的鏈稱為簡單鏈；邊和點均不重復的鏈稱為初等鏈。(2)連通：任意一對頂點之間均有鏈相連的圖稱為連通圖。(3)回路：鏈的首尾重合便構成了回路；簡單鏈的首尾重合便構成了簡單回路；初等鏈的首尾重合便構成了初等回路。編輯ppt4.連通與回路e5v1v5v4v3v2e1e4e3e2e6e8v4到v5的一條鏈：v4–e6-v2-e2-v1-e3-v3-e5-v2-e2-v1-e1-v1-e3-v3-e8-v5v4到v5的一條簡單鏈：v4–e6-v2-e2-v1-e3-v3-e5-v2–e4-v3-e8-v5v4到v5的一條初等鏈：v4–e6-v2-e2-v1-e3-v3-e8-v5編輯ppt5.部分圖與子圖(1)部分圖：圖G1=（V1，E1）和圖G2=（V2，E2），若存在V1=V2、E1E2，則稱G1為G2的部分圖。(2)子圖：圖G1=（V1，E1）和圖G2=（V2，E2），若存在V1V2、E1E2，則稱G1為G2的子圖。編輯ppt5.部分圖與子圖圖子圖部分圖編輯ppt圖的基本概念與模型圖的模型應用例9.1有甲,乙,丙,丁,戊,己6名運動員報名參加A,B,C,D,E,F6個項目的比賽。下表中打√的是各運動員報告參加的比賽項目。問6個項目的比賽順序應如何安排，做到每名運動員都不連續地參加兩項比賽。ABCDEF甲√√√乙√√√丙√√丁√√戊√√√己√√√編輯ppt圖的基本概念與模型解：用圖來建模。把比賽項目作為研究對象，用點表示。如果2個項目有同一名運動員參加，在代表這兩個項目的點之間連一條線，可得下圖。ABCDEF在圖中找到一個點序列，使得依次排列的兩點不相鄰，即能滿足要求。如：1)A,C,B,F,E,D2)D,E,F,B,C,A編輯ppt圖的基本概念與模型

一個班級的學生共計選修A、B、C、D、E、F六門課程，其中一部分人同時選修D、C、A，一部分人同時選修B、C、F，一部分人同時選修B、E，還有一部分人同時選修A、B，期終考試要求每天考一門課，六天內考完，為了減輕學生負擔，要求每人都不會連續參加考試，試設計一個考試日程表。思考題編輯ppt圖的基本概念與模型思考題解答：

以每門課程為一個頂點，共同被選修的課程之間用邊相連，得圖，按題意，相鄰頂點對應課程不能連續考試，不相鄰頂點對應課程允許連續考試，因此，作圖的補圖，問題是在圖中尋找一條哈密頓道路，如C—E—A—F—D—B，就是一個符合要求的考試課程表。編輯ppt圖的基本概念與模型AFEDCB編輯ppt圖的基本概念與模型AFEDCB編輯ppt圖的基本概念與模型圖的矩陣描述：如何在計算機中存儲一個圖呢？現在已有很多存儲的方法，但最基本的方法就是采用矩陣來表示一個圖，圖的矩陣表示也根據所關心的問題不同而有：鄰接矩陣、關聯矩陣、權矩陣等。1.鄰接矩陣 對于圖G=（V，E），|V|=n，|E|=m，有nn階方矩陣A=(aij)nn，其中編輯ppt圖的基本概念與模型v5v1v2v3v4v64332256437例9.2下圖所表示的圖可以構造鄰接矩陣A如下編輯ppt對于賦權圖G=(V,E),其中邊有權,構造矩陣B=(bij)nn

其中：圖的基本概念與模型2.關聯矩陣對于圖G=(V,E),|V|=n,|E|=m,有mn階矩陣M=(mij)mn，其中:3.權矩陣編輯ppt圖的基本概念與模型101000000000110010000000010001110000000000001001001111000000000000001100000000000111000100110000v1v2v3v4v5v6v7v8e1e2e3e4e5e6e7e8e9e10e11e12v1v2v3v5v8v7e1e2e3e4e6e5e7e9e12e10e11e8v6v4例9.3下圖所表示的圖可以構造鄰接矩陣M如下:M=（mij）=編輯ppt圖的基本概念與模型v5v1v2v3v4v64332256437例9.4下圖所表示的圖可以構造權矩陣B如下:編輯ppt第二節：樹圖1.樹的概念2.樹的性質3.部分樹4.最小部分樹5.最小部分樹的求解編輯ppt樹與圖的最小樹樹是圖論中結構最簡單但又十分重要的圖。在自然和社會領域應用極為廣泛。例9.4乒乓求單打比賽抽簽后，可用圖來表示相遇情況，如下圖所示。ABCDEFGH運動員編輯ppt樹與圖的最小樹例9.5某企業的組織機構圖也可用樹圖表示。廠長人事科財務科總工程師生產副廠長經營副廠長開發科技術科生產科設備科供應科銷售科檢驗科動力科編輯ppt1.樹的概念樹：樹是不含回路的連通圖。樹枝：樹圖的各條邊稱為樹枝編輯ppt2.樹的性質樹：無圈的連通圖即為樹性質1：樹中任意兩個頂點之間，恰有且僅有一條鏈。性質2：樹連通，但去掉任一條邊，必變為不連通。性質3：樹無回圈，但不相鄰的兩個點之間加一條邊，恰得到一個圈。性質4：n個頂點的樹必有n-1條邊。性質5：任何樹中必存在度為1的點。樹中至少存在兩個懸掛點。v1v2v3v4v5v6編輯ppt3.部分樹部分樹：如果圖G的部分圖T是一棵樹，則稱T是G的部分樹。一般圖G含有多個部分樹。圖G圖G的部分樹T1圖G的部分樹T2編輯ppt4.最小部分樹最小部分樹：在賦權圖G的所有部分樹中，樹枝權數和最小的部分樹稱為最小部分樹（或最小支撐樹）。

圖G圖G的部分樹（15）圖G的最小部分樹（8）23169223192312編輯ppt樹與圖的最小樹abcfedhgbfed編輯ppt樹與圖的最小樹abcfedhgbfdg編輯ppt樹與圖的最小樹bcedabcfedhg編輯ppt樹與圖的最小樹abchabcfedhg編輯ppt樹與圖的最小樹afdgabcfedhg編輯ppt5.最小部分樹的求解（1）破圈（回路）法（2）避圈（回路）法（3）順序生枝法編輯ppt破圈法:在連通圖中任意選取一個回路，從該回路中去掉一條權數最大的邊（如果權數最大的邊不唯一，則任意選取其中一條）。在余下的圖中，重復這一步驟，直至得到一個不含回路的連通圖（有個頂點條邊），該連通圖便是最小部分樹。求樹的方法：破圈法和避圈法編輯ppt樹與圖的最小樹破圈法編輯ppt樹與圖的最小樹部分樹編輯ppt樹與圖的最小樹避圈法v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5編輯ppt樹與圖的最小樹破圈法：任取一圈，去掉圈中最長邊，直到無圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521邊數＝n-1=5賦權圖中求最小樹的方法：破圈法和避圈法編輯ppt樹與圖的最小樹v1v2v3v4v5v643521得到最小樹：MinC(T)=15編輯ppt（1）破圈（回路）法227541435715ASBDCET編輯ppt（1）破圈（回路）法227541435715ASBDCET編輯ppt（1）破圈（回路）法22741435715ASBDCET編輯ppt（1）破圈（回路）法22741435715ASBDCET編輯ppt（1）破圈（回路）法2271435715ASBDCET編輯ppt（1）破圈（回路）法2271435715ASBDCET編輯ppt（1）破圈（回路）法221435715ASBDCET編輯ppt（1）破圈（回路）法221435715ASBDCET編輯ppt（1）破圈（回路）法22135715ASBDCET編輯ppt（1）破圈（回路）法22135715ASBDCET編輯ppt（1）破圈（回路）法2213715ASBDCET編輯ppt（1）破圈（回路）法2213715ASBDCET編輯ppt（1）破圈（回路）法221315總權數和為14ASBDCET編輯ppt避圈法:從圖中任選一點vi，讓其他各點均屬于；從溝通集合V和的連線中找出最小邊，使之包含在最小部分樹內。不妨假設最小邊為（vi,vj）令，其他各點均屬于；重復尋找從集合V到的最小邊并使之包含在最小部分樹內，直到圖中的所有點都包含在集合V中為止。

編輯ppt樹與圖的最小樹避圈法:

去掉G中所有邊，得到n個孤立點；然后加邊。加邊的原則為：從最短邊開始添加，加邊的過程中不能形成圈，直到點點連通(即:n-1條邊)。5v1v2v3v4v5v6843752618編輯ppt樹與圖的最小樹v1v2v3v4v5v6435215v1v2v3v4v5v6843752618MinC(T)=15編輯ppt（2）避圈（回路）法2275414357150ASBDCET編輯ppt（2）避圈（回路）法227541435715ASBDCET編輯ppt（2）避圈（回路）法2275414357150ASBDCET編輯ppt（2）避圈（回路）法227541435715ASBDCET編輯ppt（2）避圈（回路）法227541435715ASBDCET編輯ppt（2）避圈（回路）法227541435715ASBDCET編輯ppt（2）避圈（回路）法227541435715ASBDCET編輯ppt（2）避圈（回路）法227541435715ASBDCET編輯ppt（2）避圈（回路）法227541435715ASBDCET編輯ppt（2）避圈（回路）法227541435715ASBDCET編輯ppt（2）避圈（回路）法227541435715ASBDCET編輯ppt（2）避圈（回路）法227541435715ASBDCET編輯ppt樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336練習：應用破圈法求最小樹編輯ppt樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336編輯ppt樹與圖的最小樹v1v7v4v3v2v5v6201591625328174123編輯ppt樹與圖的最小樹v1v7v4v3v2v5v6201591625328174123編輯ppt樹與圖的最小樹v1v7v4v3v2v5v61591625328174123編輯ppt樹與圖的最小樹v1v7v4v3v2v5v61591625328174123編輯ppt樹與圖的最小樹v1v7v4v3v2v5v691625328174123編輯ppt樹與圖的最小樹v1v7v4v3v2v5v691625328174123編輯ppt樹與圖的最小樹v1v7v4v3v2v5v6925328174123編輯ppt樹與圖的最小樹v1v7v4v3v2v5v6925328174123編輯ppt樹與圖的最小樹v1v7v4v3v2v5v69328174123編輯ppt樹與圖的最小樹v1v7v4v3v2v5v69328174123編輯ppt樹與圖的最小樹v1v7v4v3v2v5v693174123min=1+4+9+3+17+23=57編輯ppt樹與圖的最小樹練習：應用避圈法求最小樹v1v7v4v3v2v5v620159162532817412336編輯ppt樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336編輯ppt樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336編輯ppt樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336編輯ppt樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336編輯ppt樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336編輯ppt樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336min=1+4+9+3+17+23=57編輯pptKruskal順序生枝法:首先將圖中的所有邊按權的大小從小到大的進行排列，在確保不出現回路的前提下，將依次排列的邊逐一繪出；若在增加某條邊時出現了回路，則排除該邊并繼續尋找下一條邊。

編輯ppt（3）順序生枝法現有五口油井，相互之間的距離（千米）如下表所示，問應如何鋪設輸油管線使輸油管長度最短。為便于檢修和計量，輸油管只允許在井口處分路。到從w2w3w4w5w11.32.10.90.7w20.91.81.2w32.61.7w40.7編輯ppt（3）順序生枝法（1）排序：按井距從小到大排列

d15=

d45=0.7d14=

d23=0.9d25=

1.2d12=

1.3

d35=1.7d24=

1.8

d13=2.1d34=

2.6（2）生枝：按排序順序生枝，如果某生枝形成回路，略去該枝并繼續直到生成P-1條邊。編輯ppt（3）順序生枝法w5w4w10.70.7編輯ppt（3）順序生枝法w5w4w10.70.7編輯ppt（3）順序生枝法w5w4w10.70.7w3w20.9編輯ppt（3）順序生枝法w5w4w10.70.7w3w20.91.2編輯ppt最短路問題如何用最短的線路將三部電話連起來？此問題可抽象為設△ABC為等邊三角形，，連接三頂點的路線（稱為網絡）。這種網絡有許多個，其中最短路線者顯然是二邊之和（如AB∪AC）。ABC編輯ppt最短路問題ABCP但若增加一個周轉站（新點P），連接4點的新網絡的最短路線為PA＋PB＋PC。最短新路徑之長N比原來只連三點的最短路徑O要短。這樣得到的網絡不僅比原來節省材料，而且穩定性也更好。編輯ppt最短路問題問題描述： 就是從給定的網絡圖中找出一點到各點或任意兩點之間距離最短的一條路.

有些問題，如選址、管道鋪設時的選線、設備更新、投資、某些整數規劃和動態規劃的問題，也可以歸結為求最短路的問題。因此這類問題在生產實際中得到廣泛應用。編輯ppt最短路問題例渡河游戲 一老漢帶了一只狼、一只羊、干草想要從南岸過河到北岸，河上只有一條獨木舟，每次除了人以外，只能帶一樣東西；另外，如果人不在，狼就要吃羊，羊就要吃干草，問應該怎樣安排渡河，才能做到既把所有東西都運過河去，并且在河上來回次數最少？這個問題就可以用求最短路方法解決。編輯ppt最短路問題定義：1）人—M（Man），狼—W（Wolf），羊—G（Goat），草—H（Hay）2）點——vi

表示河岸的狀態3）邊——ek

表示由狀態vi

經一次渡河到狀態vj

4）權——邊ek

上的權定為1我們可以得到下面的加權有向圖編輯ppt最短路問題狀態說明：v1,u1=(M,W,G,H);v2,u2=(M,W,G);v3,u3=(M,W,H);v4,u4=(M,G,H);v5,u5=(M,G)此游戲轉化為在下面的二分圖中求從v1

到u1

的最短路問題。v1v2v3v4v5u5u4u3u2u1編輯ppt第三節：最短路問題1.求圖中某一點到其他各點最短路的Dijkstra標號算法2.求圖中所有點之間最短路的Floyd矩陣算法編輯ppt令Dijkstra算法vi與vj不相鄰vi與vj相鄰vi與vj相等編輯ppt若用Lij代表從點到點的最短路，那么求從點i到點j的最短路的Dijkstra算法的具體步驟可概括如下：從點s出發，因Lss=0

，將“0”標注在旁的小方框內，表示點s已標號；從點s出發，找出與點s相鄰且距離最小的點r，將Lsr=Lss+Lsr的值標注在點r旁的小方框內，表明點r也已標號；Dijkstra算法編輯ppt找出所有與已標號點相鄰的末標號點，若Lsp=min{Lss+Lsp,Lsr+Lrp}

，則給點p標號，即將Lsp的值標注在p旁的小方框內；重復第三步，一直到t點得到標號為止；此時各點小方框內的標注值就是s點到該點的最短路。Dijkstra算法編輯ppt227541435715SABCDEF0第一步：從點s出發，對其標“0”，

令，其他各點均屬于；編輯ppt227541435715SABCDEF0故A點得到標號“2”，令其余各點均屬于2第二步：與s點相鄰的未標號點有A、B、C三個點，又因：

，編輯ppt227541435715SABCDEF02第三步：與標號點s和A相鄰的未標號點有B、C、E三個點，又因：故B、C兩點同時得到標號“4”，其余各點均屬于44編輯ppt227541435715SABCDEF024依此類推，直到所有的點均得到標號

47813編輯ppt2.求圖中所有點之間最短路的Floyd矩陣算法dij(0)=wij

(ifi與j相鄰)dij(0)=0(ifi=j)

dij(0)=(ifi與j不相鄰)dij=D(0)={dij(0)}代表從i直接到達j的距離矩陣編輯ppt2.求圖中所有點之間最短路的Floyd矩陣算法D(0)={dij}代表從i直接到達j的距離矩陣從i到達j的最短路并不局限在直接到達，兩點之間可以有1、2、……個中間點。先考慮i和j兩點之間可以有1個中間點的情況：

dij(1)

=min[dik(0)

+dkj(0)]k=1,2,……,Pikjk’編輯ppt2.求圖中所有點之間最短路的Floyd矩陣算法再考慮i和j兩點之間可以有3個中間點的情況：

dij(2)

=min[dik(1)

+dkj(1)]k=1,2,……,Pikjnm編輯ppt2.求圖中所有點之間最短路的Floyd矩陣算法i和j兩點之間可以有2n-1個中間點的情況：

dij(n)

=min[dik(n-1)

+dkj(n-1)]k=1,2,……,P結束條件：或即編輯ppt2.求圖中所有點之間最短路的Floyd矩陣算法SACBEDT227541435715SACBDETSACB

EDT編輯pptSACBEDT227541435715SACBDETSACB

EDT編輯ppt227541435715SACBDET編輯ppt227541435715SACBDET編輯ppt最短路問題例設備更新問題。某公司使用一臺設備，在每年年初，公司就要決定是購買新的設備還是繼續使用舊設備。如果購置新設備，就要支付一定的購置費，當然新設備的維修費用就低。如果繼續使用舊設備，可以省去購置費，但維修費用就高了。請設計一個五年之內的更新設備的計劃，使得五年內購置費用和維修費用總的支付費用最小。已知：設備每年年初的價格表年份12345年初價格1111121213編輯ppt最短路問題設備維修費如下表使用年數0-11-22-33-44-5每年維修費用5681118解：將問題轉化為最短路問題，如下圖：用vi表示“第i年年初購進一臺新設備”,弧（vi,vj）表示第i年年初購進的設備一直使用到第j年年初。v1v2v3v4v5v6編輯ppt最短路問題把所有弧的權數計算如下表，把權數賦到圖中，再用Dijkstra算法求最短路。123456116223041592162230413172331417235186v1v2v3v4v5v6162230415916223041312317181723編輯ppt最短路問題最終得到下圖，可知，v1到v6的距離是53，最短路徑有兩條：v1→v3→v6和

v1→v4→v6

V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723

V2（16,1）16(30,1)(53,3)(53,4)編輯ppt2.求圖中所有點之間最短路的Floyd矩陣算法案例：某城有5個區組成，各區之間的道路情況如下圖所示，各邊的權數為距離（千米）。已知各區年消費糧食分別為6000、4000、10000、7000和9000噸，若該城準備建一座統一的糧庫，問就運輸的噸千米數最小糧庫應建在哪個區？10EDCBA2051020101525編輯ppt2.求圖中所有點之間最短路的Floyd矩陣算法

0102015100520D(0)=205010101510025

2010250

編輯ppt2.求圖中所有點之間最短路的Floyd矩陣算法

01015153010051515D(1)=15501010151510020

301510200

編輯ppt2.求圖中所有點之間最短路的Floyd矩陣算法

01015152510051515D(2)=15501010151510020

251510200

編輯ppt2.求圖中所有點之間最短路的Floyd矩陣算法

01015152510051515D(2)=15501010151510020

251510200

600040001000070009000編輯ppt2.求圖中所有點之間最短路的Floyd矩陣算法

060,00090,00090,000150,00040,000020,00060,00060,000150,00050,000010,00010,000105,000105,00070,0000140,000225,000135,00090,000180,0000520,000350,000270,000340,000360,000

合計C*編輯ppt最短路問題思考題1、求下圖v1到各點的最短距離及最短路線。①②③④⑤⑥⑦⑧4526178393261216180452231039612641166188122482418所有點都已標號，點上的標號就是v1到該點的最短距離，最短路線就是紅色的鏈。編輯ppt最短路問題2.求從v1到v8的最短路徑237184566134105275934682編輯ppt最短路問題237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到v8的最短路徑為v1→v4→v7→v5→v8，最短距離為10編輯ppt最短路問題3.求下圖中v1點到另外任意一點的最短路徑v1v2v3v4v6v5322762133編輯ppt最短路問題v1V2V3V4V6V5322762133024714編輯ppt最短路問題v1V2V3V4V6V5322762133024714編輯ppt最短路問題最短路問題的應用：4、電信公司準備準備在甲、乙兩地沿路架設一條光纜線，問如何架設使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權數表示兩地間公路的長度（單位：公里）。

v1（甲地）1517624431065v2v7(乙地)v3v4v5v6編輯ppt第五節：最大流問題1.基本概念2.求網絡流圖最大流的標號算法編輯ppt1.基本概念正、負線度：從一點發出的弧的數目稱為點的正線度；進入點的弧的數目稱為點的負線度。2.發點（source）：負線度為“0”的點。3.收點（sink）：正線度為“0”的點。編輯ppt1.基本概念4.網絡流圖：（1）只有一個發點和一個收點；（2）各弧有一個非負的“容量（capacity）”，cij；（3）各弧有一個不大于“容量”的“流量（flow）”，fij。編輯ppt1.基本概念4.容量網絡：網絡上的每條弧(vi,vj)都給出一個最大的通過能力，稱為該弧的容量，簡記為cij。容量網絡中通常規定一個發點(也稱源點，記為s)和一個收點(也稱匯點，記為t)，網絡中其他點稱為中間點。s①②③④t4844122679編輯ppt1.基本概念

5.流、可行流和最大流：

流是指加在網絡各條弧上的實際流量，對加在弧(vi,vj)上的負載量記為fij。若fij=0，稱為零流。

可行流：滿足以下條件的一組流稱為可行流。

容量限制條件。容量網絡上所有的弧滿足：0≤fij≤cij

中間點平衡條件。

若以v(f)表示網絡中從s→t的流量，則有：編輯ppt網絡的最大流網絡的最大流網絡的最大流是指網絡中從發點到收點之間允許通過的最大流量。6.飽和弧：fij=cij

的弧。7.非飽和弧：fij<cij

的弧。8.零流弧：fij=0的弧。結論：任何網絡上一定存在可行流。（零流即是可行流）網絡最大流問題： 指滿足容量限制條件和中間點平衡的條件下，使v(f)值達到最大。編輯ppt1.基本概念

9.正向弧與反向弧：若是從發點vs到收點vt的一條鏈，定義鏈的方向為從vs到vt，則鏈上的弧被分為兩類：（1）弧的方向與鏈的方向一致（在該鏈上所有指向為s→t的弧），則稱正向弧（+）；（2）弧的方向與鏈的方向相反（在該鏈上所有指向為t→s的弧），則稱反向弧（-）。

10.增廣鏈：設f是一個可行流，是從發點vs到收點vt的一條鏈，若滿足下列條件，則稱其為一條增廣鏈：（1）+中的每一個弧均為非飽和弧；（2）-中的每一個弧均為非零流弧。編輯ppt若f>0，則稱這樣的鏈為增廣鏈。例如下圖中，s→v2→v1→v3→v4→t。定理3

網絡N中的流f

是最大流當且僅當N中不包含任何增廣鏈stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(4)7(5)編輯ppt網絡的最大流求網絡最大流的標號算法：[基本思想]

由一個流開始，系統地搜尋增廣鏈，然后在此鏈上增流，繼續這個增流過程，直至不存在增廣鏈。[基本方法]找出第一個可行流，（例如所有弧的流量dij

=0。）用標號的方法找一條增廣鏈首先給發點s標號(∞),標號中的數字表示允許的最大調整量。選擇一個點vi

已標號并且另一端未標號的弧沿著某條鏈向收點檢查：編輯ppt網絡的最大流如果弧的起點為vi，vj未標號且相鄰，并且有dij<Cij，則給vj標號為(vi,δj)

如果弧的方向指向vi，并且有djj>0，則vj標號(-vi,δj)(3)重復第(2)步，可能出現兩種結局：標號過程中斷，t無法標號，說明網絡中不存在增廣鏈，目前流量為最大流。

t得到標號，反向追蹤在網絡中找到一條從s到t得由標號點及相應的弧連接而成的增廣鏈。繼續第(4)步編輯ppt網絡的最大流(4)修改流量。設原圖可行流為f，令得到網絡上一個新的可行流f’。(5)擦除圖上所有標號，重復(1)-(4)步，直到圖中找不到任何增廣鏈，計算結束。編輯ppt1.基本概念v4v3v2vtv1vs(5,3)(3,0)(4,3)(1,1)(2,2)(1,1)(5,1)(3,3)(2,1)（1）鏈={vs,v1,v2,v4,v3,vt}是一條增廣鏈；（2）鏈={vs,v2,v3,v4,vt}不是增廣鏈；（3）鏈={vs,v1,v2,v4,v3,vt}不是增廣鏈。編輯ppt（0，）2.求網絡流圖最大流的標號算法v4v3v2vtv1vs(5,4)(3,0)(4,4)(1,1)(2,2)(1,0)(5,2)(4,3)(2,1)（vs，3）（vs，1）（-v2，1）（v3，1）編輯ppt2.求網絡流圖最大流的標號算法v4v3v2vtv1vs(5,4)(3,0)(4,3)(1,0)(2,2)(5,2)(4,3)(2,2)(1,0)編輯ppt2.求網絡流圖最大流的標號算法v4v3v2vtv1vs(5,4)(3,0)(4,3)(1,0)(2,2)(5,2)(4,3)(2,2)(1,0)編輯ppt（0，）2.求網絡流圖最大流的標號算法v4v3v2vtv1vs(5,4)(3,0)(4,3)(1,0)(2,2)(1,0)(5,2)(4,4)（vs，3）(2,2)最大流=6編輯ppt網絡的最大流例用標號算法求下圖中s→t的最大流量●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)編輯ppt網絡的最大流解：(1)先給s標號(0,∞)●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)(0,∞)編輯ppt網絡的最大流●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)(0,∞)(2)檢查與s點相鄰的未標號的點，v1與v2，因ds1<cs1，故對v1標號（vs

，l（v1

））:(Vs,1)(Vs,2)因ds2<cs2，故對v2標號（vs

，l（v2

））

編輯ppt網絡的最大流●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(6)(0,∞)(vs,1)(2)檢查與v2點相鄰的未標號的點，v3與v4，因（v2,v3)為負向零流弧，（v2,v4)為正向飽和弧，所以v3與v4沒有得到標號。(vs,2)編輯ppt網絡的最大流●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(6)(0,∞)(vs,1)(2)檢查與v1點相鄰的未標號的點，因f13<c13，故對v3標號l(v3)min{l(v1)

,c13-d13}=

=min{1,c13-d13}=min{1,6}=1；(v1,1)(vs,2)編輯ppt網絡的最大流●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)(0，∞)(vs,1)(v1,1)(3)檢查與v3點相鄰的未標號的點，因f3t<c3t，故對vt標號=min{1,c3t-f3t}=min{1,1}=1(v3,1)找到一條增廣鏈s→v1→v3→t(vs,2)編輯ppt網絡的最大流(4)修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(3)7(5)(0，∞)(vs,1)(v1,1)(v3,1)(vs,2)編輯ppt網絡的最大流(5)擦除所有標號，重復上述標號過程，尋找另外的增廣鏈。●stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)(0，∞)(vs,1)(v1,1)(v3,1)編輯ppt網絡的最大流(5)擦除所有標號，重復上述標號過程，尋找另外的增廣鏈。●stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)(vs,2)l(v2)=min{∞,2}=2l(v1)=min{2，3}=2l(v3)=min{2,5}=2(-v3,1)l(v4)=min{2,1}=1l(vt)=min{1,2}=1(0，∞)(-v2,2)(v1,2)(v4,1)編輯ppt網絡的最大流(6)修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。●stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)(vs,2)(v3,1)(0，∞)(v2,2)(v1,2)(v4,1)編輯ppt網絡的最大流●stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)(7)擦除所有標號，重復上述標號過程，尋找另外的增廣鏈。(vs,1)(v3,1)(0，∞)(-v2,1)(v1,1)(v4,1)編輯ppt網絡的最大流●stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)(7)擦除所有標號，重復上述標號過程，尋找另外的增廣鏈。l(v2)=min{∞,1}=1l(v1)=min{1,2}=1l(v3)=min{1,4}=1(vs,1)(0，∞)(v2,1)(v1,1)無法標號，不存在增廣鏈，此可行流已為最大流。最大流量為14。編輯ppt網絡的最大流例求下圖s→t的最大流stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)●編輯ppt網絡的最大流stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)●解:(1)在已知可行流的基礎上，通過標號尋找增廣鏈。(∞)ε(2)=min{∞,6}=6(6)ε(3)=min{6,2}=2(2)ε(t)=min{2,5}=2(2)存在增廣鏈s→v2→v3→t編輯ppt網絡的最大流(2)修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)●(∞)(6)(2)(2)編輯ppt網絡的最大流(3)擦除原標號，重新搜尋增廣鏈。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)●(∞)(6)(2)(2)編輯ppt網絡的最大流(4)重新搜尋增廣鏈。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)●(∞)ε(2)=min{∞,4}=4(4)(1)ε(5)=min{4,1}=1ε(3)=min{1,2}=1(1)(1)ε(t)=min{1,3}=1存在增廣鏈：s→v2→v5→v3→t編輯ppt網絡的最大流(5)修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)●(∞)(4)(1)(1)(1)編輯ppt網絡的最大流(6)擦除原標號stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)●(∞)(4)(1)(1)(1)編輯ppt網絡的最大流stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)●(∞)(1)(1)(1)ε(5)=min{∞,1}=1ε(5)=min{1,1}=1ε(5)=min{1,2}=1(7)重新搜尋增廣鏈。存在增廣鏈：s→v5→v3→t編輯ppt網絡的最大流(8)調整增廣鏈上的流量，非增廣鏈流量不變，得到新的可行流stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)●(∞)(1)(1)(1)編輯ppt網絡的最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)●(∞)(1)(1)(1)(9)擦除原標號編輯ppt網絡的最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)●(10)重新標號，搜索增廣鏈(∞)ε(1)=min{∞,1}=1(1)ε(5)=min{1,1}=1(1)ε(4)=min{1,1}=1(1)ε(t)=min{1,1}=1(1)存在增廣鏈：s→v1→v5→v4→t編輯ppt網絡的最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)●(∞)(1)(1)(1)(1)(11)調整增廣鏈上的流量，非增廣鏈流量不變，得到新的可行流編輯ppt網絡的最大流stv1v2v3v4v54(4)3(3)10(7)3(3)1(1)4(4)3(3)5(5)4(4)2(2)7(7)8(7)●(∞)(1)(1)(1)(1)(11)擦除標號，在新的可行流上重新標號。編輯ppt網絡的最大流stv1v2v3v4v54(4)3(3)10(7)3(3)1(1)4(4)3(3)5(5)4(4)2(2)7(7)8(7)●(∞)(11)擦除標號，在新的可行流上重新標號。(3)ε(1)=min{∞,3}=1無法標號，不存在增廣鏈，此可行流已為最大流。最大流量為14。編輯ppt第六節：中國郵路問題v8v7v6v5v4v3v2v1v10v910949718522210編輯pptv8v7v6v5v4v3v2v1v10v910949718522210編輯pptv8v7v6v5v4v3v2v1v10v9109497185222最佳郵路總長69+2310編輯ppt第七節：網絡計劃1.引論2.網絡計劃的工作步驟3.網絡圖4.網絡時間計算5.網絡優化編輯ppt1.引論（1）1956年——美國杜邦公司制定業務部門系統規劃，CPM（CriticalPathMethod）（2）1958年——美國海軍武器部“北極星”導彈計劃，PERT（ProgramEvaluationandReviewTechnique）（3）1960s——我國應用CPM和PERT----統籌法編輯ppt2.基本概念作業或工序作業或工序是指工程中在工藝技術和組織管理上相對獨立的一部分工作或活動。

作業時間為完成某一作業所需要消耗的時間稱為該作業的作業時間。作業時間的確定通常采用兩種方法，即一點法和三點法。編輯ppt2.基本概念一點法對作業時間的估計采用單值的方法，即給出一個估計點；如8天、100天、120天等。這種方法一般在具備勞動定額數據或類似作業的統計信息時使用。三點法對作業時間的估計采用三值的方法，即給出樂觀（a）、最可能（m）和悲觀（b）三個估計點；如a=5天，m=8天，b=12天。編輯ppt2.基本概念不妨假設服從正態分布，如圖9-26所示。一般情況下，可按加權平均的方式計算作業時間，即：對應的方差為：mba時間圖9-26編輯ppt2.基本概念作業之間順序關系作業之間的先后順序關系是通過緊前作業或緊后作業來加以描述的。如果作業B只有在作業A完成后才能開始，那么就稱作業A是作業B的緊前作業；而作業B稱為作業A的緊后作業。編輯ppt2.基本概念完成作業或工序的劃分、作業時間的確定、明確作業關系三個基本步驟，即可構造出由作業、作業時間和緊前作業或緊后作業所組成的作業關系明細表，如表9-5所示。表9-5作業ABCDEFGHI緊前作業ABCB、DEB、F作業時間1230815209113018編輯ppt3.網絡計劃的工作步驟(1)將整個項目劃分為基本的工作單元——工序；(2)確定工序的邏輯順序（緊前工序和緊后工序）；(3)繪制網絡圖；(4)進行網絡時間計算；(5)網絡優化及決策；(6)網絡執行及動態調整。編輯ppt4.網絡圖網絡圖的構成：（1）結點——標志著工序的開始或結束；（2）箭線——代表著工序。網絡圖的基本要求：（1）只能有一個開始結點和一個結束結點；（2）箭頭結點的標號大于箭尾結點的標號；（3）任一對結點間只