北郵-通信網規(guī)劃理論 第二章--電信網規(guī)劃(一)-全文預覽
【正文】 d graph)，否則為 非連通圖 ( disconnected graph)；非連通圖中的每個 連通子圖 稱為 成分 (ponent)29 網絡中各端點的最短連接方法?最小生成樹算法最小生成樹? 多級輻射制的電信網絡、管理的指標體系、家譜、分類學、組織結構等都是典型的樹圖?任兩點之間有且只有一條路徑的圖稱為 樹 (tree)，記為 T 樹的性質 ：?最少邊的連通子圖，樹中必不存在回路?任何樹必存在次數為 1 的點?具有 n 個節(jié)點的樹 T 的邊恰好為 n?1 條，反之，任何有 n 個節(jié)點， n?1 條邊的連通圖必是一棵樹31圖的生成樹? 樹 T 是連通圖 G 的 生成樹 (spanning tree)，若 T 是 G的子圖且包含圖 G 的所有的節(jié)點? 如何找到一棵生成樹– 深探法 (depth first search)：任選一點標記為 0 點開始搜索，選一條未標記的邊走到下一點，該點標記為 1，將走過的邊標記；假設已標記到 i 點，總是從最新標記的點向下搜索，若從 i 點無法向下標記，即與 i 點相關聯的邊都已標記或相鄰節(jié)點都已標記，則退回到 i ?1 點繼續(xù)搜索，直到所有點都被標記– 廣探法 (breadth first search)：是一種有層級結構的搜索，一般得到的是樹形圖32最小生成樹（最小部分樹）例 通信網規(guī)劃中通信線路的連接問題 某一地區(qū)有若干個主要城市，現準備修建信息高速公路把這些城市連接起來， 使得從其中任何一個城市都可以經信息高速公路直接或間接到達另一個城市 . 假定已經知道了任意兩個城市之間修建信息高速公路的成本，那么應如何決定在哪些城市間修建信息高速公路，使得總成本最??？? 顯然，這要求在已知邊長度的網路圖中找最小生成樹 最小生成樹的算法 ：33? Kruskal 算法：將圖中所有邊按權值從小到大排列選所剩最小的邊加入邊集 T是否和前面加入是否和前面加入的邊構成回路的邊構成回路T 中是否有中是否有 n?1 條邊
環(huán)評公示相關推薦
鄂ICP備17016276號-1