Sage Quickstart for Graph Theory and Discrete Mathematics

This Sage worksheet was developed for the MAA PREP Workshop "Sage: Using Open-Source Mathematics Software with Undergraduates" (funding provided by NSF DUE 0817071).

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.  And its companion "digraphs" as well.

{{{id=1| graphs. /// }}}

Visualizing a graph is similar to plotting functions.

{{{id=4| G = graphs.HeawoodGraph() plot(G) /// }}}

Defining your own graph is easy.  One way is the following; we put a vertex next to a list (recall this concept from the programming tutorial) with a colon, to show its adjacent vertices, and combine all these in curly braces (you may have seen this called a dictionary before).  Adjacency matrices, other graphs, and similar inputs are also recognized.

{{{id=15| H=Graph({0:[1,2,3], 4:[0,2], 6:[1,2,3,4,5]}) plot(H) /// }}}

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.

{{{id=17| H.set_pos(H.layout_circular()) plot(H) /// }}}

Vertices can be lots of things, for example the codewords of an error-correcting code.  (The one caveat is that they need to be "immutable", like Python's tuples.)  Here we have a matrix over the integers and a matrix of variables.  

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

Edges can be labeled.

{{{id=13| L=graphs.CycleGraph(5) for edge in L.edges(): u = edge[0] v = edge[1] L.set_edge_label(u, v, u*v) 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.

{{{id=19| C = graphs.CubeGraph(3) plot(C) /// }}} {{{id=20| Aut=C.automorphism_group() print "Order of automorphism group: ", Aut.order() print "Group: \n", Aut /// }}} {{{id=21| C.spectrum() /// }}}

Latex support for graphs will soon be vastly improved.

Here's a taste: http://trac.sagemath.org/sage_trac/attachment/ticket/9074/heawood-graph-latex.png

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

{{{id=23| pets = ['dog', 'cat', 'snake', 'spider'] C=Combinations(pets) C.list() /// }}} {{{id=22| for pair in Combinations(pets, 2): print "The " + pair[0] + " chases the " + pair[1] + "." /// }}} {{{id=25| for pair in Permutations(pets, 2): print pair /// }}}

Cryptography (for education)

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

Coding Theory

Linear Binary Codes, aka Group Codes

Start with a generator matrix over $\ZZ_2$.

{{{id=28| 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]]) C = LinearCode(G) /// }}} {{{id=32| C.is_self_dual() /// }}} {{{id=33| D = C.dual_code() D /// }}} {{{id=34| D.basis() /// }}} {{{id=35| D.automorphism_group_binary_code() /// }}} {{{id=36| /// }}}