【正文】 絡(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)等都是典型的樹圖 C1C2C3C4根葉?任兩點(diǎn)之間有且只有一條路徑的圖稱為 樹 (tree)，記為 T 樹的性質(zhì) ： ?最少邊的連通子圖，樹中必不存在回路 ?任何樹必存在次數(shù)為 1 的點(diǎn) ?具有 n 個(gè)節(jié)點(diǎn)的樹 T 的邊恰好為 n?1 條，反之，任何有 n 個(gè)節(jié)點(diǎn)， n?1 條邊的連通圖必是一棵樹 32