*Applied Discrete Structures *by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution - Noncommercial - ShareAlike 3.0 United States License.

This document describes the basic ways in which a relation can be represented with Sage. These topics are introduced in chapter 6 of *Applied Discrete Structures*.

**Example 1.** Consider the "random relation" the set of digits, 0 through 9, which each pair of digits is related with probablity 0.25. The list of digits, which we call A, is created using **range**. In Python, the default first number in range is 0 and the list specification is "open on the right" so that the upper limit is not included. Therefore **range(10)** produces the digits 0 through 9.

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Here is the complete list of pairs from which we draw approximately 25% for our relation.

[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (2, 9), (3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (4, 7), (4, 8), (4, 9), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6), (5, 7), (5, 8), (5, 9), (6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6), (6, 7), (6, 8), (6, 9), (7, 0), (7, 1), (7, 2), (7, 3), (7, 4), (7, 5), (7, 6), (7, 7), (7, 8), (7, 9), (8, 0), (8, 1), (8, 2), (8, 3), (8, 4), (8, 5), (8, 6), (8, 7), (8, 8), (8, 9), (9, 0), (9, 1), (9, 2), (9, 3), (9, 4), (9, 5), (9, 6), (9, 7), (9, 8), (9, 9)]

The result of the next expression is random. The output represents a fundamental way to represent any relation as a set of ordered pairs.

[(0, 0), (0, 1), (0, 4), (0, 8), (1, 5), (1, 6), (1, 7), (2, 2), (2, 6), (2, 7), (3, 1), (3, 4), (3, 6), (3, 8), (4, 5), (5, 1), (5, 2), (5, 5), (5, 6), (5, 7), (5, 9), (6, 1), (6, 3), (6, 9), (7, 5), (7, 8), (8, 3), (8, 4), (8, 7), (9, 0), (9, 3), (9, 8), (9, 9)]

There are several wasy to create a directed graph (**DiGraph**) in Sage. The most basic as a dictionary. The following code creates a dictionary corresponding to the relation.

To recover the information defined within a (small) dictionary, use the

[(0, [0, 1, 4, 8]), (1, [5, 6, 7]), (2, [2, 6, 7]), (3, [1, 4, 6, 8]), (4, [5]), (5, [1, 2, 5, 6, 7, 9]), (6, [1, 3, 9]), (7, [5, 8]), (8, [3, 4, 7]), (9, [0, 3, 8, 9])]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

[[0, 1, 4, 8], [5, 6, 7], [2, 6, 7], [1, 4, 6, 8], [5], [1, 2, 5, 6, 7, 9], [1, 3, 9], [5, 8], [3, 4, 7], [0, 3, 8, 9]]

Now we can create a digraph using the dictionary rd .

Looped digraph on 10 vertices

We can plot the graph. For larger relations, the information you get may not be very easy to read, but here it is clear.

33/100

0 0
1 1
2 3
3 2
4 1
5 2
6 2
7 2
8 1
9 3

2

Here is the adjacency matrix of the graph. Row i column j is 1 if the edge [i,j] is part of the relation. Recall that in Python, indexing of matrices starts at 0 just as with lists; so the first row is row 0, corresponding to the digit 0. This is why we used the digits as our vertex set.

[1 1 0 0 1 0 0 0 1 0]
[0 0 0 0 0 1 1 1 0 0]
[0 0 1 0 0 0 1 1 0 0]
[0 1 0 0 1 0 1 0 1 0]
[0 0 0 0 0 1 0 0 0 0]
[0 1 1 0 0 1 1 1 0 1]
[0 1 0 1 0 0 0 0 0 1]
[0 0 0 0 0 1 0 0 1 0]
[0 0 0 1 1 0 0 1 0 0]
[1 0 0 1 0 0 0 0 1 1]

The square of this matrix gives us information on the number of paths of length 2 between any two vertices.

[1 1 0 1 2 2 1 2 1 0]
[0 2 1 1 0 2 1 1 1 2]
[0 1 1 1 0 1 1 1 1 1]
[0 1 0 2 1 2 1 2 0 1]
[0 1 1 0 0 1 1 1 0 1]
[1 2 2 2 0 3 3 3 2 3]
[1 1 0 1 1 1 2 1 2 1]
[0 1 1 1 1 1 1 2 0 1]
[0 1 0 0 1 2 1 0 2 0]
[2 2 0 2 3 0 1 1 3 1]

The cube gives us information on paths of length 3.

[1 5 2 2 3 7 4 4 4 3]
[2 4 3 4 2 5 6 6 4 5]
[1 3 2 3 2 3 4 4 3 3]
[1 5 2 2 2 6 5 3 5 4]
[1 2 2 2 0 3 3 3 2 3]
[4 9 5 8 5 8 9 9 9 9]
[2 5 1 5 4 4 3 4 4 4]
[1 3 2 2 1 5 4 3 4 3]
[0 3 2 3 2 4 3 5 0 3]
[3 5 0 5 7 6 4 5 6 2]

The matrices above are technically not adjacencly matrices since they are not 0-1 matrices. See Example 3, below, for how to remedy this situation.

[1 1 1 1 1 1 1 1 1 1]
[1 1 1 1 1 1 1 1 1 1]
[1 1 1 1 1 1 1 1 1 1]
[1 1 1 1 1 1 1 1 1 1]
[1 1 1 1 1 1 1 1 1 1]
[1 1 1 1 1 1 1 1 1 1]
[1 1 1 1 1 1 1 1 1 1]
[1 1 1 1 1 1 1 1 1 1]
[1 1 1 1 1 1 1 1 1 1]
[1 1 1 1 1 1 1 1 1 1]

We define $r$ on the divisors of 60 by $a r b \Leftrightarrow \frac{b}{a}$ is a prime.

[1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]

{1: [2, 3, 5], 2: [4, 5, 6, 10, 15], 3: [6, 10, 15], 4: [10, 12, 15, 20, 30], 5: [10, 12, 15], 6: [12, 15, 20, 30], 10: [20, 30], 12: [30, 60], 15: [30], 20: [60], 30: [60]}

This short example illustrates the transitive closure of a relation. We start by defining a relation directly as a simple dictionary. The graph is a "chain" of length 4.

The transitive closure of a relation is the smallest *transitive relation* containing that relation.

**Example 3. **This next example is of a relation that is defined in terms of a boolean function. It is based on mod 17 arithmetic, where $a\cdot b (mod 17)$ is defined to be the remainder when 17 is divided into $a\cdot b$. For example $5\cdot 10 (mod 17) = 16$ since $5\cdot 10 = 50 = 17\cdot 2 + 16$

The set of remainders when you divide by 17 is $\{0, 1, 2, \ldots , 16\}$ but since 17 is prime and we start with the positive remainders, products will never equal 0 mod 17.

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

We define the relation $m$ on $B$ by $(a, b)\in m$ if $3\cdot x (mod 17) = y$ or $5\cdot x (mod 17) = y$. In Sage, this translates to the following function.

Changing the number 3 and 5 in the definition above to 3 and 6 creates an interesting alternative relation. Also changing the modulus can be interesting, but if you use a non-prime modulus, you have to include 0 as a possible remainder.

Again, we build a dictionary based on the boolean function.

[0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0]
[0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0]
[0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0]
[1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1]
[0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0]
[0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0]
[0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0]

The square of relation m can be determined by squaring the adjacency matrix of m. Thanks to Jason Grout, who pointed out how to turn all nonzero entries in the product to a 1. By doing that you lose the information about the number of paths of length two between any pair of vertices, but the plot of the graph is much nicer.

[0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0]
[1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1]
[0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0]
[0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0]
[0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0]
[0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0]
[0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0]
[1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0]
[0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1]
[0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0]
[0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0]
[0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0]
[0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0]
[0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0]
[1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1]
[0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0]

Here is the graph of the square of m, but with multiple edges.

[0 1 0 1 1]
[0 1 0 1 1]
[0 1 0 1 1]
[0 1 0 1 1]
[0 1 0 1 1]

[(0, 1, None), (1, 3, None), (2, 3, None), (3, 4, None), (4, 1, None)]