圖的矩陣表ppt課件-在線瀏覽
2025-06-23 23:18本頁面
【正文】 1 11 1 0 11 0 0 0A?????????????v3的出度 =1+1+0+1=3， v3的入度 =0+1+0+0=1 鄰接矩陣的 圖論意義 設 A為 無向簡單圖 G的鄰接矩陣，其 第 i行 (列 )元素為 1的個數等于 結點的度。 ① A的 第 i行 (列 )和 等于第 i個結點的出 (入 )度 ， i=1,…n 。 特別地， bii是第 i結點的 出度 。 i j 練習：求 AAT， ATA，并由此求每個結點的 出度 與 入度 1 0 1 00 2 1 01 1 3 10 0 1 1TAA?????????????0 0 1 11 0 1 00 1 0 00 1 1 0TA?????????????0 1 0 00 0 1 11 1 0 11 0 0 0A?????????????2 1 0 11 2 0 10 0 1 11 1 1 2TAA?????????????練習：求 AAT， ATA，并由此求每個結點的 出度 與 入度 0 1 00 1 01 1 101230 11TAA?????????????0 0 1 11 0 1 00 1 0 00 1 1 0TA?????????????0 1 0 00 0 1 11 1 0 11 0 0 0A?????????????1 0 11 0 10 0 112211 21TAA?????????????③ 定理 1 設簡單有向圖 G=V,E的鄰接矩陣為 A，則矩陣 A(k)中的第 i行第 j列元素等于 G中從 vi到 vj長度為 k的不同路徑的數目。 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的路中間必經由一個結點 vk,即 v2 ?vk ? v1(1?k?4)。 ④ Br=A+A(2)+A(3)+… +A(r)的元素 bij表示 從 vi到 vj長度小于等于 r的 不同路徑總數 。 bij?0(i?j)表示 從 vi到 vj可達 ， 否則從 vi到 vj不可達 ， 分屬不同強分圖 。 例 2 根據有向圖和矩陣 B5，驗證 (a) b52=0，所以 v2和 v5分屬兩
教學課件相關推薦
鄂ICP備17016276號-1