《運籌學圖與網(wǎng)絡》ppt課件-全文預覽
【正文】 v4 (3,1) v2 3 5 2 7 5 3 1 5 1 2 V1 （ 0,s) v5 (8,4) v6 (2,1) v3 (3,3) v4 ? 例 2 電信公司準備在甲、乙兩地沿路架設一條光纜線，問如何架設使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。如果上述的弧的集合不是空集，則轉下一步。 ? 最短路問題是網(wǎng)絡分析中的一個基本問題 ，它不僅可以直接應用于解決生產(chǎn)實際的許多問題 ， 如管道鋪設 、 線路安排 、 廠區(qū)布局等 ，而且經(jīng)常被作為一個基本工具 ， 用于解決其它的優(yōu)化問題 。顯然哈密爾頓回路有且只有 n 條邊，若|V|=n ? 連通圖具有哈密爾頓回路的充分必要條件是什么？這個問題是由愛爾蘭數(shù)學家哈密爾頓 1859年提出的，但至今仍未解決 ? 歐拉回路是對邊進行訪問的問題，哈密爾頓回路是對點進行訪問的問題 ? 搜索哈密爾頓回路的難度是 NPplete ? 任兩點間都有邊的圖稱為完全圖 (或全連接圖 ) ? 完全圖中有多少個不同的哈密爾頓回路？ (n–1)!/2 ? 完全圖中有多少個邊不相交的哈密爾頓回路？ (n–1)/2 ? 最小哈密爾頓回路問題 (NPplete) ? 哈密爾頓路徑：包含圖中所有點的路徑 ? 為什么說找兩點間的最長路是非常困難的問題？ 中國郵遞員問題 ? 中國郵遞員問題 (Chinese Postman Problem, CPP)是由我國管梅谷教授于 1962年首先提出并發(fā)表的 ? 問題是從郵局出發(fā)，走遍郵區(qū)的所有街道至少一次再回到郵局，走什么路由才能使總的路程最短？ ? 如果街區(qū)圖是一個偶圖，根據(jù)定理 3，一定有歐拉回路， CPP問題也就迎刃而解了 ? 若街區(qū)圖不是偶圖，則必然有一些街道要被重復走過才能回到原出發(fā)點 ? 顯然要在奇次點間加重復邊 ? 如何使所加的邊長度最少 ? 歸結為求奇次點間的最小 匹配 ( minimum weighted match) — 由 Edmons 給出多項式算法 (1965) ABC D旅行推銷員問題 (Traveling Salesman Problem) ? TSP：設 v1, v2, ...,vn 為 n 個已知城市，城市之間的旅程也是已知的，要求推銷員從 v1出發(fā)，走遍所有城市一次且僅一次又回到出發(fā)點，并使總旅程最短 ? 這種不允許點重復的旅行推銷員問題就是最小哈密爾頓回路問題 ? 一般旅行推銷員問題 (GTSP)：允許點重復的 TSP ? 典型的應用： ? 鄉(xiāng)郵員的投遞路線 ? 郵遞員開郵箱取信的路線問題 ? 郵車到各支局的轉趟問題 ? 運鈔 ? 送奶、送水 ? … . 網(wǎng)絡最短樹問題 ? 最短樹問題 的一般提法是：選取網(wǎng)絡中的部分圖 ，使得網(wǎng)絡連通 ， 且使總權數(shù)最短 。 6. 每一對頂點之間有一條且僅有一條鏈 。 2. 無圈 ， q=p1。 ? 除起點和終點外點均不相同的回路稱為 初等回路 。 ? 從頂點 u指向 υ的弧 a，記作 a=(u,v),(u,v)≠(v,u)，其中 u稱為 a的起點， v稱為 a的終點，這樣的圖稱為有向圖 。 ? 部分圖 若 V1=V2，E1?E2 ，則稱 G1為 G2的一個 部分圖 。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 連通的意義 ? 連通是一個很重要的概念，如果一個問題所對應的圖是一個不連通圖，則該問題一定可以分解成互不相關的子問題來加以研究，即可以把不連通圖分解成連通的子圖來研究。除起點和終點外點均不相同的閉鏈，稱為 初等回路 或稱為 圈 。 nnn eee ????? , 122110 ??e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 簡單鏈 ? 若鏈中所含的邊均不相同，則稱為 簡單鏈 ；若點均不相同，則稱為 初等鏈 或 通路 。 ? 設 V1和 V2分別是圖 G中次數(shù)為奇數(shù)和偶數(shù)的頂點集合。 ? 圖中的點 v5即為懸掛點 ，邊 e9即為懸掛邊 ， 而點 v6則是弧立點 。 ? 含有多重邊的圖稱作 多重圖 。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 點邊關系 ? 若點 u和 v與同一條邊相關聯(lián) ， 則 u和 v為 相鄰點 ；若兩條邊 ei和 ej有同一個端點 ， 則稱 ei與 ej為 相鄰邊 。 圖的表示 ],[ 211 ???e ],[ 212 ???e],[ 413 ???e ],[ 314 ???e],[ 315 ???e ],[ 426 ???e],[ 437 ???e ],[ 448 ???e],[ 549 ???e),(),( 987654321654321 eeeeeeeeeE ?? ???????e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 點與邊 ? 頂點數(shù) 集合
教學課件相關推薦
鄂ICP備17016276號-1