Representing Relations Using Matrices • A relation between finite sets can be represented using a zero-one matrix. • Suppose R is a relation from A={a_1,a_2,…,a_m } to B={b_1,b_2,…,b_n } ○ The elements of the two sets can be listed in any arbitrary order ○ When A=B, we use the same ordering. • The relation R is represented by the matrix ○ M_R = [m_ij], where ○ m_ij={■8(1&if (a_i,b_j )∈R@0&if (a_i,b_j )∉R)┤ • The matrix representing R has ○ a 1 as its (i,j) entry when a_i is related to b_j ○ a 0 if a_i is not related to b_j. Examples of Representing Relations Using Matrices • Example 1 ○ Suppose that A = {1,2,3} and B = {1,2} ○ Let R be the relation from A to B containing (a,b) if a b. ○ What is the matrix representing R (with increasing numerical order) • Solution ○ Because R={(2,1), (3,1),(3,2)}, the matrix is ○ M_R=[■8(0&0@1&0@1&1)] • Example 2 ○ Let A={a_1,a_2, a_3} and B={b_1,b_2, b_3,b_4, b_5}. ○ Which ordered pairs are in the relation R represented by the matrix ○ M_R=[■8(0&1&0&0&0@1&0&1&1&0@1&0&1&0&1)] • Solution ○ Because R consists of those ordered pairs (a_i,b_j) with m_ij = 1 ○ R={(a_1, b_2), (a_2, b_1),(a_2, b_3), (a_2, b_4),(a_3, b_1), {(a_3, b_3 ), (a_3, b_5 )} Matrices of Relations on Sets • If R is a reflexive relation, all the elements on the main diagonal of M_R are equal to 1 • R is a symmetric relation, if and only if m_ij = 1 whenever m_ji = 1 • R is an antisymmetric relation, if and only if m_ij = 0 or m_ji = 0 when i≠j Example of a Relation on a Set • Example 3: Suppose that the relation R on a set is represented by the matrix ○ M_R=[■8(1&1&0@1&1&1@0&1&1)] • Is R reflexive, symmetric, and/or antisymmetric? • Because all the diagonal elements are equal to 1, R is reflexive • Because M_R is symmetric, R is symmetric • R not antisymmetric because both m_1,2 and m_2,1 are 1 Representing Relations Using Digraphs Definition ○ A directed graph, or digraph, consists of a set V of vertices (or nodes) together with a set E of ordered pairs of elements of V called edges (or arcs). ○ The vertex a is called the initial vertex of the edge (a,b) ○ The vertex b is called the terminal vertex of this edge. ○ An edge of the form (a,a) is called a loop. Example 1 ○ A drawing of the directed graph with vertices a, b, c, and d ○ and edges (a, b), (a, d), (b, b), (b, d), (c, a), (c, b), and (d, b) is shown here. Example 2 ○ What are the ordered pairs in the relation represented by this directed graph? § ○ The ordered pairs in the relation are ○ (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (3, 1), (3, 3), (4, 1), (4, 3) Determining which Properties a Relation has from its Digraph • Reflexivity: A loop must be present at all vertices in the graph. • Symmetry: If (x,y) is an edge, then so is (y,x). • Antisymmetry: If (x,y) with x≠y is an edge, then (y,x) is not an edge. • Transitivity: If (x,y) and (y,z) are edges, then so is (x,z) Determining which Properties a Relation has from its Digraph • Example 1 ○ Reflexive? No, not every vertex has a loop ○ Symmetric? Yes (trivially), there is no edge from one vertex to another ○ Antisymmetric? Yes (trivially), there is no edge from one vertex to another ○ Transitive? Yes, (trivially) since there is no edge from one vertex to another • Example 2 ○ Reflexive? No, there are no loops ○ Symmetric? No, there is an edge from a to b, but not from b to a ○ Antisymmetric? No, there is an edge from d to b and b to d ○ Transitive? No, there are edges from a to c and from c to b, but there is no edge from a to d • Example 3 ○ Reflexive? No, there are no loops ○ Symmetric? No, for example, there is no edge from c to a ○ Antisymmetric? Yes, whenever there is an edge from one vertex to another, there is not one going back ○ Transitive? No, there is no edge from a to b • Example 4 ○ Reflexive? No, there are no loops ○ Symmetric? No, for example, there is no edge from d to a ○ Antisymmetric? Yes, whenever there is an edge from one vertex to another, there is not one going back ○ Transitive? Yes (trivially), there are no two edges where the first edge ends at the vertex where the second edge begins Closures • Definition ○ The closure of a relation R on A with respect to property P ○ is the least relation on A that contains R and has property P • Note ○ Least relation R^′ on A s.t. ○ R⊆R′ ○ R′ has property P ○ If S is a relation that safisfies the condition above, then R^′⊆S • Example ○ The reflexive closure of R is just R∪{(a,a)│a,∈A} ○ The symmetric closure of R is R∪R^(−1) ○ The transitive closure of R is R∪R2∪R3∪… Path in Directed Graphs • Definition ○ A path from a to b is a directed graph G is a sequence of edges ○ (a=x_0,x_1 ),(x_1,x_2 ),…,(x_(n−1),x_n=b) where n 0 ○ We denote the path by x_0,x_1,…,x_n say that the path has length n • Theorem ○ Let R be a relation on a set A ○ There is a path of length n from a to b if and only if (a,b) is an element of R^n The Connectivity Relation • Definition ○ Let R be a relation on A ○ The connectivity relation R^∗ cibsusts if all elements (a,b) s.t. ○ There is a path from a to b in R ○ In other words, R^∗ is the union of R,R2,R3,… ○ R∗=⋃24_(i=1)∞▒R^((i) ) • Example 1 ○ Let R be the relation between US state such that (a,b) is in R if a and b share a border. What is R^∗? ○ All pairs of states except Alaska and Hawaii • Example 2 ○ Let R be the relation between integers s.t. (a,b) is in R if b=a+1 ○ What is R^2, R^n, R^∗ ○ R^2={(a,b)│b=a+2} ○ R^n={(a,b)│b=a+n} ○ R^∗={(a,b)│a b} • Transitive closure ○ The connectivity relation R^∗ is exactly the transitive closure of R ○ We need to show that R is a subset of R^∗, R^∗ is transitive and least with that property. ○ The first two are easy ○ Let S be a transitive relation containing R ○ By induction we show that S contains R^n for every n Computing The Connectivity Relation • Theorem ○ Let R be a relation on A and let n be the number of elements in A. ○ The connectivity relation R^∗ is the union of R,R2,…,Rn • Proof ○ Let (a,b) be the element of R^∗ ○ Let a_0=x_0,x_1,…,x_m=b be the shortest path witnessing this. ○ If m n, then two of the vertices among x_1,…,x_m must be the same, say x_i=x_j ○ But then we can find a shorter path x_0,x_1,…,x_i=x_j,x_(j+1),x_n • Corollary ○ M_(R^∗ )=M_R∨M_R^[2] ∨…∨M_R^[n] • Example ○ Compute M_(R^∗ ) for the relation R={(a,b),(b,c),(c,d),(d,b)} ○ M_R=[■8(0&1&0&0@0&0&1&0@0&0&0&1@0&1&0&0)] ○ M_R^[2] =[■8(0&1&0&0@0&0&1&0@0&0&0&1@0&1&0&0)]⨀[■8(0&1&0&0@0&0&1&0@0&0&0&1@0&1&0&0)]=[■8(0&0&1&0@0&0&0&1@0&1&0&0@0&0&1&0)] ○ Similarly, compute M_R^[3] ,M_R^[4] ○ Then M_(R^∗ )=M_R∨M_R^[2] ∨M_R^[3] ∨M_R^[4]
