通信網(wǎng)規(guī)劃理論-在線瀏覽
2024-12-20 16:28本頁面
【正文】 社， 2020年 8月。 請?jiān)O(shè)計(jì)一條最短的信息回路 (從起點(diǎn)出發(fā) ， 經(jīng)過網(wǎng)絡(luò)中的每一條線路至少一次 ， 最后返回起點(diǎn) )？ 由于這一問題是我國復(fù)旦大學(xué) 管梅谷教授 1960年首先提出的 ，所以國際上稱之為中國郵遞員問題 . 網(wǎng)絡(luò)規(guī)劃問題的例子 例 (TSPTraveling Salesman Problem) 一條信息將走遍網(wǎng)絡(luò)中的所有結(jié)點(diǎn) ,最后返回起始點(diǎn) 。13e45圖 網(wǎng)路 (Network) 邊上具有表示連接強(qiáng)度的權(quán)值，如 wij 又稱 加權(quán)圖 (Weighted graph) 自環(huán) 平行邊 (parallel edges) 28 無向圖與有向圖 ? 弧 ? 邊 ? 關(guān)聯(lián)邊 ? 相鄰 (adjacent)節(jié)點(diǎn) ? 鏈 (link) ? 圈 (loop) 相鄰邊 ?既沒有自環(huán)也沒有平行邊的圖稱為 簡單圖 (simple graph) ?在無向圖中，與節(jié)點(diǎn)相關(guān)聯(lián)邊的數(shù)目，稱為該節(jié)點(diǎn)的 “ 次 ” (degree)， 記為 d ；次數(shù)為奇數(shù)的點(diǎn)稱為 奇點(diǎn) (odd),次數(shù)為偶數(shù)的點(diǎn)稱為 偶點(diǎn) (even)；圖中都是偶點(diǎn)的圖稱為偶圖 (even graph) 29 無向圖與有向圖 ? 有向圖中，由節(jié)點(diǎn)指向外的弧的數(shù)目稱為正次數(shù)，記為 d+，指向該節(jié)點(diǎn)的弧的數(shù)目稱為負(fù)次數(shù)，記為 d– ? 次數(shù)為 0 的點(diǎn)稱為 孤立點(diǎn) (isolated vertex) ，次數(shù)為 1 的點(diǎn)稱為 懸掛點(diǎn) (pendant vertex) 圖中奇點(diǎn)的個(gè)數(shù)總是偶數(shù)個(gè) ? 走過圖中所有邊且每條邊僅走一次的閉行走稱為 歐拉回路 偶圖一定存在歐拉回路 (一筆畫定理 ) ? 無向圖中，若任意兩點(diǎn)間至少存在一條路徑，則稱為連通圖 (connected graph)，否則為 非連通圖( disconnected graph)；非連通圖中的每個(gè) 連通子圖 稱為 成分 (ponent) 網(wǎng)絡(luò)中各端點(diǎn)的最短連接方法 ?最小生成樹算法 31 最小生成樹 ? 多級(jí)輻射制的電信網(wǎng)絡(luò)、管理的指標(biāo)體系、家譜、分類學(xué)、組織結(jié)構(gòu)等都是典型的樹圖
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1