![Representing Graphs: Adjacency Lists • Definition ○ An adjacency list can be used to represent a graph with no multiple edges by specifying the vertices that are adjacent to each vertex of the graph. • Example 1 • Example 2 Representation of Graphs: Adjacency Matrices • Definition ○ Suppose that G=(V,E) is a simple graph where |V|=n. ○ Arbitrarily list the vertices of G as v_1,v_2,…,v_n. ○ The adjacency matrix A_G of G, with respect to the listing of vertices, is the n×n zero-one matrix with 1 as its (i, j)th entry when v_i and v_j are adjacent, and 0 as its (i, j)th entry when they are not adjacent. ○ In other words, if the graphs adjacency matrix is A_G=[a_ij ], then ○ a_ij={■8(1&if {v_i,v_j } is an edge of G@0&otherwise)┤ • Example 1 ○ The ordering of vertices is a, b, c, d. • Example 2 ○ The ordering of vertices is a, b, c, d. • Note ○ The adjacency matrix of a simple graph is symmetric, i.e., a_ij=a_ji ○ Also, since there are no loops, each diagonal entry a_ii for i = 1, 2, 3, …, n, is 0. • Note ○ When a graph is sparse, that is, it has few edges relatively to the total number of possible edges, it is much more efficient to represent the graph using an adjacency list than an adjacency matrix. ○ But for a dense graph, which includes a high percentage of possible edges, an adjacency matrix is preferable. Adjacency Matrices: Graphs with Loops and Multiple Edges • Adjacency matrices can also be used to represent graphs with loops and multiple edges. • A loop at the vertex v_i is represented by a 1 at the (i, j)th position of the matrix. • When multiple edges connect the same pair of vertices v_i and v_j, (or if multiple loops are present at the same vertex), the (i, j)th entry equals the number of edges connecting the pair of vertices. • Example ○ We give the adjacency matrix of the pseudograph shown here using the ordering of vertices a, b, c, d. Adjacency Matrices: Directed graphs • Adjacency matrices can also be used to represent directed graphs. • The matrix for a directed graph G=(V, E) has a 1 in its (i, j)th position if there is an edge from v_i to v_j, where v_1,v_2,…,v_n is a list of the vertices. • In other words, if the graphs adjacency matrix is A_G=[a_ij ], then ○ a_ij={■8(1&if (v_i,v_j ) is an edge of G@0&otherwise)┤ • The adjacency matrix for a directed graph does not have to be symmetric, because there may not be an edge from v_i to v_j, when there is an edge from v_j to v_i. • To represent directed multigraphs, the value of a_ij is the number of edges connecting v_i to v_j. Representation of Graphs: Incidence Matrices • Definition ○ Let G=(V, E) be an undirected graph with vertices v_1,v_2,…,v_n and edges e_1,e_2,…,e_m. ○ The incidence matrix with respect to the ordering of V and E is the n×m matrix ○ M=[m_ij ],where m_ij={■8(1&when edge e_j is incident with v_i@0&otherwise)┤ • Example ○ Simple Graph and Incidence Matrix ○ ○ The rows going from top to bottom represent v_1 through v_5 ○ The columns going from left to right represent e_1 through e_6. • Example ○ The rows going from top to bottom represent v_1 through v_5 ○ The columns going from left to right represent e_1 through e_8. Isomorphism of Graphs • Definition ○ The simple graphs G_1 = (V_1, E_1) and G_2 = (V_2, E_2) are isomorphic if § there is a one-to-one and onto function f from V_1 to V_2 with the property that § a and b are adjacent in G_1 if and only if f(a) and f(b) are adjacent in G_2, for all a and b in V_1. ○ Such a function f is called an isomorphism. ○ Two simple graphs that are not isomorphic are called nonisomorphic. • Example ○ Show that the graphs G=(V, E) and H=(W, F) are isomorphic. • Solution ○ The function f with f(u_1) = v_1, f(u_2)=v_4, f(u_3) = v_3, and f(u_4) = v_2 is a one-to-one correspondence between V and W. ○ Note that adjacent vertices in G are u_1 and u_2, u_1 and u_3, u_2 and u_4, and u_3 and u_4. ○ Each of the pairs f(u_1) = v_1 and f(u_2) = v_4, f(u_1)=v_1 and f(u_3)=v_3 , f(u_2)=v_4 f(u_4)=v_2, f(u_3) = v_3 and f(u_4) = v_2 consists of two adjacent vertices in H • Note ○ It is difficult to determine whether two simple graphs are isomorphic using brute force because there are n! possible one-to-one correspondences between the vertex sets of two simple graphs with n vertices. ○ The best algorithms for determining whether two graphs are isomorphic have exponential worst case complexity in terms of the number of vertices of the graphs. ○ Sometimes it is not hard to show that two graphs are not isomorphic. ○ We can do so by finding a property, preserved by isomorphism, that only one of the two graphs has. ○ Such a property is called graph invariant. ○ There are many different useful graph invariants that can be used to distinguish nonisomorphic graphs, such as the number of vertices, number of edges, and degree sequence (list of the degrees of the vertices in nonincreasing order). ○ We will encounter others in later sections of this chapter. • Example ○ Determine whether these two graphs are isomorphic • Solution ○ Both graphs have eight vertices and ten edges. ○ They also both have four vertices of degree two and four of degree three. ○ However, G and H are not isomorphic. ○ Note that since deg(a) = 2 in G, a must correspond to t, u, x, or y in H, ○ because these are the vertices of degree 2. ○ But each of these vertices is adjacent to another vertex of degree two in H ○ which is not true for a in G. ○ Alternatively, note that the subgraphs of G and H made up of vertices of ○ degree three and the edges connecting them must be isomorphic. ○ But the subgraphs, as shown at the right, are not isomorphic. • Example ○ Determine whether these two graphs are isomorphic. • Solution ○ Both graphs have six vertices and seven edges. ○ They also both have four vertices of degree two and two of degree three. ○ The subgraphs of G and H consisting of all the vertices of degree two and the edges connecting them are isomorphic ○ So, it is reasonable to try to find an isomorphism f. ○ We define an injection f from the vertices of G to the vertices of H that preserves the degree of vertices. ○ We will determine whether it is an isomorphism. ○ The function f with f(u_1)=v_6,f(u_2)=v_3,f(u_3)=v_4,f(u_4)=v_5,f(u_5)=v_1,f(u_6)=v_2 is a one-to-one correspondence between G and H ○ Showing that this correspondence preserves edges is straightforward, so we will omit the details here. ○ Because f is an isomorphism, it follows that G and H are isomorphic graphs. ○ See the text for an illustration of how adjacency matrices can be used for this verification.](https://shawnzhong.com/wp-content/uploads/2018/05/img_5af10cca4823c.png)
10.3 Representing Graphs and Graph Isomorphism
Related Posts
WeChat Account
TOP
Shawn Zhong
钟万祥