2.2. Relations¶
2.2.1. Relations¶
Hopefully you found the material on sets in the last module fairly simple, and maybe familiar from previous courses. If you have had a discrete math class, than you are probably also familiar with the concept of relations. But unlike basic set notation, most people have a lot of trouble understanding the concept of a relation (many overthink the idea), and even more trouble with the different classifications. So we will cover the basics in some detail, and follow up with some practice exercises.
2.2.2. Equivalence Classes and Partial Orders¶
1 / 10
Settings
<<<>
An equivalence relation is an especially important type of relation. Relation $R$ on set $S$ is an equivalence relation if it is reflexive, symmetric, and transitive. An equivalence relation can be viewed as partitioning a set into equivalence classes. If two elements $a$ and $b$ are equivalent to each other, we write $a \equiv b$. A partition of a set $S$ is a collection of subsets that are disjoint from each other (that is, they share no elements) and whose union is $S$. An equivalence relation on $S$ partitions the set into disjoint subsets whose elements are equivalent. The UNION/FIND algorithm efficiently maintains equivalence classes on a set. Two graph algorithms that make use of disjoint sets are connected component finding and computing a minimal-cost spanning tree.
