May 7, 2018 - Shawn Zhong

10.3 Representing Graphs and Graph Isomorphism

$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.$

10.2 Graph Terminology and Special Types of Graphs

$Basic Terminology • Definition 1 ○ Two vertices u, v in an undirected graph G are called adjacent (or neighbors) in G if there is an edge e between u and v. ○ Such an edge e is called incident with the vertices u and v and e is said to connect u and v • Definition 2 ○ The set of all a vertices v of G = (V, E), denoted by N(v), is called the neighborhood of v. ○ If A is a subset of V, we denote by N(A) the set of all vertices in G that are adjacent to at least one vertex in A. So, ○ N(A)=⋃8_(v∈A)▒N(V) • Definition 3 ○ The degree of a vertex in a undirected graph is the number of edges incident with it, except that a loop at a vertex contributes two to the degree of that vertex. ○ The degree of the vertex v is denoted by deg(v). Degrees and Neighborhoods of Vertices What are the degrees and neighborhoods of the vertices in the graphs G and H? • For graph G ○ deg(a)=2,deg(b)=deg(c)=deg(f)=4,deg(d)=1,deg(e)=3,deg(g)=0. ○ N(a)={b,f},N(b)={a,c,e,f},N(c)={b,d,e,f},N(d)={c}, ○ N(e)={b,c,f},N(f)={a,b,c,e},N(g)=∅. • For graph H ○ deg(a)=4,deg(b)=deg(e)=6,deg(c)=1,deg(d)=5. ○ N(a)={b,d,e},N(b)={a,b,c,d,e},N(c)={b},N(d)={a,b,e},N(e)={a,b,d}. Degrees of Vertices • Theorem 1 (Handshaking Theorem) ○ If G=(V,E) is an undirected graph with m edges, then ○ 2m=∑_(v∈V)▒deg⁡v • Proof ○ Each edge contributes twice to the degree count of all vertices. ○ Hence, both the left-hand and right-hand sides of this equation equal twice the number of edges. ○ Think about the graph where vertices represent the people at a party and an edge connects two people who have shaken hands. • Example ○ How many edges are there in a graph with 10 vertices of degree six? • Solution ○ Because the sum of the degrees of the vertices is 6⋅10=60, the handshaking theorem tells us that 2m = 60. ○ So the number of edges m = 30. • Example ○ If a graph has 5 vertices, can each vertex have degree 3? • Solution ○ This is not possible by the handshaking theorem ○ Because the sum of the degrees of the vertices 3⋅5=15 is odd. • Theorem 2 ○ An undirected graph has an even number of vertices of odd degree. • Proof ○ Let V_1 be the vertices of even degree and V_2 be the vertices of odd degree in an undirected graph G=(V, E) with m edges.Then § 2m=∑_(v∈V)▒deg⁡v =∑_(v∈V_1)▒deg⁡v +∑_(v∈V_2)▒deg⁡v , where § ∑_(v∈V_1)▒deg⁡v must be even since deg⁡v is even for each v∈V_1 § ∑_(v∈V_2)▒deg⁡v must be even because 2m is even § and the sum of the degrees of the vertices of even degrees is also even. ○ Because this is the sum of the degrees of all vertices of odd degree in the graph, there must be an even number of such vertices Directed Graphs • Definition ○ An directed graph G = (V, E) consists of § V, a nonempty set of vertices (or nodes), and § E, a set of directed edges or arcs. ○ Each edge is an ordered pair of vertices. ○ The directed edge (u,v) is said to start at u and end at v. • Definition ○ Let (u,v) be an edge in G, then § u is the initial vertex of this edge and is adjacent to v and § v is the terminal (or end) vertex of this edge and is adjacent from u. ○ The initial and terminal vertices of a loop are the same. • Definition: ○ The in-degree of a vertex v, denoted deg^−⁡(v), is the number of edges which terminate at v. ○ The out-degree of v, denoted deg^+⁡(v), is the number of edges with v as their initial vertex. ○ Note that a loop at a vertex contributes 1 to both the in-degree and the out-degree of the vertex. • Example ○ In the graph G we have § deg^−⁡(a) = 2, deg^−⁡(b) = 2, deg^−⁡(c) = 3, deg^−⁡(d) = 2, deg^−⁡(e) = 3, deg^−⁡(f) = 0. § deg^+⁡(a) = 4, deg^+⁡(b) = 1, deg^+⁡(c) = 2, deg^+⁡(d) = 2, deg^+⁡(e) = 3, deg^+⁡(f) = 0. • Theorem 3 ○ Let G=(V, E) be a graph with directed edges. Then: § |E|=∑_(v∈V)▒〖deg^−⁡(v)+deg^+⁡(v) 〗 • Proof ○ The first sum counts the number of outgoing edges over all vertices and the second sum counts the number of incoming edges over all vertices ○ It follows that both sums equal the number of edges in the graph. Special Types of Simple Graphs: Complete Graphs • A complete graph on n vertices, denoted by K_n, is the simple graph that contains exactly one edge between each pair of distinct vertices. Special Types of Simple Graphs: Cycles and Wheels • A cycle C_n for n ≥ 3 consists of ○ n vertices v_1,v_2,…,v_n, and ○ edges {v_1,v_2 },{v_2,v_3 },…,{v_(n−1),v_n },{v_n,v_1 } • A wheel W_n is obtained by ○ adding an additional vertex to a cycle C_n for n ≥ 3, and ○ connecting this new vertex to each of the n vertices in C_n by new edges. Special Types of Simple Graphs: n-Cubes • An n-dimensional hypercube, or n-cube, Q_n, is ○ a graph with 2n vertices representing all bit strings of length n, where ○ there is an edge between two vertices that differ in exactly one bit position. Bipartite Graphs • Definition ○ A simple graph G is bipartite if V can be partitioned into two disjoint subsets V_1 and V_2 such that every edge connects a vertex in V_1 and a vertex in V_2 ○ In other words, there are no edges which connect two vertices in V_1 or in V_2. • It is not hard to show that an equivalent definition of a bipartite graph is a graph where it is possible to color the vertices red or blue so that no two adjacent vertices are the same color. Bipartite Graphs and Matchings • Bipartite graphs are used to model applications that involve matching the elements of one set to elements in another, for example: • Job assignments - vertices represent the jobs and the employees, edges link employees with those jobs they have been trained to do. • A common goal is to match jobs to employees so that the most jobs are done. Bipartite Graphs (continued) • Example ○ Show that C_6 is bipartite. • Solution ○ We can partition the vertex set into V_1={v_1, v_3, v_5} and V_2={v_2, v_4, v_6} so that every edge of C_6 connects a vertex in V_1 and V_2. • Example ○ Show that C_2 is not bipartite. • Solution ○ If we divide the vertex set of C_3 into two nonempty sets, one of the two must contain two vertices ○ But in C_3 every vertex is connected to every other vertex ○ Therefore, the two vertices in the same partition are connected. ○ Hence, C_3 is not bipartite. Complete Bipartite Graphs • Definition ○ A complete bipartite graph K_(m,n) is a graph that has its vertex set partitioned into two subsets V_1 of size m and V_2 of size n such that there is an edge from every vertex in V_1 to every vertex in V_2. • Example ○ We display four complete bipartite graphs here. New Graphs from Old • Definition ○ A subgraph of a graph G = (V,E) is a graph (W,F), where W⊂V and F⊂E. ○ A subgraph H of G is a proper subgraph of G if H≠G. • Example ○ Here we show K_5 and one of its subgraphs. • Definition ○ Let G=(V, E) be a simple graph. ○ The subgraph induced by a subset W of the vertex set V is the graph (W,F), where the edge set F contains an edge in E if and only if both endpoints are in W. • Example ○ Here we show K_5 and the subgraph induced by W={a,b,c,e}. • Definition ○ The union of two simple graphs G_1=(V_1, E_1) and G_2=(V_2, E_2) is the simple graph with vertex set V_1∪V_2 and edge set E_1∩E_2 ○ The union of G_1 and G_2 is denoted by G_1∪G_2. • Example$