Equivalence Relations and Partial Orders

This section is concerned with basic concepts in set theory and their relationship to abstract–transitive-closure algorithms. Its purposes are to put the ideas that we are studying into a larger context and to demonstrate the wide applicability of the algorithms that we are considering. Mathematically inclined readers who are familiar with set theory may wish to skip to because the material that we cover is elementary (although our brief review of terminology may be helpful); readers who are not familiar with set theory may wish to consult an elementary text on discrete mathematics because our treatment is rather succinct. The connections between digraphs and these fundamental mathematical concepts are too important for us to ignore. Given a set, a relation among its objects is defined to be a set of ordered pairs of the objects. Except possibly for details relating to parallel edges and self-loops, this definition is the same as our definition of a digraph: Relations and digraphs are different representations of the same abstraction. The mathematical concept is somewhat more powerful because the sets may be infinite, whereas our computer programs all work with finite sets, but we ignore this difference for the moment. Typically, we choose a symbol R and use the notation sRt as shorthand for the statement "the ordered pair (s,t) is in the relation R." For example, we use the symbol "<" to represent the "less than" relation among numbers. Using this terminology, we can characterize various properties of relations. For example, a relation R is said to be symmetric if sRt implies that tRs for all s and t; it is said to be reflexive if sRs for all s. Symmetric relations are the same as undirected graphs. Reflexive relations correspond to graphs in which all vertices have self-loops; relations that correspond to graphs where no vertices have self-loops are said to be irreflexive. A relation R is said to be transitive when sRt and tRu implies that sRu for all s, t, and u. The transitive closure of a relation is a well-defined concept; but instead of redefining it in set-theoretic terms, we appeal to the definition that we gave for digraphs in . Any relation is equivalent to a digraph, and the transitive closure of the relation is equivalent to the transitive closure of the digraph. The transitive closure of any relation is transitive. In the context of graph algorithms, we are particularly interested in two particular transitive relations that are defined by further constraints. These two types, which are widely applicable, are known as equivalence relations and partial orders. An equivalence relation Screenshot is a transitive relation that is also reflexive and symmetric. Note that a symmetric, transitive relation that includes each object in some ordered pair must be an equivalence relation: If s Screenshot t, then t Screenshot s (by symmetry) and s Screenshot s (by transitivity). Equivalence relations divide the objects in a set into subsets known as equivalence classes. Two objects s and t are in the same equivalence class if and only if s Screenshot t. The following examples are typical equivalence relations: Modular arithmetic Any positive integer k defines an equivalence relation on the set of integers, with s Screenshot t (mod k) if and only if the remainder that results when we divide s by k is equal to the remainder that results when we divide t by k. The relation is obviously symmetric; a short proof establishes that it is also transitive (see Exercise 19.67) and therefore is an equivalence relation. Connectivity in graphs The relation "is in the same connected component as" among vertices is an equivalence relation because it is symmetric and transitive. The equivalence classes correspond to the connected components in the graph. When we build a graph ADT that gives clients the ability to test whether two vertices are in the same connected component, we are implementing an equivalence-relation ADT that provides clients with the ability to test whether two objects are equivalent. In practice, this correspondence is significant because the graph is a succinct representation of the equivalence relation (see Exercise 19.71). In fact, as we saw in Chapters 1 and 18, to build such an ADT we need to maintain only a single vertex-indexed array. A partial order Screenshot is a transitive relation that is also irreflexive. As a direct consequence of transitivity and irreflexivity, it is trivial to prove that partial orders are also asymmetric: If s Screenshot t and t Screenshot s, then s Screenshot s (by transitivity), which contradicts irreflexivity, so we cannot have both s Screenshot t and t Screenshot s. Moreover, extending the same argument shows that a partial order cannot have a cycle, such as s Screenshot t, t Screenshot u, and u Screenshot s. The following examples are typical partial orders: Subset inclusion The relation "includes but is not equal to" (Screenshot) among subsets of a given set is a partial order—it is certainly irreflexive, and if s Screenshot t and t Screenshot u, then certainly s Screenshot u. Paths in DAGs The relation "can be reached by a nonempty directed path from" is a partial order on vertices in DAGs with no self-loops because it is transitive and irreflexive. Like equivalence relations and undirected graphs, this particular partial order is significant for many apps because a DAG provides a succinct implicit representation of the partial order. For example, Screenshot illustrates DAGs for subset containment partial orders whose number of edges is only a fraction of the cardinality of the partial order (see Exercise 19.73).

Screenshot Set-inclusion DAG

In the DAG at the top, we interpret vertex indices to represent subsets of a set of 3 elements, as shown in the table at the bottom. The transitive closure of this DAG represents the subset inclusion partial order: There is a directed path between two nodes if and only if the subset represented by the first is included in the subset represented by the second.

Java graphics 19fig17.gif


Indeed, we rarely define partial orders by enumerating all their ordered pairs, because there are too many such pairs. Instead, we generally specify an irreflexive relation (a DAG) and consider its transitive closure. This usage is a primary reason for considering abstract–transitive-closure ADT implementations for DAGs. Using DAGs, we consider examples of partial orders in . A total order T is a partial order where either sTt or tTs for all s Screenshot t. Familiar examples of total orders are the "less than" relation among integers or real numbers and lexicographic ordering among strings of characters. Our study of sorting and searching algorithms in Parts 3 and 4 was based on a total-order ADT implementation for sets. In a total order, there is one and only one way to arrange the elements in the set such that sTt whenever s is before t in the arrangement; in a partial order that is not total, there are many ways to do so. In , we examine algorithms for this task. In summary, the following correspondences between sets and graph models help us to understand the importance and wide applicability of fundamental graph algorithms:

  • Relations and digraphs
  • Symmetric relations and undirected graphs
  • Transitive relations and paths in graphs
  • Equivalence relations and paths in undirected graphs
  • Partial orders and paths in DAGs

This context places in perspective the types of graphs and algorithms that we are considering and provides one motivation for us to move on to consider basic properties of DAGs and algorithms for processing those DAGs.

Exercises

Show that "has the same remainder after dividing by k" is a transitive relation (and therefore is an equivalence relation) on the set of integers.

Show that "is in the same edge-connected component as" is an equivalence relation among vertices in any graph.

Show that "is in the same biconnected component as" is not an equivalence relation among vertices in all graphs.

Prove that the transitive closure of an equivalence relation is an equivalence relation and that the transitive closure of a partial order is a partial order.

Java graphics ltr.gif 19.71 The cardinality of a relation is its number of ordered pairs. Prove that the cardinality of an equivalence relation is equal to the sum of the squares of the cardinalities of that relation's equivalence classes.

Screenshot 19.72 Using an online dictionary, build a graph that represents the equivalence relation "has k letters in common with" among words. Determine the number of equivalence classes for k = 1 through 5.

The cardinality of a partial order is its number of ordered pairs. What is the cardinality of the subset containment partial order for an n-element set?

Java graphics ltr.gif 19.74 Show that "is a factor of" is a partial order among integers.



   
Comments