離散數(shù)學(xué)圖論圖矩陣表示PPT學(xué)習(xí)教案

1、會計學(xué)1 離散數(shù)學(xué)圖論圖矩陣表示離散數(shù)學(xué)圖論圖矩陣表示 內(nèi)容：內(nèi)容：關(guān)聯(lián)矩陣，鄰接矩陣，可達(dá)矩陣。 重點：重點：1、有向圖，無向圖的關(guān)聯(lián)矩陣， 2、有向圖的鄰接矩陣。 了解：了解：有向圖的可達(dá)矩陣。 第1頁/共22頁 鄰接矩陣鄰接矩陣 存儲原則存儲原則: 存儲結(jié)點集和邊集的信息存儲結(jié)點集和邊集的信息. （1 1）存儲結(jié)點集；）存儲結(jié)點集； （2 2）存儲邊集：）存儲邊集： 存儲每兩個結(jié)點存儲每兩個結(jié)點 是否有關(guān)系。是否有關(guān)系。 第2頁/共22頁 ij a i v 12 , p Vv vv 定義 1.6.2設(shè) 的頂點集為 ，用 表示 中頂點 與 之間的邊數(shù)。稱矩陣 為 的 鄰接矩陣。 ( , )

2、GV E Gj v( )() ijp p M Ga G 從圖的鄰接矩陣的定義容易得出以下性質(zhì)： (1) 是一個對稱矩陣； (2)若 為無環(huán)圖。則 中第 行(列)的元素之和等于頂點 的度 數(shù)； (3) 兩個圖 與 同構(gòu)的充要條件是存在一個置換矩陣 ，使得 。 ( )M G ( )M G( )M G i i v GHP ( )() T M GP M H P 對應(yīng)的鄰接矩 陣 12345 1 2 3 4 5 01011 10211 () 02000 11011 11010 vvvvv v v MG v v v 例2下圖所示 的鄰接矩陣為： G A( G) A( G) A( G) A( G) A( G

3、) A( G) 相當(dāng)于將單位 矩陣中相應(yīng)的 行與行，或者 列與列互換的 矩陣 第3頁/共22頁 v1 v2 v3 v4 圖G1 va vb vc vd 圖G2 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 A1 1 2 3 4 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 A2 a b c d v1va v2vb v3vc v4vd 第4頁/共22頁 所以 n k=1 v k viv j 長度長度 =1 長度長度=l 第5頁/共22頁 第6頁/共22頁 2 34 0100010100 1010002000 0100010100 0000100001 0001

4、000010 0200020200 2020004000 0200020200 0000100010 0001000001 AA AA 第7頁/共22頁 第8頁/共22頁 設(shè)圖，如下圖所示 討論 （1）圖G的鄰接矩陣中的元素為0和1，又稱為布爾矩陣； （2）圖G的鄰接矩陣中的元素的次序是無關(guān)緊要的，進(jìn)行行和行 、列和列的交換，則得到相同矩陣。 若有二個簡單有向圖，則可得到二個對應(yīng)的鄰接矩陣，若對某 一矩陣進(jìn)行行和行、列和列之間的交換后得到和另一矩陣相同的 矩陣，則此二圖同構(gòu)。 （3）當(dāng)有向圖中的有向邊表示關(guān)系時，鄰接矩陣就是關(guān)系矩陣； （4）零圖的鄰接矩陣稱為零矩陣，即矩陣中的所有元素均為0；

5、 （5）在圖的鄰接矩陣中， 行中1的個數(shù)就是行中相應(yīng)結(jié)點的引出次數(shù) 列中1的個數(shù)就是列中相應(yīng)結(jié)點的引入次數(shù) A 第9頁/共22頁 A T A T AA AAT 主對角線上的數(shù)表 示結(jié)點i（或j）的 引出次數(shù)。 主對角線上的數(shù)表示 結(jié)點i（或j）的引入次 數(shù)。 第10頁/共22頁 AAA2 AAA 23 AAA 34 表示i和j之間具有長度為 2的通路數(shù)， 表示i和j之間具有長度為 3的通路數(shù)， 表示i和j之間具有長度為 4的通路數(shù)， 2 A 3 A 4 A 第11頁/共22頁 bij表示從結(jié)點vi到vj有長度分別為1，2，3 ，4的不同通路總數(shù)。 此時， bij0，表示從vi到vj是可達(dá)的。

6、4321 4 AAAAB 第12頁/共22頁 1、設(shè)有向圖,DV E 12 , n Vv vv， EmD的鄰接矩陣 (1) () ij n n A Da ， 其中指鄰接到的邊的條數(shù) (非負(fù)整數(shù))。 (1) ij a i v j v 第13頁/共22頁 第14頁/共22頁 有向圖(下圖所示)，求D()A D。 解：解： 1210 0010 () 0001 0010 A D 第15頁/共22頁 一個圖 由它的頂點與邊的關(guān)聯(lián)關(guān)系唯一 確定； ( , )GV E ( )() ijp q B Gb j e i vij b 12 , p Vv vv 定義定義 1.6.1 設(shè) 的頂點集和邊集分別為 ， 。用

7、 表示頂點 與邊 關(guān)聯(lián)的次數(shù)(0， 1或2)，稱矩陣 為 的關(guān)聯(lián)矩陣。 ( , )GV E 12 , q Ee ee G 第16頁/共22頁 G 下圖所示 的關(guān)聯(lián)矩陣為： 對應(yīng)的關(guān)聯(lián)矩 陣 123456789 1 2 3 4 5 000010011 111000101 ( ) 110000000 001211000 000001110 eeeeeeeee v v B G v v v 從圖的關(guān)聯(lián)矩陣的定義容易得出以下性質(zhì)： (1) 的每一列元素之和均為2； (2) 的每一行元素之和等于對應(yīng)頂點的度數(shù)。 (3)若某行元素全為0，則對應(yīng)的頂點為孤立點。 (4)重邊所對應(yīng)的列完全相同。 ( )B G

8、( )B G 2 1 0 jij jij ji exe exe ex 關(guān)聯(lián)于 ， 是自環(huán) 關(guān)聯(lián)于 ， 不是自環(huán) 不關(guān)聯(lián)與 = ij b 第17頁/共22頁 1、設(shè)有向圖有向圖,DV E 12 , n Vv vv， 12 , m Ee ee，的關(guān)聯(lián)矩陣 D ()() ijn m M Dm ， 1 0 1 ij ijij ij ve mve ve 為 的始點 與 不關(guān)聯(lián) 為 的終點 其中 2 1 1 0 ji jij jij ji ex Dexe Dexe ex 是自環(huán)，且關(guān)聯(lián)與 在 中 以 為起點， 不是自環(huán) 在 中 以 為終點， 不是自環(huán) 與 不關(guān)聯(lián) 第18頁/共22頁 有向圖(下圖所示)，求D()M D。 11000 10111 () 00001 01110 M D 解：解： A(D) A(D) 第19頁/共22頁 設(shè)為有向圖，,DV E 12 , n Vv vv 令1 ii p ，1