Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

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.

clipboard_e22cc9586cdb24a1cd7bc915e0acdad6c.png
Figure 6.2.1Digraph of a relation

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.

clipboard_e8f4e91ae945876a1ee7154a5d6d05442.png
Figure 6.2.2: Alternate embedding of the previous directed graph

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)}.

clipboard_e153cf5de0a05d647870ed8b109363ddf.png
Figure 6.2.3: Digraph of the relation s

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.

clipboard_e0427f4b66176bc81b0300cf2af0bc2af.pngFigure 6.2.4: Graph for set containment on subsets of {1,2}

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

clipboard_ea09140ac71453cfb0834d7d54648dfe6.png

Figure 6.2.5: Digraph for

clipboard_e8ce2c5ec7978bdcc65babe2b61288e7f.png

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 ba is even. Draw a digraph for t.

Answer

See Figure 6.2.7

clipboard_eb94767f831aa7d090c52d93542450a20.png

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.

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

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 AB=. 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.


This page titled 6.2: Graphs of Relations on a Set is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Al Doerr & Ken Levasseur via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?