A problem in which an
equivalence relation is deinfed over every pair of
elements in a
set S.
Let the relation be represented by the '~' character
a ~ b is either true or false and satisfies the properties of an
equivalence relation
ex:
S is a set of computers
~ = "is connected to"
Say we want to know if two computers a and b are connected. (a ~ b?). These types of
problems are most easily solved through the use of the
disjoint set.
Note: This requires that the connections be two way (symmetric), transitive (i.e. a is connected to b, which is connected to c, so a is connected to c.), and reflexive (a is connected to itself). These stipulations, which might seem obvious, are required to satisfy the requirements of an equivalence relation.