Processing math: 100%
Skip to main content
permalink

Section 10.2 Graphs of Relations on a Set

permalink

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

permalink

Subsection 10.2.1 Digraphs

permalinkLet A={0,1,2,3}, and let

R={(0,0),(0,3),(1,2),(2,1),(3,2),(2,0)}

permalinkIn 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 10.2.1 is a digraph for R. Notice that since 0 is related to itself, we draw a “self-loop” at 0.

permalink
Digraph of the relation r
Figure 10.2.1. Digraph of a relation

permalinkThe 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 10.2.1 could also be presented as in Figure 10.2.2.

permalink
Digraph of the relation r, alternate embedding
Figure 10.2.2. Alternate embedding of the previous directed graph

permalinkA 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 two graphs.

Consider the relation \(R\) whose digraph is Figure 10.2.4. What information does this give us? The graph tells us that \(R\) is a relation on \(A = \{1, 2, 3\}\) and that \(R = \{(1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 3)\}\text{.}\)

permalink
Digraph of the relation \(R\)
Figure 10.2.4. Digraph of the relation \(R\)

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

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 10.2.6.

permalink
Graph for set containment on subsets  of \(\{1,2\}\)
Figure 10.2.6. 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.

permalink

Exercises 10.2.2 Exercises

permalink
1.

Let A={1,2,3,4}, and let R be the relation on A. Draw a digraph for R.

Answer
permalink
Solution to exercise 1 of 6.2
Figure 10.2.7.
permalink
2.

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

permalink
3.

Let A={1,2,3,4,5}. Define T on A by aTb if and only if ba is even. Draw a digraph for T.

Answer

See Figure 10.2.8

permalink
Figure 10.2.8. Digraph of the relation \(T\)
permalink
4.
  1. Let A be the set of strings of 0's and 1's of length 3 or less. Define the relation of D on A by xDy if x is contained within y. For example, 01D101. Draw a digraph for this relation.
  2. Do the same for the relation P defined by xPy if x is a prefix of y. For example, 10P101, but 01P101 is false.
permalink
5.

Recall the relation in Exercise 5 of Section 10.1, ρ defined on the power set, P(S), of a set S. The definition was (A,B)ρ iff AB=. Draw the digraph for ρ where S={a,b}.

permalink
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.