*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, 6), (1, 2), (1, 6), (2, 1), (2, 5), (2, 7), (2, 9), (3, 3), (3, 4), (3, 5), (4, 0), (4, 1), (4, 3), (4, 4), (4, 7), (4, 8), (5, 1), (5, 7), (6, 0), (6, 6), (7, 0), (7, 8), (8, 2), (8, 3), (8, 6), (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, [6]), (1, [2, 6]), (2, [1, 5, 7, 9]), (3, [3, 4, 5]), (4, [0, 1, 3, 4, 7, 8]), (5, [1, 7]), (6, [0, 6]), (7, [0, 8]), (8, [2, 3, 6]), (9, [9])]

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

[[6], [2, 6], [1, 5, 7, 9], [3, 4, 5], [0, 1, 3, 4, 7, 8], [1, 7], [0, 6], [0, 8], [2, 3, 6], [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.

13/50

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

+Infinity

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.

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

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

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

The cube gives us information on paths of length 3.

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

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 0 0 0 0 0 1 0 0 0]
[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 0 0 0 0 0 1 0 0 0]
[1 1 1 1 1 1 1 1 1 1]
[1 1 1 1 1 1 1 1 1 1]
[0 0 0 0 0 0 0 0 0 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)]