Lecture Data Structures: Lesson 34 provide students with knowledge about equivalence relations; electrical connectivity, where all connections are by metal wires, is an equivalence relation; the disjoint sets view; dynamic equivalence problem; discuss a solution to the union/find problem that for any sequence; . | Equivalence Relations A binary relation over a set S is called an equivalence relation if it has following properties 1. Reflexivity for all element x S x x 2. Symmetry for all elements x and y x y if and only if y x 3. Transitivity for all elements x y and z if x y and y z then x z The relation is related to is an equivalence relation over the set of people Lecture Data Structure Dr. Sohail Aslam Equivalence Relations The relationship is not an equivalence relation. It is reflexive since x x and transitive since x y and y z implies x z it is not symmetric since x y does not imply y x. Equivalence Relations Electrical connectivity where all connections are by metal wires is an equivalence relation. It is clearly reflexive since any component is connected to itself. It is symmetric because if component a is connected to component b then b must be electrically connected to a. It is transitive since if component a is connected to component b and b is connected to c then a is connected to c. The Disjoint Sets View An equivalence relation over a set S can be viewed as a partitioning of S into disjoint sets. Each set of the partition is called an equivalence class of all elements that are related . The Disjoint Sets View Every member of S appears in exactly one equivalence class. To decide if a b we need only to check whether a and b are in the same equivalence class. This provides a strategy to solve the equivalence problem. Dynamic Equivalence Problem If the relation is stored as a two-dimensional array of booleans then of course this can be done in constant time. The problem is that the relation is usually not explicitly defined but rather implicitly defined. Ahmed Haaris Qasim Omar Asim Saad Haaris T T T Saad T T Ahmed T Omar T Asim T T Qasim T Dynamic Equivalence Problem As an example suppose the equivalence relation is defined over the five-element set a1 a2 a3 a4 a5 . There are 25 pairs of elements each of which is related or not. 30 pairs 5 self- pairs 25
