【正文】 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ù) 史密斯先生和他太太邀請四對夫妻參加晚會每個人 到的時候 ， 房間里的一些人都要與別的一些人握手 。 當 然 ， 每個人都不會與自己的配偶握手 ， 也不會跟同一個 人握手兩次 。 之后 ， 史密斯先生問每個人和別人握了幾 次手 ， 他們的答案都不一樣 。 那么 ， 史密斯太太和別人 握了幾次手呢 ? 這個問題具有挑戰(zhàn)性的原因是因為它沒有一個明顯 的起始點 ， 但如果對此建立一個圖模型 ， 問題就變得很 簡單了 。 河南城建學院 握手的次數(shù) 分析：從題目我們得到了哪些信息 ? ? 史密斯和太太邀請四對夫妻參加晚會 —— 房間里共有10 人 。 ? 每個人都不會與自己的配偶握手 —— 握手的兩個人不是配偶 。 ? 每個人都不會跟同一個人握手兩次 —— 兩個人間的握手最多是一次 。 ? 史密斯先生問每個人和別人握了幾次手 ， 他們的答案都不一樣 —— 除史密斯先生外 ， 每個人和別人握手的次數(shù)都不一樣 。 ? —— 除史密斯先生外 ， 每個人握手的次數(shù)最多是 8次 ，最少為 0次 。 ? —— 房間里除了史密斯先生外的 9個人 ， 他們與別人握手的次數(shù)分別為 0， 1， 2， 3， 4， 5， 6， 7， 8次 。 河南城建學院 握手的次數(shù) 要知道史密斯太太和別人握手的次數(shù) ， 只需確定除史 密斯先生外的 9人中哪一個是史密斯太太即可 。 根據(jù)以上信息 ， 建立圖模型： 河南城建學院 握手的次數(shù) 由圖可知： ? 8號的配偶是 0號； ? 7號的配偶是 1號； ? 6號的配偶是 2號； ? 5號的配偶是 3號； ? 史密斯太太是 4號 ， 所以史密斯太太和別 人握了 4次 河南城建學院 實例二 渡河問題 某人帶狗 、 羊 、 以及蔬菜渡河 ， 一小船除需 人劃外 ， 每次只能載一物過河 。 而人不在場時 ， 狗要吃羊 ， 羊要吃菜 ， 問此人應如何過河 ？ 模型構成此問題可化為狀態(tài)轉(zhuǎn)移問題 ， 用四 維向量 （ 人 ， 狗 ， 羊 ， 菜 ） 來表示狀態(tài) ， 當一物 在此岸時相應分量取 1， 而在彼岸時則取 0。 （ 1） 可取狀態(tài) 人在此岸 人在彼岸 總共有十個可取狀態(tài) 。 河南城建學院 現(xiàn)在用狀態(tài)運算來完成狀態(tài)轉(zhuǎn)移 。 由于擺一次游戲即改變現(xiàn)有狀態(tài) ， 為此再引入一個四維轉(zhuǎn)移向量 ， 用它來反映擺渡情況用 1表示過河 ， 0表示未過河 。 例如表示人帶狗過河 。 此狀態(tài)只有四個允許轉(zhuǎn)移向量： 現(xiàn)在規(guī)定狀態(tài)向量與轉(zhuǎn)移向量 （ 分量 ） 之間的運算為 渡河問題 河南城建學院 渡河問題 模型求解 通過上面的定義 ， 問題化為 — 由初始狀態(tài) 出發(fā) ， 經(jīng)過奇數(shù)次上述運算轉(zhuǎn)移為狀態(tài) 的轉(zhuǎn) 移過程 。 可用圖表示為 河南城建學院 河南城建學院 實例三 循環(huán)比賽的名次 問題 n支球隊循環(huán)比賽 ， 每場只計勝負 ， 沒有平局 . 根據(jù)比賽結果排出各隊名次 .圖 （ 1） 給出了 6支 球隊的比賽結果 ， 即 1隊戰(zhàn)勝 6隊 ， 而 輸給了 3隊； 5隊戰(zhàn)勝 6隊 ， 而輸給了 4 隊等等 . 河南城建學院 循環(huán)比賽的名次 方法 1：尋找按箭頭方向通過全部頂點的路徑 . 312456 146325 …… ?無法排名 方法 2：計算得分： 1隊勝 4場 ， 2， 3隊各勝 3 場 ， 4， 5隊各勝 2場 ， 6隊勝 1場 .2， 3 隊 ， 4， 5隊無法排名 .3→ 2， 4→ 5? 排名 132456合理嗎 ？ 用圖論的知識可以解決這個問題 . 河南城建學院 循環(huán)比賽的名次 競賽圖及其性質(zhì) 循環(huán)比賽的結果 —— 競賽圖：每對頂點之間都有 一條邊相連的有向圖 .名次是由出度由大到小排序 。 3個頂點的競賽圖： 名次： {1,2,3} {(1,2,3)}并列 河南城建學院 4個頂點的競賽圖： 名次： {1,2,3,4} {2,(1,3,4)} {(1,3,4),2} {(1,2),(3,4)} {1,2,3,4} 循環(huán)比賽的名次 河南城建學院 循環(huán)比賽的名次 競賽圖的 3種形式 ： ? 具有唯一的完全路徑 ， 如 (1) ? 雙向連通圖 任一對頂點存在兩條有向路徑相 互連通 ， 如 (4)； ? 其他 ， 如 (2),(3). 競賽圖的性質(zhì) ： ? 必存在完全路徑； ? 若存在唯一的完全路徑 ， 則由它確定的頂點 順序與按得分排列的順序一致 ， 如 （ 1） . 雙向連通競賽圖的名次排序 河南城建學院 循環(huán)比賽的名次 河南城建學院 循環(huán)比賽的名次 模型建立 定義鄰接矩陣如下： 故 （ 4） 的鄰接矩陣為 河南城建學院 循環(huán)比賽的名次 記頂點 得分向量 為 ,則有 ～ 1級得分向量 ～ 2級得分向量 河南城建學院 循環(huán)比賽的名次 模型求解 利用著名的 PerronFrobenius定理 ， 素陣 A的最大 特征根為正單根 ， 對應正特征向量 s， 且有 (歸一化后 ) 用 s排名 . 對 （ 4） ， 因 河南城建學院 循環(huán)比賽的名次 對于本節(jié)開始提出的 6支球隊循環(huán)比賽的結果 ， 有： 河南城建學院 循環(huán)比賽的名次 所以 ， 排出名 次為 。 河南城建學院 課后作業(yè) 四名商人各帶一個隨從乘船渡河 ， 一只小船 只能容納二人 ， 由他們自己劃行 。 隨從們密約 ， 在河的任一岸 ， 一旦隨從的人數(shù)比商人多 ， 就殺 人越貨 。 但是如何乘船渡河的大權掌握在商人們 手中 。 商人們怎樣才能安全渡河呢 ? 河南城建學院 167。 5 Euler圖和 Hamilton圖 ? 基本概念 ? 定義 經(jīng)過 G的每條邊的跡叫做 G的 Euler跡 ；閉的 Euler跡叫做 Euler回路或 E回路 ；含 Euler回路的圖叫做 Euler圖 。 ? 直觀地講， Euler圖就是從一頂點出發(fā)每邊恰通過一次能回到出發(fā)點的那種圖，即不重復地行遍所有的邊再回到出發(fā)點 。 河南城建學院 ? 定義 包含 G的每個頂點的軌叫做 Hamilton(哈密頓 )軌 ；閉的 Hamilton軌叫做 Hamilton圈或 H圈 ；含 Hamilton圈的圖叫做 Hamilton圖 。 ? 直觀地講， Hamilton圖就是從一頂點出發(fā)每頂點恰通過一次能回到出發(fā)點的那種圖，即不重復地行遍所有的頂點再回到出發(fā)點。 河南城建學院 ? Euler回路的 Fleury算法 ? 1921年， Fleury給出下面的求 Euler回路的算法。 ? Fleury算法： ? 1. ?v0∈V(G) ，令 W0=v0。 ? 2. 假設跡 Wi=v0e1v1…eivi 已經(jīng)選定，那么按下述方法從 E{e1, … ,ei}中選取邊 ei+1： 河南城建學院 ? （ i） ei+1和 vi相關聯(lián)； ? （ ii）除非沒有別的邊可選擇，否則 ei+1不是Gi=G {e1, … ,ei}的割邊 (cut edge)。 (所謂割邊是一條刪除后使連通圖不再連通的邊 )。 ? 3. 當?shù)?2步不能再執(zhí)行時，算法停止。 河南城建學院 ? 應用 ? 郵遞員問題 ? 中國郵遞員問題 ? 一位郵遞員從郵局選好郵件去投遞，然后返回郵局，當然他必須經(jīng)過他負責投遞的每條街道至少一次，為他設計一條投遞路線，使得他行程最短。 ? 上述中國郵遞員問題的數(shù)學模型是：在一個賦權連通圖上求一個含所有邊的回路，且使此回路的權最小。 ? 顯然，若此連通賦權圖是 Euler圖，則可用Fleury算法求 Euler回路，此回路即為所 求。 河南城建學院 ? 多郵遞員問題： ? 郵局有 k(k≥2)位投遞員，同時投遞信件，全城街道都要投遞，完成任務返回郵局，如何分配投遞路線，使得完成投遞任務的時間最早？我們把這一問題記成 kPP。 河南城建學院 ? 旅行商（ TSP）問題 ? 一名推銷員準備前往若干城市推銷產(chǎn)品，然后回到他的出發(fā)地。如何為他設計一條最短的旅行路線（從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地）？這個問題稱為旅行商問題。用圖論的術語說，就是在一個賦權完全圖中，找出一個有最小權的 Hamilton圈。稱這種圈為最優(yōu)圈。與最短路問題及連線問題相反，目前還沒有求解旅行商問題的有效算法。所以希望有一個方法以獲得相當好（但不一定最優(yōu)）的解。 河南城建學院 167。 7 最小生成樹及其應用 ? 定義 無向圖 G=（ V,E）的生成子圖 T是樹 ,則稱 T是 G的一棵生成樹（ 支撐樹 ） (不唯一） . ? 任何連通無向圖 G至少有一棵生成樹 . ? 賦權簡單連通無向圖 G=(V,E,W)的子圖 H的權定義為 H 的所有邊的權和 .G中權最小的生成樹稱為 最小生成樹 (對普通簡單連通圖不考慮最小生成樹 ). ? 最小生成樹有很強的應用背景 ,例如 :設計聯(lián)系若干城市的最短線路通信網(wǎng) 。設計供應若干居民點的最短自來水管線路等 . ? 最小生成樹的求法： 破圈法 和 避圈法 河南城建學院 A Kruskal算法（或避圈法） 步驟如下： 1) 選擇邊 e1，使得 w(e1)盡可能??； 2) 若已選