【正文】 院 參考書： １ 、 高隨祥 《 圖論與網(wǎng)絡流理論 》 高等教育出版社 ２ 、 王樹禾 《 圖論 》 科學出版社 河南城建學院 167。 1857年，凱萊在計數(shù)烷的同分異構物時，也發(fā)現(xiàn)了“樹”。 河南城建學院 ? 例 1 最短路問題（ SPP－ shortest path problem） ? 一名貨柜車司機奉命在最短的時間內將一車貨物從甲地運往乙地。由于各員工的特點不同，不同的員工去完成同一項任務時所獲得的回報是不同的。如何為他（她）設計一條最短的旅行路線（從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地）？這一問題的研究歷史十分悠久，通常稱之為旅行商問題 。 所以上面例子中介紹的問題都是網(wǎng)絡優(yōu)化問題。當無向邊 ( , )ije v v?時，稱 e 與 iv，jv關聯(lián)，或 iv，jv與 e 關聯(lián)，或 iv與 jv 相鄰接；關聯(lián)于同一頂點的一條邊稱為環(huán)。 ( 7) 任意兩頂點都相鄰的簡單圖稱為 完全圖 。 圖的定義與記號 河南城建學院 定義 2 子圖：給定兩個無 (有 )向圖 G=（ V,E） ， G?=（ V?,E?） 。 河南城建學院 167。 定義 2 (1) 在無向圖 G中 ,若存在一條從頂點 u到 w的路 徑 , 則稱 從 u到 w可達 .約定每個結點到自身 可達 。 4．圖的矩陣表示 定義 1 關聯(lián)矩陣 (1) 對無向圖 G ，其關聯(lián)矩陣()ij vMm???，其中 ij1 , v v0 , ijm???? ij若 與 相 關 聯(lián)若 v 與 v 不 關 聯(lián) (2) 對有向圖 G ，其關聯(lián)矩陣()ij vMm???，其中 1 , 1 , 0 , iij iivmvv???????jjj若 是 e 的 起 點若 是 e 的 終 點若 與 e 不 關 聯(lián) 河南城建學院 1 3 4 5 2 關聯(lián)矩陣示例 右上圖的關聯(lián)矩陣是 右下圖的關聯(lián)矩陣是 1e1 3 4 2 ????????????????110100001010010001101010000110010000011154321?????????????????1100010110011010001143212e3e4e5e6e 7e8e1e2e3e4e5e1e1e2e2e3e3e 4e4e 5e5e6e 7e 8e河南城建學院 定義 2 鄰接矩陣 (1) 對無向圖 G ，其鄰接矩陣()ij v vAa??，其中 1 , 0 , ijijijvvavv????若 與 相 鄰若 與 不 相 鄰 (2) 對有向圖 G = V ， E ，其鄰接矩陣()ij v vAa??，其中 1 , ( , )0 , ( , )ijijijv v Eav v E??????若若 （ 3 ） 對有向賦權圖 G ，其鄰接矩陣()ij v vAa??， 其中 , ( , )0 , , ( , )i j i j i jijijw v v E wa i jv v E? ?????????若 , 且 為 其 權若若 河南城建學院 鄰接矩陣示例 右上圖的鄰接矩陣是 右下圖的鄰接矩陣是 1 3 4 5 2 1 3 4 2 ????????????????01110101011101110101011105432154321????????????010000001100011043214321河南城建學院 定義 3 可達矩陣： 對有向圖 G = （ V ， E ），其可達矩陣()ij v vPp??，其中 1 , 0 , ijijijvvpvv????若 與 可 達若 與 不 可 達 1 3 4 2 1 2 3 41 1 1 1 12 0 1 1 13 0 0 1 04 0 0 1 1????????????例 右圖的可達矩陣是 河南城建學院 二、圖論模型實例分析 實例一 握手的次數(shù) 史密斯先生和他太太邀請四對夫妻參加晚會每個人 到的時候 ， 房間里的一些人都要與別的一些人握手 。 河南城建學院 握手的次數(shù) 分析：從題目我們得到了哪些信息 ? ? 史密斯和太太邀請四對夫妻參加晚會 —— 房間里共有10 人 。 ? —— 除史密斯先生外 ， 每個人握手的次數(shù)最多是 8次 ，最少為 0次 。 而人不在場時 ， 狗要吃羊 ， 羊要吃菜 ， 問此人應如何過河 ？ 模型構成此問題可化為狀態(tài)轉移問題 ， 用四 維向量 （ 人 ， 狗 ， 羊 ， 菜 ） 來表示狀態(tài) ， 當一物 在此岸時相應分量取 1， 而在彼岸時則取 0。 例如表示人帶狗過河 。 河南城建學院 課后作業(yè) 四名商人各帶一個隨從乘船渡河 ， 一只小船 只能容納二人 ， 由他們自己劃行 。 5 Euler圖和 Hamilton圖 ? 基本概念 ? 定義 經(jīng)過 G的每條邊的跡叫做 G的 Euler跡 ；閉的 Euler跡叫做 Euler回路或 E回路 ；含 Euler回路的圖叫做 Euler圖 。 河南城建學院 ? Euler回路的 Fleury算法 ? 1921年， Fleury給出下面的求 Euler回路的算法。 ? 3. 當?shù)?2步不能再執(zhí)行時，算法停止。 河南城建學院 ? 多郵遞員問題： ? 郵局有 k(k≥2)位投遞員，同時投遞信件，全城街道都要投遞，完成任務返回郵局，如何分配投遞路線，使得完成投遞任務的時間最早？我們把這一問題記成 kPP。稱這種圈為最優(yōu)圈。 7 最小生成樹及其應用 ? 定義 無向圖 G=（ V,E）的生成子圖 T是樹 ,則稱 T是 G的一棵生成樹（ 支撐樹 ） (不唯一） . ? 任何連通無向圖 G至少有一棵生成樹 . ? 賦權簡單連通無向圖 G=(V,E,W)的子圖 H的權定義為 H 的所有邊的權和 .G中權最小的生成樹稱為 最小生成樹 (對普通簡單連通圖不考慮最小生成樹 ). ? 最小生成樹有很強的應用背景 ,例如 :設計聯(lián)系若干城市的最短線路通信網(wǎng) 。 2 3 4 5 6 7 4 v3 v1 v2 v4 v5 v6 1 5 河南城建學院 2 3 4 5 6 7 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 5 6 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 5 6 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 5 4 v3 v1 v2 v4 v5 v6 1 5 河南城建學院 2 3 4 5 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 v3 v1 v2 v4 v5 v6 1 5 河南城建學院 最小生成樹實例 :有線電視網(wǎng)最優(yōu)布線問題 單位： 100米 : 衛(wèi)星加密電視的開播 ,受到大 家歡迎 ,要想收看加密電視必 須建一套有線電視網(wǎng)．我們 考慮這樣一個具體問題：設 某市六個個區(qū)之的相互距離 如下表所示，試確定表數(shù)據(jù) 形成的網(wǎng)絡中，如何布線能 布線最??？ 1 2 3 4 5 6 1 0 13 51 77 68 50 2 13 0 60 70 67 59 3 51 60 0 57 3 62 4 77 70 57 0 20 55 5 68 67 36 20 0 34 6 50 59 2 55 34 0 河南城建學院 最小生成樹實例 :有線電視網(wǎng)最優(yōu)布線問題 ２ .問題求解 : 最優(yōu)布線問題，就是要求任何兩地都有鏈相連，而使總線路最短，這個問題在圖論中也稱為最小樹題．作下圖，其中頂點 v1 ， v２ ， v３ ， v４ ， v５ ， v６ 分別表示兩區(qū)之間的距離． V1 V6 V3 V5 V4 V2 60 70 20 13 67 59 77 57 55 68 51 2 34 36 50 河南城建學院 最小生成樹實例 :有線電視網(wǎng)最優(yōu)布線問題 對于上圖，我們要找使布線最省的網(wǎng)絡模型．圖論中的破圈法可以解 決這個問題，具體過程如下：在圈 v1v２ v３ v1中，去掉最長邊 v２ v３ ＝ 60，同 樣去掉圈 v1v３ v６ v1， v２ v４ v５ v２ ， v３ v４ v５ v３ ， v3 v5v６ v3， v4v5 v6 v4， v1v3v4v1， v1v6v2v1， v2v5v6v2中最長的邊 v1v３ ＝ 51， v2v4＝ 70， v3v4＝ 57， v3v5＝ 36,v4v6＝ 55， v1v4＝ 77， v1v5＝ 68， v2v6＝ 59， v2v5＝ 67，最后構 成的圖（如下）就是最省的 布線圖 ． 13 2 50 34 20 v2 v3 v1 v6 v4 v6 V1 V6 V3 V5 V4 V2 60 70 20 13 67 59 77 57 55 68 51 2 34 36 50 河南城建學院 167。 求最短路的方法： (1) 求從一點到其余各點間的 Dijkstra算法 。現(xiàn)要求從點到某一點 t的最 短路。 }sp ss sp sr rpL L d