圖的矩陣表ppt課件-展示頁
2025-05-15 23:18本頁面
【正文】 。 鄰接矩陣的 圖論意義 設 A為 無向簡單圖 G的鄰接矩陣，其 第 i行 (列 )元素為 1的個數(shù)等于 結點的度。 ? 有 n個結點的多重圖 的鄰接矩陣是 n階方陣 A=(aij)，其中 aij代表從 vi到 vj的邊的重數(shù)。 ? 無向簡單圖 的鄰接矩陣是 對稱矩陣： A=AT。 ? 當有向線圖代表關系，關系矩陣就是鄰接矩陣。 ? 零圖 的鄰接矩陣的元素全為 0，稱為零矩陣。具有這樣性質的矩陣稱它們 置換等價 。南京信息工程大學 離散數(shù)學教學組 制作 離 散 數(shù) 學 電 子 課 件 第八章 圖論 圖的基本概念 路徑和回路 圖的矩陣表示 二部圖 平面圖 樹 有向樹 圖的矩陣表示 1. 鄰接矩陣 2. 可達性矩陣 3. 可達性矩陣的應用 4. 關聯(lián)矩陣 鄰接矩陣 定義 1 設 G=V,E有向（無向）線圖 ，有 n個 標定了次序 的結點 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個結點的 標定次序有關 ，對于 V中各元素不同的標定次序，可得出不同的鄰接矩陣。不過這些矩陣可以通過交換行和列而相互得出。 例如，左下圖的兩個 置換等價鄰接矩陣 ： 0 1 0 00 0 1 11 1 0 11 0 0 0A?????????????????????????????010000011101101041324132vvvvvvvv② 有向簡單圖在標定次序后得到唯一鄰接矩陣 。 ? 完全圖 Kn的鄰接矩陣是 恰有 n個 0并全在對角線上的 n階 (0,1)方陣 。 ? 有向線圖 G=?V,E?的鄰接矩陣是 A，則 G的 逆圖 G~=?V,E~?的鄰接矩陣是 A的轉置矩陣，記為 AT。 ? 有 n個結點的賦權圖 G=?V,E,W?的鄰接矩陣是 n階方陣 A=(aij)，其中當 (vi,vj)?E， aij=W(vi,vj)；否則 ,aij=0。 幾個特殊圖的鄰接矩陣 鄰接矩陣的 圖論意義 設 A為 無向簡單圖 G的鄰接矩陣，其 第 i行 (列 )元素為 1的個數(shù)等于 結點的度。 設 A為 有向簡單圖 G的鄰接矩陣。 0 1 0 00 0
教學課件相關推薦
鄂ICP備17016276號-1