# Sage Quickstart for Graph Theory and Discrete Mathematics¶

As computers are discrete and finite, topics from discrete mathematics are natural to implement and use. We’ll start with Graph Theory.

## Graph Theory¶

The pre-defined graphs object provides an abundance of examples. Just tab to see!

sage: graphs.[tab]


Its companion digraphs has many built-in examples as well.

Visualizing a graph is similar to plotting functions.

sage: G = graphs.HeawoodGraph()
sage: plot(G)


Defining your own graph is easy. One way is the following.

• Put a vertex next to a list (recall this concept from the programming tutorial) with a colon, to show its adjacent vertices. For example, to put vertex 4 next to vertices 0 and 2, use 4:[0,2].
• Now combine all these in curly braces (in the advanced appendix to the programming tutorial, this is called a dictionary ).
sage: H=Graph({0:[1,2,3], 4:[0,2], 6:[1,2,3,4,5]})
sage: plot(H)


Adjacency matrices, other graphs, and similar inputs are also recognized.

Graphs have “position” information for location of vertices. There are several different ways to compute a layout, or you can compute your own. Pre-defined graphs often come with “nice” layouts.

sage: H.set_pos(H.layout_circular())
sage: plot(H)


Vertices can be lots of things, for example the codewords of an error-correcting code.

Note

Technical caveat: they need to be “immutable”, like Python’s tuples.

Here we have a matrix over the integers and a matrix of variables as vertices.

sage: a=matrix([[1,2],[3,4]])
sage: var('x y z w')
(x, y, z, w)
sage: b=matrix([[x,y],[z,w]])
sage: a.set_immutable()
sage: b.set_immutable()
sage: K=DiGraph({a:[b]})
sage: show(K, vertex_size=800)


Edges can be labeled.

sage: L=graphs.CycleGraph(5)
sage: for edge in L.edges():
...       u = edge[0]
...       v = edge[1]
...       L.set_edge_label(u, v, u*v)
sage: plot(L, edge_labels=True)


There are natural connections to other areas of mathematics. Here we compute the automorphism group and eigenvalues of the skeleton of a cube.

sage: C = graphs.CubeGraph(3)
sage: plot(C)

sage: Aut=C.automorphism_group()
sage: print "Order of automorphism group: ", Aut.order()
Order of automorphism group:  48
sage: print "Group: \n", Aut
Group:
Permutation Group with generators [('010','100')('011','101'), ('001','010')('101','110'), ('000','001')('010','011')('100','101')('110','111')]

sage: C.spectrum()
[3, 1, 1, 1, -1, -1, -1, -3]


There is a huge amount of LaTeX support for graphs. The following graphic shows an example of what can be done; this is the Heawood graph.

Press ‘tab’ at the next command to see all the available options.

sage: sage.graphs.graph_latex.GraphLatex.set_option?

## More Discrete Mathematics¶

Discrete mathematics is a broad area, and Sage has excellent support for much of it. This is largely due to the “sage-combinat” group. These developers previously developed for MuPad (as “mupad-combinat”) but switched over to Sage shortly before MuPad was sold.

### Simple Combinatorics¶

Sage can work with basic combinatorial structures like combinations and permutations.

sage: pets = ['dog', 'cat', 'snake', 'spider']
sage: C=Combinations(pets)
sage: C.list()
[[], ['dog'], ['cat'], ['snake'], ['spider'], ['dog', 'cat'], ['dog', 'snake'], ['dog', 'spider'], ['cat', 'snake'], ['cat', 'spider'], ['snake', 'spider'], ['dog', 'cat', 'snake'], ['dog', 'cat', 'spider'], ['dog', 'snake', 'spider'], ['cat', 'snake', 'spider'], ['dog', 'cat', 'snake', 'spider']]

sage: for pair in Combinations(pets, 2):
...       print "The " + pair[0] + " chases the " + pair[1] + "."
The dog chases the cat.
The dog chases the snake.
The dog chases the spider.
The cat chases the snake.
The cat chases the spider.
The snake chases the spider.

sage: for pair in Permutations(pets, 2):
...       print pair
['dog', 'cat']
['dog', 'snake']
['dog', 'spider']
['cat', 'dog']
['cat', 'snake']
['cat', 'spider']
['snake', 'dog']
['snake', 'cat']
['snake', 'spider']
['spider', 'dog']
['spider', 'cat']
['spider', 'snake']


Of course, we often want these for numbers, and these are present as well. Some are familiar:

sage: Permutations(5).cardinality()
120


Others somewhat less so:

sage: D = Derangements([1,1,2,2,3,4,5])
sage: D.list()[:5]
[[2, 2, 1, 1, 4, 5, 3], [2, 2, 1, 1, 5, 3, 4], [2, 2, 1, 3, 1, 5, 4], [2, 2, 1, 3, 4, 5, 1], [2, 2, 1, 3, 5, 1, 4]]


And some somewhat more advanced – in this case, symmetric polynomials.

sage: s = SymmetricFunctions(QQ).schur()
sage: a = s([2,1])
sage: a.expand(3)
x0^2*x1 + x0*x1^2 + x0^2*x2 + 2*x0*x1*x2 + x1^2*x2 + x0*x2^2 + x1*x2^2


Various functions related to this are available as well.

sage: binomial(25,3)
2300

sage: multinomial(24,3,5)
589024800

sage: falling_factorial(10,4)
5040


Do you recognize this famous identity?

sage: var('k,n')
(k, n)
sage: sum(binomial(n,k),k,0,n)
2^n


### Cryptography (for education)¶

This is also briefly mentioned in the Number theory quickstart. Sage has a number of good pedagogical resources for cryptography.

sage: # Two objects to make/use encryption scheme
sage: #
sage: from sage.crypto.block_cipher.sdes import SimplifiedDES
sage: sdes = SimplifiedDES()
sage: bin = BinaryStrings()
sage: #
sage: # Convert English to binary
sage: #
sage: P = bin.encoding("Encrypt this using S-DES!")
sage: print "Binary plaintext: ", P, "\n"
sage: #
sage: # Choose a random key
sage: #
sage: K = sdes.list_to_string(sdes.random_key())
sage: print "Random key: ", K, "\n"
sage: #
sage: # Encrypt with Simplified DES
sage: #
sage: C = sdes(P, K, algorithm="encrypt")
sage: print "Encrypted: ", C, "\n"
sage: #
sage: # Decrypt for the round-trip
sage: #
sage: plaintxt = sdes(C, K, algorithm="decrypt")
sage: print "Decrypted: ", plaintxt, "\n"
sage: #
sage: # Verify easily
sage: #
sage: print "Verify encryption/decryption: ", P == plaintxt
Binary plaintext:  01000101011011100110001101110010011110010111000001110100001000000111010001101000011010010111001100100000011101010111001101101001011011100110011100100000010100110010110101000100010001010101001100100001

Random key:  0100000011

Encrypted:  00100001100001010011000111000110010000011011101011111011100011011111101111110111110010101000010010001101101010101000010011001010100001010111000010001101000011001001111111110100001000010000110001011000

Decrypted:  01000101011011100110001101110010011110010111000001110100001000000111010001101000011010010111001100100000011101010111001101101001011011100110011100100000010100110010110101000100010001010101001100100001

Verify encryption/decryption:  True


### Coding Theory¶

Here is a brief example of a linear binary code (group code).

Start with a generator matrix over $$\ZZ/2\ZZ$$.

sage: G = matrix(GF(2), [[1,1,1,0,0,0,0], [1,0,0,1,1,0,0], [0,1,0,1,0,1,0], [1,1,0,1,0,0,1]])
sage: C = LinearCode(G)

sage: C.is_self_dual()
False

sage: D = C.dual_code()
sage: D
Linear code of length 7, dimension 3 over Finite Field of size 2

sage: D.basis()
[(1, 0, 1, 0, 1, 0, 1), (0, 1, 1, 0, 0, 1, 1), (0, 0, 0, 1, 1, 1, 1)]

sage: D.permutation_automorphism_group()
Permutation Group with generators [(4,5)(6,7), (4,6)(5,7), (2,3)(6,7), (2,4)(3,5), (1,2)(5,6)]