Library > MA 208 home > 13.2: Graph representations ! " Help / FAQ # Alicia Clark $ 13.2 Graph representations Below are drawings of two graphs: Figure 13.2.1: Two drawings of an undirected graph. The two graphs look different, but that is only because they are drawn differently. The two graphs a actually the same graph because they have the same vertex and edge sets as shown below: V = {a, b, c, d, e} E = {{a, b}, {b, c}, {b, e}, {c, d}, {d, e}} The way a graph is drawn on a 2-dimensional surface (paper or screen) is not part of the graph itse PARTICIPATION ACTIVITY 13.2.1: Identifying identical graphs. Indicate whether the graphs shown are the same graph. 1) Same Different 2) Same Different A drawing is a convenient way to represent a small graph for a person to visualize. However, drawin be deceptive in that identical graphs can be made to look very different if they are drawn in differen If a graph is part of the input to a computer program, a more formal speciTcation of a graph is requ One way to represent a graph unambiguously is to list the edges. However, a list of the edges in the is not the most convenient way to for a program to access the information about the graph. A typic in an algorithm operating on a graph would be to determine whether two vertices are connected by edge or to list all the neighbors of a given vertex. Each of these steps would require scanning the en of edges. There are two common ways to represent graphs for use in algorithms that make the information about the graph more accessible. Adjacency list representation for graphs In the adjacency list representation of a graph, each vertex has a list of all its neighbors. Note that the graph is undirected if vertex a is in b's list of neighbors, then b must also be in a's list of neighbo animation below shows the adjacency list representation for a small example: PARTICIPATION ACTIVITY 13.2.2: Adjacency list representation. Start a b Adjacency List Representation a c b c e d d e b c a c e a b d c e b d Found c! Yes, b is adjacent to c. Worst case: time proportional to deg(b) Is b adjacent to c? Scan b's list and look for c View animation caption(s) If a graph is represented using adjacency lists, the time required to list the neighbors of a vertex v is proportional to deg(v), the number of vertices to be listed. In order to determine if {a, b} is an edge, necessary to scan the list of a's neighbors or the list of b's neighbors. In the worst case, the time re is proportional to the smaller of deg(a) or deg(b). Matrix representation for graphs The matrix representation for a graph with n vertices is an n by n matrix whose entries are all eithe indicating whether or not each edge is present. If the matrix is labeled M, then Mi,j denotes the entry i and column j. For a matrix representation, the vertices of the graph are labeled with integers in the from 1 to n. Entry Mi,j=1 if and only if {i, j} is an edge in the graph. Since the graph is undirected, Mi,j because {i, j} and {j, i} refer to the same edge which is either present in the graph or not. Thus the m representation of an undirected graph is symmetric about the diagonal, meaning that it is a mirror i of itself along the diagonal extending from the upper left corner to the lower right corner. The anima below illustrates. PARTICIPATION ACTIVITY 13.2.3: Matrix representation. Start Matrix Product Representation 1 2 1 3 5 4 2 3 4 5 1 0 1 1 0 0 2 1 0 1 0 1 3 1 1 0 1 0 4 0 0 1 0 1 5 0 1 0 1 0 What are the neighbors of vertex 5? 2 4 Time proportional to the number of vertices. View animation caption(s) If a graph is represented with a matrix, determining if {i, j} is an edge only requires examining matrix element Mi,j which can be done in O(1) time. In order to list the neighbors of a vertex j, it is necessa scan all of row j. Each 1 encountered corresponds to a neighbor of vertex j. The time to required to neighbors of vertex j requires (n) time. PARTICIPATION ACTIVITY 13.2.4: Graph representations. The diagram below shows two graphs. 1) Which of the two graphs above corresponds to the following matrix representation? (The rows and columns of the matrix are numbered 1 through 5). 0 1 1 0 1 1 0 1 0 1 1 1 0 1 0 0 0 1 0 1 1 1 0 1 0 G H 2) Which of the two graphs above corresponds to the following adjacency list representation? G H Additional exercises EXERCISE 13.2.1: From a graph drawing to other graph representations. A graph G is depicted in the diagram below. (a) Give the adjacency list representation of G. (b) Give the matrix representation of G. EXERCISE 13.2.2: Time complexity of graph operations with matrix and adjacency list representations. Each question below describes an operation on a graph. Give the worst-case time complexity of performing the operation for a d-regular graph with a matrix representation and with an adjacenc representation. The number of vertices in the graph is n. Give your answer Trst for the case d = 4 then for d = n . The variable d should not be in your Tnal expression. With the adjacency list representation, assume you can Tnd the list for a particular vertex in O(1) Also the neighbors of a vertex are stored in an arbitrary order, so searching for a particular neighb a list takes time proportional to the length of the list in the worst case. (a) Given a vertex i, list all the neighbors of vertex i. (b) Find any neighbor of vertex i. (c) Given a vertex i, list all the neighbors of the neighbors of vertex