第九章 圖與網(wǎng)絡(luò)分析

1、1第九章圖與網(wǎng)絡(luò)優(yōu)化9.1重點、難點提要一、圖與網(wǎng)絡(luò)的基本概念1無向圖設(shè)是一個有個頂點的非空集合：；是一個有條Vn21nvvvV??Em無向邊的集合：，則稱和這兩個集合構(gòu)成了一個無向21meeeE??VE圖，記為。)(EVG?中任一條邊若連接頂點和，則記該邊為（或），并稱Eeuv][vue?][uv與為無向邊的兩個端點，且邊與頂點及相關(guān)聯(lián)，頂點和頂點相uveeuvuv鄰。對于圖，頂點集和無向邊集也可以分別表示為和。GVE)(GV)(GE

2、一般用和表示圖中頂點個數(shù)和邊的條數(shù)。||V||E無向圖中有平行邊、簡單圖、完備圖、子圖、生成子圖、導(dǎo)出子圖、鏈、初等鏈、回路、連通圖、割邊、賦權(quán)連通圖和網(wǎng)絡(luò)等基本概念。其中賦權(quán)連通圖是網(wǎng)絡(luò)優(yōu)化考慮的一個重要對象。根據(jù)實際問題的需要，每條邊的權(quán)重可以是時間、距離、成本等相應(yīng)的數(shù)值。2有向圖設(shè)是一個有個頂點的非空集合：；是一個有條弧Vn21nvvvV??Em的集合：，則稱和這兩個集合構(gòu)成了一個有向圖，記為21meeeE??VE。)(EVD?

3、有向圖中有弧、入度、出度、平行邊、孤立點、簡單圖、完備圖、基本圖、子圖、導(dǎo)出子圖、導(dǎo)出生成子圖、同構(gòu)圖、鏈、初等鏈、路、路徑、回路、賦權(quán)有向圖和網(wǎng)絡(luò)等基本概念。和賦權(quán)連通圖一樣，賦權(quán)有向圖也是網(wǎng)絡(luò)優(yōu)化研究的一個重要對象。3圖的矩陣表示(1)無向圖的關(guān)聯(lián)矩陣和鄰接矩陣設(shè)為一個無向圖，其中，，)(EVG???nvvvV21????meeeE21??圖的關(guān)聯(lián)矩陣為，其中G??mnijaA??????上上上上上上上jijiijeveva01關(guān)聯(lián)

4、矩陣描述的是無向圖頂點與邊的關(guān)聯(lián)狀態(tài)。3般用表示。T結(jié)論1：如果是一棵樹，且，則下列命題等價。)(EVT?mEnV??||||（1）連通且無回路；T（2）無回路且只有條邊，即；T1?n1??nm（3）連通且只有條邊；T1?n（4）無回路，但在不相鄰的任意兩個頂點之間加上一條邊，恰好得到一T個回路；（5）連通，但去掉的任何一條邊，將不再連通；TTT（6）的任意兩個頂點之間有且僅有一條初等鏈。T(2)支撐樹支撐樹——若是無向圖的生成子圖，并

5、且同時又是樹，則稱是TGTTG的支撐樹，也稱為生成樹。結(jié)論2圖有支撐樹的充分必要條件是有支撐樹的充分必要條件是為連通圖。為連通圖。)(EVG?G(3)最小支撐樹給定一個網(wǎng)絡(luò)，設(shè)是的支撐樹，稱中所有邊)(wEVG?)(1EVT?GT的權(quán)數(shù)之和為樹的權(quán)，記為，即T)(Gw???1)()(EeewTw如果的支撐樹滿足G)(EVT?或)(min)(1TwTwE??????11)(min)(EeEEeewew則稱為的最小支撐樹，簡稱最小樹。TG對