離散數(shù)學(xué)ppt課件(參考版)
2025-05-05 05:11本頁面
【正文】 離散數(shù)學(xué) 71 矩陣與圖的連通性 矩陣與圖的連通性 無向線圖 G是連通圖當(dāng)且僅當(dāng)它的可達性矩陣 P的所有元素都 均為 1； 有向線圖 G是強連通圖當(dāng)且僅當(dāng)它的可達性矩陣 P的所有元素 都均為 1； 有向線圖 G是單側(cè)連通圖當(dāng)且僅當(dāng)它的可達性矩陣 P及其轉(zhuǎn)置 矩陣 PT經(jīng) “ 布爾求和 ” 運算后所得矩陣 P1＝ P∨P T中除對角線以 外的其余元素均為 1； 有向線圖 G是弱連通圖當(dāng)且僅當(dāng)它的鄰接矩陣 A及其轉(zhuǎn)置矩陣 AT經(jīng) “ 布爾求和 ” 運算后作為新的鄰接矩陣 B＝ A∨A T而求出的可 達性矩陣 PB中所有元素均為 1。 顯然 M(r1)(G)有一個 (r1)階子陣 ， 其行列式的值不為 0， 故 M(r1)(G)的秩至少為 r1。 如果 M’(G1)的第一列全為零 ， 則可將 M’(G1)的非零列與第一列對調(diào) ， 不影響完全關(guān)聯(lián)矩陣的秩數(shù) 。 離散數(shù)學(xué) 68 證明 離散數(shù)學(xué) 69 證明（續(xù)） 證明 由于 M’(G1)是 G1的完全關(guān)聯(lián)矩陣 ， 而 G1是由 G的兩個結(jié)點 vi和 vj合并而得到 。 ⑵ 設(shè) M(G)的第一列對應(yīng)邊 e， 且 e的端點為 vi和 vj， 調(diào)整行序使第 i行為第一行 ， 這時 M(G)的首列僅在第 1行和第 j行為 1， 其余各元素均為 0， 再把第一行加到第 j行上去則得到矩陣 M’(G)。 證明 這里對無向圖進行證明 。 b) vi與 vj都是邊 er的端點 ， 那么合并后在 G’中 er成為 vi,j的自回路 ， 按規(guī)定應(yīng)該被刪去 。 因為若有 關(guān)項中第 r個對應(yīng)分量有 ， 則說明 vi與 vj兩者之中只有一個結(jié)點是邊 er的端點 ， 且將這兩 個結(jié)點合并后的結(jié)點 vi,j仍是 er的端點 。 離散數(shù)學(xué) 63 例： 例： 如對于圖，可寫完全關(guān)聯(lián)矩陣： 離散數(shù)學(xué) 64 邊的合并 對圖 G的完全關(guān)聯(lián)矩陣中的兩個行相加定義如下： 若記 vi對應(yīng)的行為 ， 將第 i行與第 j行相加 ， 規(guī)定 為：對有向圖是指對應(yīng)分量的加法運算 ， 對無向圖是 指對應(yīng)分量的模 2的加法運算 ， 把這種運算記作 iv?ijji vvv ??? ??離散數(shù)學(xué) 65 邊的合并 關(guān)聯(lián)矩陣的加法運算 例： 圖 (a)中使 v4和 v5合并得到圖 (b)。 ⑵每一行元素 ” 1”的個數(shù)對應(yīng)于 ， ” 1”的個數(shù)對應(yīng)于 。 離散數(shù)學(xué) 61 定義 定義 給定簡單有向圖 G=〈 V ， E〉 ， V={v1,v2,… vp} ， E={e1,e2,… eq} ，p q階矩陣 M(G)=(mij)， 其中 稱 M(G)為 G的完全關(guān)聯(lián)矩陣 。 ⑷兩個平行邊其對應(yīng)的兩列相同。 ⑵每一行元素的和數(shù)對應(yīng)于 。）（）（）（????????????????????1111111111111111A......AAAP n32離散數(shù)學(xué) 58 三：完全關(guān)聯(lián)矩陣 三：完全關(guān)聯(lián)矩陣 定義 給定無向圖 G， 令 v1,v2,… ,vp和 e1,e2,… ,eq分別記為 G的結(jié)點和邊 ， 則矩陣 M(G)=(mij)， 其中 稱 M(G)為完全關(guān)聯(lián)矩陣。???????????????1111111111111111P離散數(shù)學(xué) 56 利用布爾求乘和布爾求和的運算直接求可達性矩陣 P＝ A?A(2)?A(3)?...?A(n) A(m)＝ A?A?A?...?A (m＝ 1,2,3,… n) 若把鄰接矩陣看作是結(jié)點集 V上關(guān)系 R的關(guān)系矩陣，則可達性矩陣 P即為 MR＋ ， 因此可達性矩陣可以用 Warshall算法計算 2) 利用布爾求乘和布爾求和的運算直接求可達性矩陣 離散數(shù)學(xué) 57 例： 例： 利用鄰接矩陣的布爾運算求可達性矩陣。 ，??????????????????????????????0010111110121100A0001101111000010A 2。 見例題 1。 求 v1與 v2之間長度為 3的路數(shù) ， 結(jié)點 v1與 v3之間長度為 2的路數(shù) ， 在結(jié)點 v2之間長度為 4的回路數(shù) ？ ??????????????????????????????????1000001000001010002000101 01000100000001000101000102AA??????????????????????????????????1000001000002020004000202 010001000000020002020002043 AA離散數(shù)學(xué) 53 二、可達性矩陣 二、可達性矩陣 ????，否則至少存在一條路到，01 jiijvvp (i， j＝ 1， 2， 3， …… ， n) 則稱矩陣 P為圖 G的 可達性矩陣 。，????????????????????????????????????????????????????????????3303330300903303A0030003033030030A1101110100301101A0010001011010010A432如下： 上面圖中結(jié)點的度數(shù)和兩結(jié)點間長度為 k的路的條數(shù)。、 A179。 對所有的 k求和 ， 即是所有從 vi到 v的長度為 t+1的路的數(shù)目 ， 故命題對成立 。 證明 對 l施歸納法 當(dāng) l =2時 ， 由上得知是顯然成立 。＝ A A＝ (aij(2))n?n，則有： ????n1kkjik)2(ijij aaab此時， bij表示從 vi到 vj長度為 2的路數(shù)目，如 bij＝ 0，則無長度為 2的路，而 bii給出了經(jīng)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1