Recall that if \(R\) is a relation on a set \(A\text{,}\) then formally \(R\) is a subset \(A \cartprod A\text{.}\) In other words, \(R\) is a collection of ordered pairs of elements from \(A\text{.}\)
Also recall that in a directed graph, the edge collection is formally defined to be a collection of ordered pairs of vertices. So when the set \(A\) is finite, we may regard \(A\) as a set of vertices and \(R\) as a collection of (directed) edges in a graph!
To summarize, we may represent a relation \(R \subseteq A \cartprod A\) by the directed graph \((A,R)\text{.}\) The vertices of the graph are the elements of \(A\text{,}\) and for elements \(a_1,a_2 \in A\text{,}\) we draw an arrow from \(a_1\) to \(a_2\) if \(a_1 \mathrel{R} a_2\) is true.
Example17.4.1.Graph of the division relation on a finite set of natural numbers.
Recall that for natural numbers \(m\) and \(n\text{,}\)\(m \mid n\) means “\(m\) divides \(n\)”. Consider this relation on the finite set \(A = \{ 2,3,4,5,6,7,8,9,10 \}\text{.}\) The graph of this relation appears in Figure 17.4.2.
Figure17.4.2.Graph of the division relation on a small set of natural numbers.
Note that each vertex has a loop since every number divides itself.
Example17.4.3.Graph of an inverse relation.
Using the same division relation on the same set \(A\) as in Example 17.4.1 above, we may obtain the graph for the inverse relation by just reversing the direction of all the arrows in the graph in Figure 17.4.2.
Question17.4.4.
How are the properties of a relation reflected in its graph?
Reflexive relations.
In this case, \(a \mathrel{R} a\) is true for every element \(a \in A\text{,}\) so every vertex has a loop. For example, the relation in Example 17.4.1 is reflexive, and we see this mirrored in the graph in Figure 17.4.2 by the placement of a loop at every node.
Remark17.4.5.
When a relation is understood to be reflexive, we often omit the loops from its graph to reduce visual clutter.
Symmetric relations.
In this case, the conditional \(a_1 \mathrel{R} a_2 \lgcimplies a_2 \mathrel{R} a_1\) is always true. Therefore, in the graph for \(R\text{,}\) whenever we have an arrow from \(a_1\) to \(a_2\text{,}\) we must also have an arrow from \(a_2\) to \(a_1\text{.}\)
Example17.4.6.Graph of a symmetric relation.
On the set \(A = \{a,b,c,d\}\text{,}\) the relation
\begin{equation*}
R = \{(a,b),(b,a),(b,c),(c,b)\}
\end{equation*}
is symmetric, and we see this property reflected in the graph in Figure 17.4.7, as each pair of related (distinct) nodes has an arrow in each direction between them.
Figure17.4.7.The graph of a basic symmetric relation.
Remark17.4.8.
When \(R\) is symmetric, arrows are essentially meaningless since between every pair of vertices we will have either no arrows or one arrow in each direction. So we may as well draw the graph for \(R\) as an ordinary (undirected) graph instead of a directed graph, replacing each pair of arrows with a single edge.
Example17.4.9.Simplified graph of a symmetric relation.
The relation in the previous example is more concisely depicted graphically as in Figure 17.4.10 below.
Figure17.4.10.The simplified graph of a basic symmetric relation.
Antisymmetric relations.
In this case, we never have both \(a_1 \mathrel{R} a_2\) and \(a_2 \mathrel{R} a_1\) for \(a_1 \ne a_2\text{,}\) so in the graph for \(R\text{,}\)no pair of vertices can have two oppositely-directed arrows between them.
Example17.4.11.Graph of an antisymmetric relation.
On the set \(A = \{a,b,c,d\}\text{,}\) the relation
\begin{equation*}
R = \{(a,a),(a,b),(c,b)\}
\end{equation*}
is antisymmetric, and we see this property reflected in the graph in Figure 17.4.12, as each pair of distinct nodes has at most one arrow between them.
Figure17.4.12.The graph of a basic antisymmetric relation.
Transitive relations.
In this case, the conditional \({{a_1 \mathrel{R} a_2} \lgcand {a_2 \mathrel{R} a_3}} \lgcimplies {a_1 \mathrel{R} a_3}\) is always true. Therefore, in the graph for \(R\text{,}\) every “chain” of two arrows has a corresponding “composite” arrow.
Example17.4.13.Graph of an transitive relation.
On the set \(A = \{a,b,c,d,e\} \text{,}\) the relation
\begin{equation*}
R = \{(a,b),(b,c),(a,c),(d,e),(e,d),(d,d),(e,e)\}
\end{equation*}
is transitive, and we see this property reflected in the graph in Figure 17.4.14, as each pair of arrows forming a “chain” between three nodes has a corresponding “composite” arrow from the first node in the chain to the third.
Figure17.4.14.The graph of a basic antisymmetric relation.
Remark17.4.15.
In the graph of a transitive relation, we often omit the “composite” arrows to reduce visual clutter, as we can infer from “chains” of arrows where the “composite” arrows would go. For example, we did this in both the power set graph in Example 14.4.1 (see Figure 14.4.2) and in the division graph in Example 14.4.3 (see Figure 14.4.4). It should be obvious that the relations “is a subset of” and “divides” are transitive, so there was no need to clutter up the graphs of those relations with extra “composite” arrows — we could trace the fact that one set was a subset of another or the fact that one number divides another by following a chain of arrows through intermediate nodes, as necessary.
