6.2: Graphs of Relations on a Set
( \newcommand{\kernel}{\mathrm{null}\,}\)
In this section we introduce directed graphs as a way to visualize relations on a set.
Digraphs
Let A={0,1,2,3}, and let
r={(0,0),(0,3),(1,2),(2,1),(3,2),(2,0)}
In representing this relation as a graph, elements of A are called the vertices of the graph. They are typically represented by labeled points or small circles. We connect vertex a to vertex b with an arrow, called an edge, going from vertex a to vertex b if and only if arb. This type of graph of a relation r is called a directed graph or digraph. Figure 6.2.1 is a digraph for r. Notice that since 0 is related to itself, we draw a “self-loop” at 0.

The actual location of the vertices in a digraph is immaterial. The actual location of vertices we choose is called an embedding of a graph. The main idea is to place the vertices in such a way that the graph is easy to read. After drawing a rough-draft graph of a relation, we may decide to relocate the vertices so that the final result will be neater. Figure 6.2.1 could also be presented as in Figure 6.2.2.

A vertex of a graph is also called a node, point, or a junction. An edge of a graph is also referred to as an arc, a line, or a branch. Do not be concerned if two graphs of a given relation look different as long as the connections between vertices are the same in the two graphs.
Example 6.2.1: Another Directed Graph
Consider the relation s whose digraph is Figure 6.2.3. What information does this give us? The graph tells us that s is a relation on A={1,2,3} and that s={(1,2),(2,1),(1,3),(3,1),(2,3),(3,3)}.

We will be building on the next example in the following section.
Example 6.2.2: Ordering Subsets of a Two Element Universe
Let B={1,2}, and let A=P(B)={∅,{1},{2},{1,2}}. Then ⊆ is a relation on A whose digraph is Figure 6.2.4.

We will see in the next section that since ⊆ has certain structural properties that describe “partial orderings.” We will be able to draw a much simpler type graph than this one, but for now the graph above serves our purposes.
Exercises
Exercise 6.2.1
Let A={1,2,3,4}, and let r be the relation ≤ on A. Draw a digraph for r.
- Answer
-
Figure 6.2.5: Digraph for ≤
Figure 6.2.6: Hasse diagram for ≤
Exercise 6.2.2
Let B={1,2,3,4,6,8,12,24}, and let s be the relation “divides” on B. Draw a digraph for s.
Exercise 6.2.3
Let A={1,2,3,4,5}. Define t on A by atb if and only if b−a is even. Draw a digraph for t.
- Answer
-
See Figure 6.2.7
Figure 6.2.7: Digraph of the relation t
Exercise 6.2.4
Let A be the set of strings of 0's and 1's of length 3 or less. This includes the empty string, λ, which is the only string of length zero.
- Define the relation of d on A by xdy if x is contained within y. For example, 01d101. Draw a digraph for this relation.
- Do the same for the relation p defined by xpy if x is a prefix of y. For example, 10p101, but 01p101 is false.
Exercise 6.2.5
Recall the relation in Exercise 6.1.5 of Section 6.1, ρ defined on the power set, P(S), of a set S. The definition was (A,B)∈ρ iff A∩B=∅. Draw the digraph for ρ where S={a,b}.
Exercise 6.2.6
Let C={1,2,3,4,6,8,12,24} and define t on C by atb if and only if a and b share a common divisor greater than 1. Draw a digraph for t.