$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 6.2: Graphs of Relations on a Set

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

In this section we introduce directed graphs as a way to visualize relations on a set.

## Digraphs

Let $$A = \{0, 1,2,3\}\text{,}$$ and let

\begin{equation*} r = \{(0, 0), (0, 3), (1, 2), (2, 1), (3, 2), (2, 0)\} \end{equation*}

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 $$a r b\text{.}$$ This type of graph of a relation $$r$$ is called a directed graph or digraph. Figure $$\PageIndex{1}$$ is a digraph for $$r\text{.}$$ 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 $$\PageIndex{1}$$ could also be presented as in Figure $$\PageIndex{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 $$\PageIndex{1}$$: Another Directed Graph

Consider the relation $$s$$ whose digraph is Figure $$\PageIndex{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)\}\text{.}$$

We will be building on the next example in the following section.

Example $$\PageIndex{2}$$: Ordering Subsets of a Two Element Universe

Let $$B = \{1,2\}\text{,}$$ and let $$A = \mathcal{P}(B) = \{\emptyset, \{1\}, \{2\}, \{1,2\}\}\text{.}$$ Then $$\subseteq$$ is a relation on $$A$$ whose digraph is Figure $$\PageIndex{4}$$. Figure $$\PageIndex{4}$$: Graph for set containment on subsets of $$\{1,2\}$$

We will see in the next section that since $$\subseteq$$ 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 $$\PageIndex{1}$$

Let $$A = \{1, 2, 3, 4\}\text{,}$$ and let $$r$$ be the relation $$\leq$$ on $$A\text{.}$$ Draw a digraph for $$r\text{.}$$ Figure $$\PageIndex{5}$$: Digraph for $$\leq$$ Figure $$\PageIndex{6}$$: Hasse diagram for $$\leq$$

Exercise $$\PageIndex{2}$$

Let $$B = \{1,2, 3, 4, 6, 8, 12, 24\}\text{,}$$ and let $$s$$ be the relation “divides” on $$B\text{.}$$ Draw a digraph for $$s\text{.}$$

Exercise $$\PageIndex{3}$$

Let $$A=\{1,2,3,4,5\}\text{.}$$ Define $$t$$ on $$A$$ by $$a t b$$ if and only if $$b - a$$ is even. Draw a digraph for $$t\text{.}$$

See Figure $$\PageIndex{7}$$ Figure $$\PageIndex{7}$$: Digraph of the relation $$t$$

Exercise $$\PageIndex{4}$$

Let $$A$$ be the set of strings of 0's and 1's of length 3 or less. This includes the empty string, $$\lambda\text{,}$$ which is the only string of length zero.

1. Define the relation of $$d$$ on $$A$$ by $$x d y$$ if $$x$$ is contained within $$y\text{.}$$ For example, $$01 d 101\text{.}$$ Draw a digraph for this relation.
2. Do the same for the relation $$p$$ defined by $$x p y$$ if $$x$$ is a prefix of $$y\text{.}$$ For example, $$10 p 101\text{,}$$ but $$01 p 101$$ is false.

Exercise $$\PageIndex{5}$$

Recall the relation in Exercise 6.1.5 of Section 6.1, $$\rho$$ defined on the power set, $$\mathcal{P}(S)\text{,}$$ of a set $$S\text{.}$$ The definition was $$(A,B) \in \rho$$ iff $$A\cap B = \emptyset\text{.}$$ Draw the digraph for $$\rho$$ where $$S = \{a, b\}\text{.}$$

Exercise $$\PageIndex{6}$$

Let $$C= \{1,2, 3, 4, 6, 8, 12, 24\}$$ and define $$t$$ on $$C$$ by $$a t b$$ if and only if $$a$$ and $$b$$ share a common divisor greater than 1. Draw a digraph for $$t\text{.}$$

6.2: Graphs of Relations on a Set is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Al Doerr & Ken Levasseur.