Properties of Relation ■Suppose R is a relation on X.R is reflexive if for any a∈X,(a,a)∈R Suppose R is a relation on X.R is symmetric if(a,b)∈R→(b,a)∈R. ■Suppose R is a relation on X.R is antisymmetric if(a,b)∈R∧(b,a)∈R→a=b. Suppose R is a relation on X.R is strongly antisymmetric if (a,b)∈R→(b,a)年R Example:Construct a relation on set {1,2,3}that is Reflexive but not symmetric. Not reflexive but symmetric. Reflexive and antisymmetric,but not strongly antisymmetric. Can a reflexive relation be strongly antisymmetric?
Properties of Relation Suppose R is a relation on X. R is reflexive if for any a∈X, (a,a)∈R. Suppose R is a relation on X. R is symmetric if (a,b)∈R→(b,a)∈R. Suppose R is a relation on X. R is antisymmetric if (a,b)∈R∧(b,a)∈R →a=b. Suppose R is a relation on X. R is strongly antisymmetric if Example: Construct a relation on set {1,2,3} that is Reflexive but not symmetric. Not reflexive but symmetric. Reflexive and antisymmetric, but not strongly antisymmetric. Can a reflexive relation be strongly antisymmetric?
Transitive Relation and Transitive Closure A relation R on set X is transitive if (a,b)∈R∧(b,c∈R→(a,c∈R Example 1:The "greater than"relation on the set of real numbers is transitive. Example 2:The "greater than or equal to"relation on the set of real numbers is also transitive. Recall that when we do inequalities,we often write things like a>b>...>d. This is a chain of elements,any two of which (in the given order)belong to the "greater than”relation. If we can write down ALL POSSIBLE elements,we have found the transitive closure of the relation. Suppose R is a transitive relation on set X.The transitive closure of R, denoted by R*,is defined as R*=RU(a,b)there exist c1,...,ck s.t.(a,c1),(c1,C2),...,(ck-1,c),(ck,b)ER}
Transitive Relation and Transitive Closure A relation R on set X is transitive if Example 1: The “greater than” relation on the set of real numbers is transitive. Example 2: The “greater than or equal to” relation on the set of real numbers is also transitive. Recall that when we do inequalities, we often write things like a>b>…>d. This is a chain of elements, any two of which (in the given order) belong to the “greater than” relation. If we can write down ALL POSSIBLE elements, we have found the transitive closure of the relation. Suppose R is a transitive relation on set X. The transitive closure of R, denoted by R*,is defined as
Transitive Closure and Warshall Algorithm Examples of transitive closure: 1.The transitive closure of the "greater than"relation is itself. 2.The transitive closure of{(1,2),(2,3),(4,4)}is{(1,2),(2,3),(1,3),(4,4)}. Question:Given a transitive relation R,how can we compute its transitive closure R*? ■Naive algorithm: ■Start with R*=R. Check each element c to see whether there is (a,b)such that (a,c),(c,b)R".If so,add (a,b)to R*. Repeat the above step until nothing more can be added to R*. Analysis of Naive algorithm: It definitely works. .(a,c2)must be added to R*in the first iteration; .(a,c3)must have been added to R*by the second iteration; (a,C),(c1,c2),.,(Ck-1,ck),(ck,b)∈R .(a,b)must have been added to R*by the kth iteration
Transitive Closure and Warshall Algorithm Examples of transitive closure: 1. The transitive closure of the “greater than” relation is itself. 2. The transitive closure of {(1,2),(2,3),(4,4)} is {(1,2),(2,3),(1,3),(4,4)}. Question: Given a transitive relation R, how can we compute its transitive closure R*? Naïve algorithm: Start with R*=R. Check each element c to see whether there is (a,b) such that (a,c), (c,b)∈ R*. If so, add (a,b) to R*. Repeat the above step until nothing more can be added to R*. Analysis of Naïve algorithm: It definitely works
Transitive Closure and Warshall Algorithm From the above analysis,we also learn that the algorithm takes no more than k iterations,where k is the length of the longest chain minus 1. Assume the underlying set is of size N.Then the number of iterations is no more than N-2. Each iteration checks each a,each b,and each c,and so takes no more than N3 "steps. ·In total,the naive algorithm needs no more than N4-2N3“steps.” To be smart and beat the naive algorithm,we can use Warshall Algorithm. Stephen Warshall (1935-2006),American Computer Scientist. Bachelor's degree in math from Harvard,1956. Never attended graduate school due to lack of CS graduate program at that time. 是RUM号 Won a bottle of rum for proving this algorithm 风型 to be correct
Transitive Closure and Warshall Algorithm From the above analysis, we also learn that the algorithm takes no more than k iterations, where k is the length of the longest chain minus 1. Assume the underlying set is of size N. Then the number of iterations is no more than N-2. Each iteration checks each a, each b, and each c, and so takes no more than N3 “steps.” In total, the naïve algorithm needs no more than N4-2N3 “steps.” To be smart and beat the naïve algorithm, we can use Warshall Algorithm. • Stephen Warshall (1935-2006), American Computer Scientist. • Bachelor’s degree in math from Harvard, 1956. • Never attended graduate school due to lack of CS graduate program at that time. • Won a bottle of rum for proving this algorithm to be correct
Transitive Closure and Warshall Algorithm The secret of Warshall algorithm:You don't need N-2 iterations! .A single iteration is enough. Hence,Warshall algorithm needs no more than N3 "steps. ■But why?? Suppose (4,2),(2,1)(1,3),(3,5)ER.Let us see how (4,5)can be added to R". The Single iteration of Warshall Algorithm: 1.Check element 1 to see whether there is (a,b)such (2,3)is added,because of (2,1) that(a,1),(1,b)∈R. and(1,3) 2.Check element 2 to see whether there is (a,b)such → (4,3)is added,because of (4,2) that(a,2),(2,b)∈R. and(2,3) 3.Check element 3 to see whether there is (a,b)such (4,5)is added,because of (4,3) that(a,3),(3,b)∈R and(3,5) 4.Check element 4 to see whether there is (a,b)such that(a,4),(4,b)∈R 升r9 rous prao时bgidac& 5. Check element 5 to see whether there is (a,b)such that(a,5),(5,b)∈R. yoar homeor (BIIT NO RUM)
Transitive Closure and Warshall Algorithm The secret of Warshall algorithm: You don’t need N-2 iterations! A single iteration is enough. Hence, Warshall algorithm needs no more than N3 “steps.” But why??? Suppose (4,2),(2,1)(1,3),(3,5)∈R. Let us see how (4,5) can be added to R*. The Single iteration of Warshall Algorithm: 1. Check element 1 to see whether there is (a,b) such that (a,1), (1,b)∈ R*. 2. Check element 2 to see whether there is (a,b) such that (a,2), (2,b)∈ R*. 3. Check element 3 to see whether there is (a,b) such that (a,3), (3,b)∈ R*. 4. Check element 4 to see whether there is (a,b) such that (a,4), (4,b)∈ R*. 5. Check element 5 to see whether there is (a,b) such that (a,5), (5,b)∈ R*. (2,3) is added, because of (2,1) and (1,3) (4,3) is added, because of (4,2) and (2,3) (4,5) is added, because of (4,3) and (3,5) A rigorous proof (by induction) is your homework (but no rum)