圖論基礎通風網(wǎng)絡ppt課件(編輯修改稿)
2025-06-02 23:19 本頁面
【文章內(nèi)容簡介】 432143210110101111010110vvvvvvvvA ?47 1 圖論基礎 圖的矩陣表示 — 鄰接矩陣 思考 （ 2）如何構(gòu)造非簡單有向圖的鄰接矩陣？ e1 e2 e4 e5 e3 v1 v3 v2 v4 e6 432143210110002100010000vvvvvvvvA ?48 1 圖論基礎 圖的矩陣表示 — 關(guān)聯(lián)矩陣 2）關(guān)聯(lián)矩陣 表示圖的節(jié)點和邊的關(guān)聯(lián)關(guān)系的矩陣。 nmijbB ?? )(1,1,0,iji j ib i j iij???? ???節(jié) 點 與 邊 關(guān) 聯(lián) , 且 為 始 節(jié) 點 ；節(jié) 點 與 邊 關(guān) 聯(lián) , 且 為 終 節(jié) 點 ；節(jié) 點 與 邊 不 關(guān) 聯(lián) 。構(gòu)造方陣 其中： （ 1）完全關(guān)聯(lián)矩陣 49 1 圖論基礎 圖的矩陣表示 — 關(guān)聯(lián)矩陣 1110104011100300011121000011???????fedcbaBeb a d f 2 1 3 4 c e 矩陣 Be的行向量是線性相關(guān)的，矩陣的秩 R=3（ 41） . 50 1 圖論基礎 圖的矩陣表示 — 關(guān)聯(lián)矩陣 （ 2）基本關(guān)聯(lián)矩陣 在 m階連通圖 G的完全關(guān)聯(lián)矩陣 Be中 ,劃去任一行后 ,所得的 (m1) n矩陣 ,稱為圖 G的基本關(guān)聯(lián)矩陣，簡稱關(guān)聯(lián)矩陣，記作 B。劃去的對應點稱為 參考點 。 b a d f 1 2 3 4 c e 411101030111002022111??????fedcbaB基本關(guān)聯(lián)矩陣線性獨立。 通常， 通風網(wǎng)絡中劃去的節(jié)點為大氣節(jié)點。 51 1 圖論基礎 圖的矩陣表示 — 關(guān)聯(lián)矩陣 思考 e1 e2 e4 e5 e3 v1 v3 v2 v4 （ 1）寫出下圖的關(guān)聯(lián)矩陣。 52 1 圖論基礎 圖的矩陣表示 — 關(guān)聯(lián)矩陣 思考 （ 2）根據(jù)下面的關(guān)聯(lián)矩陣，繪制對應的網(wǎng)絡圖。 1 2 3 4 5 6 71 1 1 0 0 0 0 02 1 0 1 0 1 0 03 0 0 1 1 0 1 04 0 1 0 1 0 0 15 0 0 0 0 1 1 1ee e e e e e evvBvvv??????????????????53 1 圖論基礎 圖的矩陣表示 — 回路矩陣 3）回路矩陣 表示一個圖的邊與回路關(guān)系的矩陣。 （ 1）完全回路矩陣 1 , ,1 , ,0,ijj i jC e j i jji???????邊 在 回 路 內(nèi) 且 邊 與 回 路 方 向 一 致邊 在 回 路 內(nèi) 且 邊 與 回 路 方 向 相 反邊 不 在 回 路 內(nèi)imax=2nm+11 jmax=n 互異回路：至少有一條邊不同的回路 包含圖的所有互異回路的矩陣。 54 1 圖論基礎 圖的矩陣表示 — 回路矩陣 6 d c b a 4 1 5 2 3 回路個數(shù)： 264+11=7 7654321011011011100101001110111101110110010000111654321CCCCCCCCe????????55 1 圖論基礎 圖的矩陣表示 — 回路矩陣 6 d c b a 4 1 5 2 3 7654321011011011100101001110111101110110010000111654321CCCCCCCCe????????)1,3,2(1 ???C)5,6,2(2 ?C)4,6,3,2(3 ?C214 CCC ??315 CCC ??326 CCC ??3217 CCCC ???若生成樹為 T=(2,3,6)，余樹弦為（ 1,4,5） 56 1 圖論基礎 圖的矩陣表示 — 回路矩陣 完全回路矩陣的特點 1) 每一行對應一個回路； 2) 每行非零元素組成一個回路； 3) 行數(shù)： 2nm+1。 4) 各行之間并非線性獨立； 5) 秩為 nm+1（獨立回路數(shù)）。 7654321011011011100101001110111101110110010000111654321CCCCCCCCe????????獨立回路矩陣能反映完全回路性質(zhì)，沒有必要寫完全回路矩陣？ 57 1 圖論基礎 圖的矩陣表示 — 回路矩陣 互異回路 與 獨立回路 的 區(qū)別 回路數(shù)方面 線性相關(guān)方面 獨立回路數(shù)為 nm+1 互異回路為 2nm+11個 獨立回路是線性獨立的 互異回路則是線性相關(guān)的 58 1 圖論基礎 圖的矩陣表示 — 回路矩陣 （ 2）基本回路矩陣 基本回路矩陣一般是在某個生成樹的基礎上提出的。 1 , ,1 , ,0,ijj i jC j i jji???????邊 在 回 路 內(nèi) 且 邊 與 回 路 方 向 一 致邊 在 回 路 內(nèi) 且 邊 與 回 路 方 向 相 反邊 不 在 回 路 內(nèi)imax=nm+1 jmax=n 321101110110010000111654321CCCC???6 d c b a 4 1 5 2 3 C1 C2 C3 若生成樹為 T=(2,3,6)，余樹弦為（ 1,4,5） 59 1 圖論基礎 圖的矩陣表示 — 回路矩陣 ? ?111100101010011001632451,???? fCIC1)基本回路矩陣的秩等于： nm+1 2)余樹弦在前、樹枝在后分為兩部分： 6 d c b a 4 1 5 2 3 C1 C2 C3 生成樹為 T=(2,3,6)，余樹弦為（ 1,4,5） 基本回路矩陣的性質(zhì) 60 1 圖論基礎 圖的矩陣表示 — 割集矩陣 4）割集矩陣 （ 1）完全割集矩陣 表達圖的邊與割集關(guān)系的矩陣 包含圖 G的全部割集的矩陣 1 , S 。1 , 。0 , .ii j iijS j SjS???? ???若 邊 在 割 集 內(nèi) ， 且 與 割 集 同 向若 邊 在 割 集 內(nèi) ， 且 與 割 集 反 向邊 不 在 割 集 內(nèi)61 1 圖論基礎 圖的矩陣表示 — 割集矩陣 7654321110101010110011011001101111000101110100011SSSSSSSfedcbaSe???????????62 1 圖論基礎 圖的矩陣表示 — 割集矩陣 取生成樹 ),( ecaT ?余樹弦 ),( fdb可發(fā)現(xiàn) ),(),(),(321fedSfbcdSfbaS???),(),(),(),(3217326315214fecaSSSSebcSSSedbaSSScdaSSS?????????????7654321110101010110011011001101111000101110100011SSSSSSSfedcbaSe???????????63 1 圖論基礎 圖的矩陣表示 — 割集矩陣 （ 2）基本割集矩陣 ),(100110010111001101ISecafdbS f?????同一個圖，有不同的生成樹，故基本割集也不相同。 列：余樹在前，樹枝在后； 行：按樹枝在矩陣內(nèi)的列序排序 1 1 0 0 0 10 1 1 1 0 10 0 0 1 1 1a b c d e fS??
教學課件相關(guān)推薦
鄂ICP備17016276號-1