lecture1introduction-資料下載頁
2025-07-17 15:19本頁面
【正文】 irected graph satisfies AT = A? Adjacencymatrix can be used to represent weighted graphs. ??? ??ot he r w is e 0,),( if 1 Ejiaij ??????o t h e r w is e ,),( if 1 Ejiaij? 2022SDU 33 Adjacencymatrix representation (Advantage vs. disadvantage) Advantage: ? Easily or quickly to determine if an edge is in the graph or not by just looking at the proper position of the matrix. Disadvantage: ? Uses more memory to store a graph. O(| V |2) ? 2022SDU 34 Properties of adjacencymatrix representation Lemma ? Suppose that A is the adjacencymatrix representation of an undirected graph G, then the element Ak[i, j] of Ak = A?A?… ?A is the number of paths of length k that connect vertices i and j. ? Proof by induction on k. – Basic step: k = 1, A1 = A, A[i, j] is the number of paths of length 1 that connect vertices i and j. – Inductive step: Suppose it is true for k 1 and the numbers smaller than k, that is, Ak[i, j] is the number of paths of length k that connect vertices i and j. From Ak+1=A ? Ak, we have Ak+1[i, j] = ?l?V A[i, l] ? Ak[l, j]. For A[i, l] is the number of paths of length 1 that connect vertices i and l, Ak[l, k] is the number of paths of length k that connect vertices l and j. So, A[i, l] ? Ak[l, j] is the number of paths of length k+1 that connect vertices i and j via l. Consider all vertices l, 1? l ? n, we get our conclusion. ? 2022SDU 35 Properties of adjacencymatrix representation 211[ , ] [ , ] [ , ] ( )nn GjjA i i A i j A j i d i??????? Corollary Proof: For symmetry of adjacencymatrix, A[i, l]=A[l, i] = 0 or 1, so 21 1 1[ , ] [ , ] [ , ] [ , ] [ , ] ( )n n nGl j jA i i A i l A l i A i j A j i d i? ? ?? ? ? ? ?? ? ?1 2 4 3 A2[1, 1]: 2: (1, 2, 1), (1, 3, 1) A2[2, 2]: 3: (2, 1, 2), (2, 3, 2), (2, 4, 2) ? 2022SDU 36 Euler Graph History: ? Leonhard Euler (1707 1783) In Konigsberg, German, a river ran through the city such that in its center was an island, and after passing the island, the river broke into two parts. Seven bridges were built so that the people of the city could get from one part to another. ? 2022SDU 37 Knigsberg Bridges Problem People wondered whether or not one could walk around the city in a way that would involve crossing each bridge exactly once. Now, have a try! How about if a bridge is removed? ? 2022SDU 38 Why?
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1