10.3 Representing Graphs and Graph Isomorphism May 07, 2018 Shawn Math 240 No comments yet 10.2 Graph Terminology and Special Types of Graphs May 07, 2018 Shawn Math 240 2 comments 10.1 Graphs and Graph Models May 07, 2018 Shawn Math 240 No comments yet 9.6 Partial Orderings May 07, 2018 Shawn Math 240 No comments yet Math 541 – 5/2 May 05, 2018 Shawn Math 541 No comments yet 1 … 14 15 16 17 18 … 87
![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)
![Prime Ideal • Definition ○ Suppose R is commutative ○ An ideal P⊊R is prime if ○ a,b∈R,ab∈P⇒a∈P or b∈P • Example ○ Take R=Z ○ The prime ideals are ideals of the form (n), where n is prime or n=0 ○ Proof (⟹) § Let (n)⊆Z be a prime ideal, and n≠0 § We want to show that n is prime § Choose a,b∈Z s.t. n=ab § Then ab∈(n), so either a∈(n) or b∈(n) § Without loss of generality, suppose a∈(n) § Then ├ n┤ |a┤ § Choose q∈Z s.t. nq=a § n=ab⇒n=nqb⇒1=qb⇒b∈{±1} § So n is a prime ○ Proof (⟸) § (0) is prime □ Let a,b∈Z, and ab∈(0) □ Then ab=0 □ ⇒a=0 or b=0 □ ⇒a∈(0) or b∈(0) □ Therefore (0) is prime § (p) is prime for p∈Z prime □ Let a,b∈Z, and say ab∈(p) □ Then p|ab □ Since p is prime, this means p|a or p|b □ ⇒a∈(p) or b∈(p) Proposition 73: Criterion for Prime Ideal • Statement ○ Let R be a commutative ring, P⊆R an ideal, then ○ P is prime ⇔ R\/P is a domain ○ In particular, R is a domain ⇔ 0 ideal is prime • Proof (⟹) ○ Let a+P,b+P∈(R/P)∖\{P} ○ Then (a+P)(b+P)=ab+P=0 ○ So, ab∈P ○ Since P is prime, a∈P or b∈P ○ Therefore a+P=0 or b+P=0 • Proof (⟸) ○ Let a,b∈R, and suppose ab∈P, then ○ 0=ab+P=(a+P)(b+P) ○ Since R\/P is a domain, a+P=0 or b+P=0 ○ So a∈P or b∈P • Example ○ (x^2−1)⊆R[x] is not prime ○ R[x]\/(x^2−1)≅R×R, which is not a domain ○ Also, x^2−1∈(x^2−1), but x−1,x+1∉(x^2−1) Corollary 74 • Statement ○ If R is a commutative ring, and M⊆R is maximal, then M is prime • Proof ○ M is maximal ⇒R\/M is a field ⇒R\/M is a domain ⇒ M is prime Euclidean Domain • Definition ○ Let R be a domain ○ A norm on R is a function N:R→Z(≥0) s.t. N(0)=0 ○ R is called a Euclidean domain if R is equipped with a norm N s.t. ○ ∀a,b∈R with b≠0, ∃q,r∈R s.t. § a=qb+r § Either r=0 or N(r) N(b) • Example 1 ○ Z is a Euclidean domain, N(a)=|a| • Example 2 ○ If F is a field, then F is trivially a Euclidean domain ○ Take N:F→Z(≥0) to be any function s.t. N(0)=0 ○ Then, if a,b∈F, where b≠0, take q=a/b,r=0 • Example 3 ○ If F is a field, then F[x] is a Euclidean domain, with N(p)=degp ○ The division algorithm have is just polynomial division ○ Note § deg0=−∞∉Z(≥0), so this definition isn t quite right § To handle this problem, define a norm to take vales not in Z(≥0) § But any total ordered set in order-preserving bijection with Z(≥0) § (For instance, Z(≥0)∪{−∞}) Proposition 75 • Statement ○ Every ideal in a Euclidean domain R is principal ○ More precisely, if I⊆R is an ideal, then I=(d), where ○ d is an element of I with minimum norm • Proof ○ Let I⊆R be an ideal ○ If I=(0), then I is principal, so assume I≠(0) ○ {N(a)│a∈I∖{0} } has a minimal element, by well-ordering principal ○ Choose d∈I∖{0} s.t. N(d) is minimal ○ Certainly, (d)⊆I ○ Let a∈I, write a=qd+r, where q,r∈R and either r=0 or N(r) N(d) ○ Since r=a−qd∈I, N(r) can t be smaller than N(d) ○ So r=0⇒a=qd⇒a∈(d) • Example 1 ○ We haven t yet proven that F[x] is a Euclidean domain, when F is a field ○ Once we show this, we ll know F[x] has the property that ○ All of its ideals are principal • Definition ○ A domain in which every ideal is principal is called a principal ideal domain • Example 2 ○ Z[x] cannot be a Euclidean domain, since (2,x)⊆Z[x] is not principal Theorem 76 • Statement ○ Let F be a field ○ Then F[x] is a Euclidean domain ○ More specifically, if a,b∈F[x] where b≠0, then ○ ∃!q,r∈F[x] s.t. a=bq+r and degr degb • Proof (Existence) ○ We argue by induction on dega ○ If a=0, take q,r=0, so assume a≠0 ○ Set n≔dega, m≔degb ○ If n m, then take q=0,r=a ○ Assume n≥m ○ Write a=a_n x^n+…+a_1 x+a_0,b=b_m x^m+…+b_1 x+b_0 ○ Set a^′=a−a_n/b_m x^(n−m) b ○ Since a and a_n/b_m x^(n−m) b have the same leading coefficient, dega′ dega ○ By induction, ∃q^′,r∈F[x] with a^′=q^′ b+r with degr degb ○ Set q=q^′+a_n/b_m x^(n−m) b ○ Then a=a^′+a_n/b_m x^(n−m) b=q^′ b+r+a_n/b_m x^(n−m) b=(q^′+a_n/a_m x^(n−m) )b+r=qb+r • Proof (Uniqueness) ○ Suppose bq^′+r^′=a=bq+r where degr degb, and degr′ degb ○ Then deg(a−bq) degb and deg〖(a−bq′) degb 〗 ○ ⇒deg((a−bq)−(a−bq^′ ))=deg(bq^′−bq)=degb+deg(q^′−q) degb ○ ⇒deg(q^′−q) 0⇒q^′=q ○ It follows immediately that r^′=r](https://shawnzhong.com/wp-content/uploads/2018/05/img_5aee501817d08.png)
