dynamic equivalence problem

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.

There's a slight problem in this definition: to be non-trivial, it should be stated that only a proper subset of all equivalence relations are given and the goal is either:

• to determine whether two particular elements are in the same equivalence class; or
• to define completely all equivalence classes.

This is equivalent to the finding the connected components of an undirected graph. (The elements are vertices and equivalence is represented by edges.) The connected component problem is probably much better known; a brief web search revealed several class notes but only one published reference to the dynamic equivalence problem: Data Structures and Algorithm Analysis, by Mark Allen Weiss (Addison Wesley, 1997).