離散數(shù)學(xué)課件第5章(1)-展示頁
2025-01-25 20:38本頁面
【正文】 aij = 1 if {vi, vj} is an edge of G, aij = 0 otherwise. 8 2022/2/13 〖 Example 1〗 What is the adjacency matrix AG for the following graph G based on the order of vertices a, b, c, d ? a b c d ?????????????0111100110011110GASolution: Note: Adjacency matrices of undirected graphs are always 是對稱的 Representing Graphs and Graph Isomorphism 9 2022/2/13 注意： 1） 圖的鄰接矩陣依賴于所選擇的頂點(diǎn)的順序。在這里將給出兩種類型的常用的表示圖的矩陣 : 一種類型是基于頂點(diǎn)的鄰接關(guān)系， 一種類型是基于頂點(diǎn)與邊的關(guān)聯(lián)關(guān)系 。1 離散數(shù)學(xué) Discrete Mathematics 汪榮貴 教授 合肥工業(yè)大學(xué)軟件學(xué)院專用課件 Chapter 5 graph theory 3 CHAPTER 5 Graphs Introduction to Graphs 圖的概述 Graph Terminology 圖的術(shù)語 Representing Graphs and Graph Isomorphism圖的表示和圖的同構(gòu) Connectivity 連通性 Euler and Hamilton Paths 歐拉通路和哈密頓通路 Planar Graphs and Graph Coloring 平面圖與著色 Trees 樹 4 2022/2/13 Representing Graphs and Graph Isomorphism Representing Graphs 圖的表示 Methods for representing graphs: ? Adjacency lists 鄰接表 lists that specify all the vertices that are adjacent to each vertex該表規(guī)定與圖的每個頂點(diǎn)鄰接的頂點(diǎn) ? Adjacency matrice 鄰接矩陣 ? Incidence matrices 關(guān)聯(lián)矩陣 5 2022/2/13 Adjacency lists鄰接表 例： 用鄰接表描述所給的簡單圖 6 2022/2/13 若圖里面有許多邊，則把圖表示成邊表或鄰接表，就不便于執(zhí)行圖的算法。 為了簡化計算，可用矩陣表示圖。 Adjacency Matrices 鄰接矩陣 7 2022/2/13 Representing Graphs and Graph Isomorphism 定義：假設(shè) G = (V, E)是簡單圖 ， 其中 |V|=n . 假 設(shè) 把 G 的 頂 點(diǎn) 任 意 地 排 列成 。因此帶 n個頂點(diǎn)的圖有 n!個不同的鄰接矩陣，因?yàn)?n個頂點(diǎn)有 n!個不同的順序?？梢杂锰厥獾姆椒▉肀硎竞陀嬎氵@樣的矩陣。若 是有向圖任意的頂點(diǎn)序列。 1 0 0 0 0 1 0 1 0 P ＝ a11 a12 a13 a21 a22 a23 a31 a32 a33 A ＝ a11 a12 a13 a31 a32 a33 a21 a22 a23 PA ＝ a11 a13 a12 a31 a33 a32 a21 a23 a22 (PA)P ＝ P就是一個置換矩陣 ?鄰接矩陣中圖的性質(zhì)： v1 v2 v3 v4 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 A ＝ 無向圖的鄰接矩陣是對稱的！ (1)A=(αij)n n中，第 i行或第 i列中非 0元素 的個數(shù)等于頂點(diǎn) vi的度。 (有向圖 ) (3) B=A2。 a11 a12 … a 1n a21 a22 … a 2n …… an1 an2 … a nn C= (cij)= a11 a21 … a n1 a12 a22 … a n2 …… a1n a2n … a nn cij表示以 vi,vj為 始 點(diǎn)的 終 點(diǎn)數(shù)目。 a11 a12 … a 1n a21 a22 … a 2n …… an1 an2 … a nn D= (cij)= a11 a21 … a n1 a12 a22 … a n2 …… a1n a2n … a nn dij表示以 vi,vj為 終 點(diǎn)的 始 點(diǎn)數(shù)目。 則相對于 V和 E的這個順序的關(guān)聯(lián)矩陣是 n m矩陣 nvvv , 21 ? meee , 21 ?mnijm ?? ][M????ot he rw i s e0 i t h i nc i de nt w is e dg ew he n 1 ijijvem23 2022/2/13 Representing Graphs and Graph Isomorphism 〖 Example 4〗 What is the incidence matrix M for the following graph G based on the order of vertices a, b, c, d and edges 1, 2, 3, 4, 5, 6? Solution: a b c d 1 2 4 5 3 6 ?????????????001110111000000101010011dcbaMNote: Incidenc
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1