Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

🔗

Section 17.4 Graphing relations

🔗
Recall that if R is a relation on a set A, then formally R is a subset A×A. In other words, R is a collection of ordered pairs of elements from A.
🔗
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⊆A×A by the directed graph (A,R). The vertices of the graph are the elements of A, and for elements a1,a2∈A, we draw an arrow from a1 to a2 if a1Ra2 is true.
🔗

Example 17.4.1. Graph of the division relation on a finite set of natural numbers.

🔗
Recall that for natural numbers m and n, m∣n means “m divides n”. Consider this relation on the finite set A={2,3,4,5,6,7,8,9,10}. The graph of this relation appears in Figure 17.4.2.
Graph of the division relation on a small set of natural numbers.
Figure 17.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.
🔗

Example 17.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.
🔗

Question 17.4.4.

🔗
How are the properties of a relation reflected in its graph?
🔗

Reflexive relations.

🔗
In this case, aRa is true for every element a∈A, 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.
🔗

Remark 17.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 a1Ra2⇒a2Ra1 is always true. Therefore, in the graph for R, whenever we have an arrow from a1 to a2, we must also have an arrow from a2 to a1.
🔗

Example 17.4.6. Graph of a symmetric relation.

🔗
🔗
On the set A={a,b,c,d}, the relation
R={(a,b),(b,a),(b,c),(c,b)}
🔗
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.
The graph of a basic symmetric relation.
Figure 17.4.7. The graph of a basic symmetric relation.
🔗

Remark 17.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.
🔗

Example 17.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.
The simplified graph of a basic symmetric relation.
Figure 17.4.10. The simplified graph of a basic symmetric relation.
🔗

Antisymmetric relations.

🔗
In this case, we never have both a1Ra2 and a2Ra1 for a1≠a2, so in the graph for R, no pair of vertices can have two oppositely-directed arrows between them.
🔗

Example 17.4.11. Graph of an antisymmetric relation.

🔗
🔗
On the set A={a,b,c,d}, the relation
R={(a,a),(a,b),(c,b)}
🔗
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.
The graph of a basic antisymmetric relation.
Figure 17.4.12. The graph of a basic antisymmetric relation.
🔗

Transitive relations.

🔗
In this case, the conditional a1Ra2∧a2Ra3⇒a1Ra3 is always true. Therefore, in the graph for R, every “chain” of two arrows has a corresponding “composite” arrow.
🔗

Example 17.4.13. Graph of an transitive relation.

🔗
🔗
On the set A={a,b,c,d,e}, the relation
R={(a,b),(b,c),(a,c),(d,e),(e,d),(d,d),(e,e)}
🔗
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.
The graph of a basic transitive relation.
Figure 17.4.14. The graph of a basic antisymmetric relation.
🔗

Remark 17.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.
<Prev^TopNext>