PREP Quickstart, Graph Theory and Discrete Math
system:sage


<h1 style="font-size: 2em;">Sage Quickstart for Graph Theory and Discrete Mathematics</h1>
<p>This&nbsp;<a href="http://www.sagemath.org" target="_blank">Sage</a>&nbsp;worksheet was developed for the MAA PREP Workshop "Sage: Using Open-Source Mathematics Software with Undergraduates" (funding provided by NSF DUE 0817071).</p>
<p>As computers are discrete and finite, topics from discrete mathematics are natural to implement and use.&nbsp; We'll start with Graph Theory.</p>
<h2>Graph Theory</h2>

<p>The pre-defined "graphs" object provides an abundance of examples.&nbsp; And its companion "digraphs" as well.</p>

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

<p>Visualizing a graph is similar to plotting functions.</p>

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

<p>Defining your own graph is easy.&nbsp; 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 <em>dictionary</em>&nbsp;before).&nbsp; Adjacency matrices, other graphs, and similar inputs are also recognized.</p>

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

<p>Graphs have "position" information for location of vertices.&nbsp; There are several different ways to compute a layout, or you can compute your own.&nbsp; Pre-defined graphs often come with "nice" layouts.</p>

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

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

{{{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)
///
}}}

<p>Edges can be labeled.</p>

{{{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)
///
}}}

<p>There are natural connections to other areas of mathematics.&nbsp; Here we compute the automorphism group and eigenvalues of the skeleton of a cube.</p>

{{{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()
///
}}}

<p>Latex support for graphs will soon be vastly improved.</p>
<p>Here's a taste: <a href="http://trac.sagemath.org/sage_trac/attachment/ticket/9074/heawood-graph-latex.png">http://trac.sagemath.org/sage_trac/attachment/ticket/9074/heawood-graph-latex.png</a></p>

<h2>Discrete Mathematics</h2>
<p>Discrete mathematics is a broad area, and Sage has excellent support for much of it.&nbsp; This is largely due to the "sage-combinat" group.&nbsp; These developers previously developed for muPad (as "mupad-combinat") but switched over to Sage shortly before muPad was sold.</p>

<h3><span style="color: #ff0000;"><span style="background-color: #ffffff;">Simple Combinatorics</span></span></h3>

{{{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
///
}}}

<h3><span style="color: #ff0000;">Cryptography (for education)</span></h3>

{{{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
///
}}}

<h3><span style="color: #ff0000;">Coding Theory</span></h3>

<p>Linear Binary Codes, aka Group Codes</p>
<p>Start with a generator matrix over $\ZZ_2$.</p>

{{{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|

///
}}}