通信網(wǎng)規(guī)劃理論(存儲版)
【正文】 圖 網(wǎng)路 (Network) 邊上具有表示連接強度的權(quán)值，如 wij 又稱 加權(quán)圖 (Weighted graph) 自環(huán) 平行邊 (parallel edges) 28 無向圖與有向圖 ? 弧 ? 邊 ? 關聯(lián)邊 ? 相鄰 (adjacent)節(jié)點 ? 鏈 (link) ? 圈 (loop) 相鄰邊 ?既沒有自環(huán)也沒有平行邊的圖稱為 簡單圖 (simple graph) ?在無向圖中，與節(jié)點相關聯(lián)邊的數(shù)目，稱為該節(jié)點的 “ 次 ” (degree)， 記為 d ；次數(shù)為奇數(shù)的點稱為 奇點 (odd),次數(shù)為偶數(shù)的點稱為 偶點 (even)；圖中都是偶點的圖稱為偶圖 (even graph) 29 無向圖與有向圖 ? 有向圖中，由節(jié)點指向外的弧的數(shù)目稱為正次數(shù)，記為 d+，指向該節(jié)點的弧的數(shù)目稱為負次數(shù)，記為 d– ? 次數(shù)為 0 的點稱為 孤立點 (isolated vertex) ，次數(shù)為 1 的點稱為 懸掛點 (pendant vertex) 圖中奇點的個數(shù)總是偶數(shù)個 ? 走過圖中所有邊且每條邊僅走一次的閉行走稱為 歐拉回路 偶圖一定存在歐拉回路 (一筆畫定理 ) ? 無向圖中，若任意兩點間至少存在一條路徑，則稱為連通圖 (connected graph)，否則為 非連通圖( disconnected graph)；非連通圖中的每個 連通子圖 稱為 成分 (ponent) 網(wǎng)絡中各端點的最短連接方法 ?最小生成樹算法 31 最小生成樹 ? 多級輻射制的電信網(wǎng)絡、管理的指標體系、家譜、分類學、組織結(jié)構(gòu)等都是典型的樹圖 C1C2C3C4根葉?任兩點之間有且只有一條路徑的圖稱為 樹 (tree)，記為 T 樹的性質(zhì) ： ?最少邊的連通子圖，樹中必不存在回路 ?任何樹必存在次數(shù)為 1 的點 ?具有 n 個節(jié)點的樹 T 的邊恰好為 n?1 條，反之，任何有 n 個節(jié)點， n?1 條邊的連通圖必是一棵樹 32 圖的生成樹 ? 樹 T 是連通圖 G 的 生成樹
教學課件相關推薦
鄂ICP備17016276號-1