Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News Sign UpSign In
| Download

Worksheets related to Applied Discrete Structures

Views: 15734
Image: ubuntu2004
Kernel: SageMath 9.2

An Introduction to Relations using Sage 

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.

A=range(10) A
range(0, 10)

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

tuples(A,2)
[(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.

r=random_sublist(tuples(A,2),0.25) r
[(0, 7), (0, 8), (1, 6), (2, 0), (2, 1), (2, 9), (3, 3), (3, 5), (3, 9), (4, 6), (5, 5), (5, 9), (6, 1), (6, 8), (6, 9), (7, 1), (7, 5), (8, 6), (9, 4), (9, 5)]

Next, we'll be creating a dictionary and will need to extract the entries of pairs.

pair=(4,5) pair[0]
4

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.

rd={} for p in r: if p[0] in rd: rd[p[0]].append(p[1]) else: rd[p[0]]=[p[1]]

To recover the information defined within a (small) dictionary, use the , or methods.  With , the result is a list of pairs where the first entry is related to all values in the list that makes up the second entry. You can recover just the first entries, with , or the second entries of items with .

rd.items()
dict_items([(0, [7, 8]), (1, [6]), (2, [0, 1, 9]), (3, [3, 5, 9]), (4, [6]), (5, [5, 9]), (6, [1, 8, 9]), (7, [1, 5]), (8, [6]), (9, [4, 5])])
rd.keys()
dict_keys([0, 1, 3, 4, 5, 6, 7, 8, 9])
rd.values()
dict_values([[0, 3, 4, 5, 7], [5, 6, 8], [0, 3, 9], [6, 9], [0], [0, 2, 9], [9], [2, 3, 5, 7], [0, 1, 6, 8]])

Now we can create a digraph using the dictionary [removed]rd.

g=DiGraph(rd) g
Image in a Jupyter notebook

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

g.plot()
Image in a Jupyter notebook
g.density()
13/50
for k in range(10): print(k, g.distance(0,k))
0 0 1 2 2 +Infinity 3 +Infinity 4 4 5 2 6 2 7 1 8 1 9 3
g.distance(9,1)
+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.

R=g.adjacency_matrix() R
[0 0 0 0 0 0 0 1 1 0] [0 0 0 0 0 0 1 0 0 0] [1 1 0 0 0 0 0 0 0 1] [0 0 0 1 0 1 0 0 0 1] [0 0 0 0 0 0 1 0 0 0] [0 0 0 0 0 1 0 0 0 1] [0 1 0 0 0 0 0 0 1 1] [0 1 0 0 0 1 0 0 0 0] [0 0 0 0 0 0 1 0 0 0] [0 0 0 0 1 1 0 0 0 0]

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

R*R
[0 1 0 0 0 1 1 0 0 0] [0 1 0 0 0 0 0 0 1 1] [0 0 0 0 1 1 1 1 1 0] [0 0 0 1 1 3 0 0 0 2] [0 1 0 0 0 0 0 0 1 1] [0 0 0 0 1 2 0 0 0 1] [0 0 0 0 1 1 2 0 0 0] [0 0 0 0 0 1 1 0 0 1] [0 1 0 0 0 0 0 0 1 1] [0 0 0 0 0 1 1 0 0 1]

The cube gives us information on paths of length 3.

R*R*R
[0 1 0 0 0 1 1 0 1 2] [0 0 0 0 1 1 2 0 0 0] [0 2 0 0 0 2 2 0 1 2] [0 0 0 1 2 6 1 0 0 4] [0 0 0 0 1 1 2 0 0 0] [0 0 0 0 1 3 1 0 0 2] [0 2 0 0 0 1 1 0 2 3] [0 1 0 0 1 2 0 0 1 2] [0 0 0 0 1 1 2 0 0 0] [0 1 0 0 1 2 0 0 1 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.

g.transitive_closure().adjacency_matrix()
Example 2 - Prime Steps

We define rr on the divisors of 60 by arb⇔ba a r b \Leftrightarrow \frac{b}{a} is a prime.

D=60.divisors();D
[1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]
r={}; for p in tuples(D,2): if (p[1]//p[0]).is_prime(): if p[0] in r: r[p[0]]=r[p[0]]+[p[1]] else: r[p[0]]=[p[1]] r
{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]}
DiGraph(r).plot(tree_root=1)
Image in a Jupyter notebook

Example 3.

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.

s={} s[0]=[1] s[1]=[2] s[2]=[3] s[3]=[4]
DiGraph(s).plot()

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

DiGraph(s).transitive_closure().plot()

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⋅b(mod17)a\cdot b (mod 17)  is defined to be the remainder when 17 is divided into a⋅ba\cdot b.  For example 5⋅10(mod17)=165\cdot 10 (mod 17) = 16  since 5⋅10=50=17⋅2+165\cdot 10 = 50 = 17\cdot 2 + 16

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

B=range(1,17) B
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

We define the relation mm on BB by  (a,b)∈m(a, b)\in m  if 3⋅x(mod17)=y3\cdot x (mod 17) = y  or 5⋅x(mod17)=y5\cdot x (mod 17) = y.  In Sage, this translates to the following function.

def m(x,y): return (3*x).mod(17)==y or (5*x).mod(17)==y

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.

md={} for k in B: for j in B: if m(k,j): if k in md: md[k].append(j) else: md[k]=[j]
g=DiGraph(md) g.plot()
Image in a Jupyter notebook
G=g.adjacency_matrix() G
[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.

H=(G*G).apply_map(lambda x: 1 if x!=0 else 0) H
[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.

DiGraph(H).plot()
Image in a Jupyter notebook