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

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

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

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

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

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