圖與網(wǎng)絡(luò)分析graphtheoryandnetworkanalysis(已修改)
2025-08-13 12:36 本頁面
【正文】 圖與網(wǎng)絡(luò)分析 (Graph Theory and Network Analysis) 圖與網(wǎng)絡(luò)的基本知識 最短路問題 樹及最小樹問題 最大流問題 最小費(fèi)用最大流問題 B D A C A B C D 哥尼斯堡七空橋 一筆畫問題 一、 圖與網(wǎng)絡(luò)的基本知識 （一）、 圖與網(wǎng)絡(luò)的基本概念 E A D C B 一個(gè)圖是由點(diǎn)和連線組成。（連線可帶箭頭，也可不帶，前者叫弧，后者叫邊） 一個(gè)圖是由點(diǎn)集 和 中元素的無序?qū)Φ囊粋€(gè)集合 構(gòu)成的二元組 ， 記為 G =(V， E)， 其中 V 中的元素 叫做頂點(diǎn) ， V 表示圖 G 的點(diǎn)集合； E 中的元素 叫做邊 ， E 表示圖 G 的邊集合 。 ? ?jvV ?}{ keE ?jvkeVv1 v2 v3 v4 v5 v6 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 例 ? ?654321 ,, vvvvvvV ?},,{ 10987654321 eeeeeeeeeeE ，?},{ 211 vve ? },{ 212 vve ?},{ 323 vve ? },{ 434 vve ?},{ 315 vve ? },{ 536 vve ?},{ 537 vve ? },{ 658 vve ?},{ 669 vve ? },{ 6110 vve ?圖 1 如果一個(gè)圖是由點(diǎn)和邊所構(gòu)成的 ， 則稱其為無向圖 ， 記作G = (V， E)， 連接點(diǎn)的邊記作 [vi , vj]， 或者 [vj , vi]。 如果一個(gè)圖是由點(diǎn)和弧所構(gòu)成的，那么稱它為有向圖，記作 D=(V, A)， 其中 V 表示有向圖 D 的點(diǎn)集合， A 表示有向圖 D 的弧集合。一條方向從 vi指向 vj 的弧，記作 (vi , vj)。 v4 v6 v1 v2 v3 v5 V = {v1 , v2 , v3 , v4 , v5 , v6 }， A = {(v1 , v3 ) , (v2 , v1) , (v2 , v3 ) , (v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) } 圖 2 一條邊的兩個(gè)端點(diǎn)是相同的 ,那么稱為這條邊是環(huán)。 如果兩個(gè)端點(diǎn)之間有兩條以上的邊，那么稱為它們?yōu)槎嘀剡叀? 一個(gè)無環(huán)，無多重邊的圖稱為簡單圖，一個(gè)無環(huán)，有多重邊的圖稱為多重圖。 每一對頂點(diǎn)間都有邊相連的無向簡單圖稱為完全圖。 有向完全圖則是指任意兩個(gè)頂點(diǎn)之間有且僅有一條有向邊的簡單圖。 v1 v2 v3 v4 v5 v6 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 度為零的點(diǎn)稱為弧立點(diǎn)，度為 1的點(diǎn)稱為懸掛點(diǎn)。懸掛點(diǎn)的關(guān)聯(lián)邊稱為懸掛邊。度為奇數(shù)的點(diǎn)稱為奇點(diǎn)，度為偶數(shù)的點(diǎn)稱為偶點(diǎn)。 以點(diǎn) v為端點(diǎn)的邊的個(gè)數(shù)稱為點(diǎn) v 的度（次），記作 。 )(vd 圖中 d(v1)= 4， d(v6)= 4（ 環(huán)計(jì)兩度 ） 設(shè) G1=（ V1 , E1 ）， G2 =（ V2 ,E2 ） 如果 V2 ?V1 , E2 ?E1 稱 G2 是 G1 的子圖；如果 V2 = V1 , E2 ?E1 稱 G2 是 G1 的部分圖或支撐子圖。 v1 v2 v3 v4 v5 v6 v7 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 (a) e5 e7 v1 v2 v5 v6 v7 e1 e6 e8 (b) 子圖 v1 v2 v3 v4 v5 v6 v7 e1 e6 e7 e9 e10 e11 (c) 支撐子圖 在實(shí)際應(yīng)用中，給定一個(gè)圖 G=（ V， E） 或有向圖 D=（ V， A） ， 在 V中指定兩個(gè)點(diǎn)，一個(gè)稱為始點(diǎn)（或發(fā)點(diǎn)），記作 v1 ， 一個(gè)稱為終點(diǎn)（或收點(diǎn)），記作vn ， 其余的點(diǎn)稱為中間點(diǎn)。對每一條弧 ，對應(yīng)一個(gè)數(shù) ，稱為弧上的 “ 權(quán) ” 。通常把這種賦權(quán)的圖稱為網(wǎng)絡(luò)。 Avv ji ?),(jiw 由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序列稱為鏈。 如 :v0 ， e1， v1， e2， v2， e3 ， v3 ,… ,vn1 , en ， vn， 記作（ v0 ， v1 ， v2， v3 , … , vn1 ， vn ）， e3 v1 v2 v3 v4 v5 v6 e7 e8 e1 e2 e4 e5 e6 e9 e10 1圖中任意兩點(diǎn)之間均至少有一條通路，則稱此圖為連通圖，否則稱為不連通圖。 其鏈長為 n ， 其中 v0 ， vn 分別稱為鏈的起點(diǎn)和終點(diǎn) 。若鏈中所含的邊均不相同，則稱此鏈為簡單鏈；所含的點(diǎn)均不相同的鏈稱為初等鏈 , 也稱通路。 （ 二 ） 、 圖的矩陣表示 對于網(wǎng)絡(luò) （ 賦權(quán)圖 ） G=（ V， E） ， 其中邊 有權(quán) ， 構(gòu)造矩陣 ， 其中： 稱矩陣 A為網(wǎng)絡(luò) G的權(quán)矩陣 。 ),( ji vvjiw???????? EvvEvvwajijijiji ),(0),(nnjiaA ?? )(nnjiaA ?? )(???????? EvvEvvajijiji ),(0),(1 設(shè)圖 G=（ V， E） 中頂點(diǎn)的個(gè)數(shù)為 n， 構(gòu)造一個(gè) 矩陣 ，其中： 稱矩陣 A為網(wǎng)絡(luò) G的鄰接矩陣。 654321654321 010101101001010111101010001101111010vvvvvvvvvvvvB?????????????????????例 權(quán)矩陣為： 鄰接矩陣為： v5 v1 v2 v3 v4 v6 4 3 3 2 2 5 6 4 3 7 654321654321 030303302022020576305020007204346040vvvvvvvvvvvvA????????????????????? 二 、 樹及最小樹問題 已知有六個(gè)城市 ， 它們之間 要架設(shè)電話線 ， 要求任意兩個(gè)城市均可以互相通話 ， 并且電話線的總長度最短 。 v1 v2 v3 v4 v5 v6 一個(gè)連通的無圈的無向圖叫做樹。 樹中次為 1的點(diǎn)稱為樹葉，次大于 1的點(diǎn)稱為分支點(diǎn)。 樹 的性質(zhì)： （ 1）樹 必連通，但無回路（圈）。 （ 2） n 個(gè)頂點(diǎn)的樹必有 n1 條邊 。 （ 3） 樹 中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈（初等鏈）。 （ 4）樹 連通，但去掉任一條邊， 必變?yōu)椴贿B通。 （ 5） 樹 無回路（圈），但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰得到一個(gè)回路（圈）。 v1 v2 v3 v4 v5 v6 設(shè)圖 是圖 G=(V , E )的一支撐子圖， 如果圖 是一個(gè)樹 ,那么稱 K 是 G 的一個(gè)生成樹（支撐樹），或簡稱為圖 G 的樹。圖 G中屬于生成樹的邊稱為樹枝，不在生成樹中的邊稱為弦。 ),( 1EVK ?一個(gè)圖 G 有生成樹的充要條件是 G 是連通圖。 v1 v2 v3 v4 v5 v1
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1