圖的矩陣表ppt課件-免費閱讀
【正文】 方法：圖 G的強分圖可從矩陣 P∧ PT求得 可求得 G的 強連通分支 對應(yīng)結(jié)點集為： {1}， {2}， {3,4,5}。 (c) b53=3， 所以從 v5到 v3長度 不超過 5的路徑有 3條 。 0 1 0 00 0 1 11 1 0 11 0 0 0A?????????????( 2 )0 0 1 12 1 0 11 1 1 10 1 0 0A?????????????分析 : a21(2)= a21a11+a22a21+ a23a31+a24a41=0?0+0?0+1?1+1?1=2 注意從 v2到 v1長度為 2的路中間必經(jīng)由一個結(jié)點 vk,即 v2 ?vk ? v1(1?k?4)。 0 1 0 00 0 1 11 1 0 11 0 0 0A?????????????v3的出度 =1+1+0+1=3， v3的入度 =0+1+0+0=1 鄰接矩陣的 圖論意義 設(shè) A為 無向簡單圖 G的鄰接矩陣，其 第 i行 (列 )元素為 1的個數(shù)等于 結(jié)點的度。 ? 有向線圖 G=?V,E?的鄰接矩陣是 A，則 G的 逆圖 G~=?V,E~?的鄰接矩陣是 A的轉(zhuǎn)置矩陣，記為 AT。南京信息工程大學(xué) 離散數(shù)學(xué)教學(xué)組 制作 離 散 數(shù) 學(xué) 電 子 課 件 第八章 圖論 圖的基本概念 路徑和回路 圖的矩陣表示 二部圖 平面圖 樹 有向樹 圖的矩陣表示 1. 鄰接矩陣 2. 可達性矩陣 3. 可達性矩陣的應(yīng)用 4. 關(guān)聯(lián)矩陣 鄰接矩陣 定義 1 設(shè) G=V,E有向（無向）線圖 ，有 n個 標(biāo)定了次序 的結(jié)點 v1, v2,…v n?V，則 n階方陣 A=(aij)稱為 G的鄰接矩陣，這里 例 1 左下圖的 鄰接矩陣 ： 1 ( )0()()()i j i jiji j i jv v v vavEEEv v vE?????? ?? ??????,0 1 0 00 0 1 11 1 0 11 0 0 0A?????????????注 ① 圖的鄰接矩陣與 n個結(jié)點的 標(biāo)定次序有關(guān) ，對于 V中各元素不同的標(biāo)定次序，可得出不同的鄰接矩陣。 ? 無向簡單圖 的鄰接矩陣是 對稱矩陣： A=AT。 設(shè) A為 有向簡單圖 G的鄰接矩陣。 一般地 , A(m)中從 i到 j長為 m的路徑總數(shù)是 aij(m)條，過 i的長為 m的回路共有 aii(m)條 。 v1 ( 2 )( 3 ) ( 4 )0 0 1 0 0 0 0 0
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1