運(yùn)籌學(xué)圖與網(wǎng)絡(luò)ppt課件-文庫吧資料
2025-05-18 13:31本頁面
【正文】 lete) ? 哈密爾頓路徑：包含圖中所有點(diǎn)的路徑 ? 為什么說找兩點(diǎn)間的最長路是非常困難的問題？ 中國郵遞員問題 ? 中國郵遞員問題 (Chinese Postman Problem, CPP)是由我國管梅谷教授于 1962年首先提出并發(fā)表的 ? 問題是從郵局出發(fā)，走遍郵區(qū)的所有街道至少一次再回到郵局，走什么路由才能使總的路程最短？ ? 如果街區(qū)圖是一個(gè)偶圖，根據(jù)定理 3，一定有歐拉回路， CPP問題也就迎刃而解了 ? 若街區(qū)圖不是偶圖，則必然有一些街道要被重復(fù)走過才能回到原出發(fā)點(diǎn) ? 顯然要在奇次點(diǎn)間加重復(fù)邊 ? 如何使所加的邊長度最少 ? 歸結(jié)為求奇次點(diǎn)間的最小 匹配 ( minimum weighted match) — 由 Edmons 給出多項(xiàng)式算法 (1965) ABC D旅行推銷員問題 (Traveling Salesman Problem) ? TSP：設(shè) v1, v2, ...,vn 為 n 個(gè)已知城市，城市之間的旅程也是已知的，要求推銷員從 v1出發(fā)，走遍所有城市一次且僅一次又回到出發(fā)點(diǎn)，并使總旅程最短 ? 這種不允許點(diǎn)重復(fù)的旅行推銷員問題就是最小哈密爾頓回路問題 ? 一般旅行推銷員問題 (GTSP)：允許點(diǎn)重復(fù)的 TSP ? 典型的應(yīng)用： ? 鄉(xiāng)郵員的投遞路線 ? 郵遞員開郵箱取信的路線問題 ? 郵車到各支局的轉(zhuǎn)趟問題 ? 運(yùn)鈔 ? 送奶、送水 ? … . 網(wǎng)絡(luò)最短樹問題 ? 最短樹問題 的一般提法是：選取網(wǎng)絡(luò)中的部分圖 ，使得網(wǎng)絡(luò)連通 ， 且使總權(quán)數(shù)最短 。 ? 網(wǎng)絡(luò) 賦權(quán)的圖 ? 權(quán) 程度的度量 ， 數(shù)量描述 。 6. 每一對(duì)頂點(diǎn)之間有一條且僅有一條鏈 。 4. 無圈 ， 但若任意增加一條邊 ， 則可得到一個(gè)且僅一個(gè)圈 。 2. 無圈 ， q=p1。 ? 一個(gè)連通的無圈圖則稱為 樹 ， 一個(gè)林的每個(gè)連通子圖都是一個(gè)樹 。 ? 除起點(diǎn)和終點(diǎn)外點(diǎn)均不相同的回路稱為 初等回路 。 ? 當(dāng)路的起點(diǎn)與終點(diǎn)相同，即 u=v時(shí)，稱作一條 回路 。 ? 從頂點(diǎn) u指向 υ的弧 a，記作 a=(u,v),(u,v)≠(v,u)，其中 u稱為 a的起點(diǎn)， v稱為 a的終點(diǎn)，這樣的圖稱為有向圖 。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 e1 e2 e3 e4 e5 v2 v3 v1 有向圖 ? 在有些圖中，邊是沒有方向的，即 [u,v]=[v,u]，這種圖稱為 無向圖 。 ? 部分圖 若 V1=V2，E1?E2 ，則稱 G1為 G2的一個(gè) 部分圖 。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 e1 e2 e3 e4 e5 v2 v3 v1 必須指出，并不是從圖G2中任選一些頂點(diǎn)和邊在一起就組成 G2的子圖G1，而只有在 G2中的一條邊以及連接該邊的兩個(gè)端點(diǎn)均選入 G1時(shí)， G1才是 G2的子圖。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 連通的意義 ? 連通是一個(gè)很重要的概念，如果一個(gè)問題所對(duì)應(yīng)的圖是一個(gè)不連通圖，則該問題一定可以分解成互不相關(guān)的子問題來加以研究，即可以把不連通圖分解成連通的子圖來研究。 143746211 , ????? eeee連通性 ? 若一個(gè)圖 G的任意兩點(diǎn)之間均至少有一條通路（初等鏈）連接起來，則稱這個(gè)圖 G是一個(gè) 連通圖 ，否則稱作不連通圖 。除起點(diǎn)和終點(diǎn)外點(diǎn)均不相同的閉鏈，稱為 初等回路 或稱為 圈 。 ? 例如圖中 e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 是一條鏈，且是開鏈，也是簡單鏈，但不是初等鏈，因?yàn)?v1出現(xiàn)兩次。 nnn eee ????? , 122110 ??e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 簡單鏈 ? 若鏈中所含的邊均不相同，則稱為 簡單鏈 ；若點(diǎn)均不相同，則稱為 初等鏈 或 通路 。 ? v0稱為鏈的 起點(diǎn) ， vn稱為鏈的 終點(diǎn) 。 ? 設(shè) V1和 V2分別是圖 G中次數(shù)為奇數(shù)和偶數(shù)的頂點(diǎn)集合。 ? 定理 1 所有頂點(diǎn)的次的和，等于所有邊數(shù)的 2倍。 ? 圖中的點(diǎn) v5即為懸掛點(diǎn) ，邊 e9即為懸掛邊 ， 而點(diǎn) v6則是弧立點(diǎn) 。 e1 e2 e3 e4 e5 v2 v3 v1 v4 v
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1