Steve Maurer, Professor of Mathematics here at Swarthmore College, came to talk to us this morning about Graph Theory. Steve has developed a wonderful series of activities using the application Mathematica. If you don't know what Mathematica is, where to get it, or how to use it, you may write to me (Eric Sasson).
Graph TheorySteve began by telling us a little bit about what graph theory is and what it's used for. He provided proof for the claim that it is beginning to appear in curricula from the elementary school level on up. Here's an example of a simple graph:v1€----------€v2 \ \ \ €v3It can be represented by the "adjacency matrix":0 1 0 1 0 1 0 1 0where rows and columns represent v1, v2, v3 and a 1 (alternately, a 0) means there is (alternately, is NOT) an edge connecting the vertices that head that row and column. In graph theory, however, there is a graphical representation that can be represented algebraically in several ways.
Steve found Mathematica an appropriate tool to learn graph theory because it provides symbolic, numeric, and graphical manipulation. Since it was written primarily for calculus, however, the basics for graph theory are not built into Mathematica. Luckily, there's a package that Mathematica can load called Combinatorica that provides the necessary building blocks. Steve has been using and improving upon these two programs to create fascinating interactive ways to study graph theory.
We got a chance to look at some of the projects (written as worksheets or homework assignments) that Steve has made. Since graph theory was new to most of the group, we worked on these assignments as if we were his students. In Mathematica, he provided examples, explanations, questions and suggestions. Since Mathematica is running while they're working, his students can simply change commands and numerical values and observe the results. They also create new graphs, explain them and then hand in their assignments through the Internet.
Minimum Spanning TreesThe last lesson we looked at was one about Minimum Spanning Trees. One of Steve's student workers led us through a presentation (on Mathematica) of an algorithm used to minimize the sum of edge weights in a spanning tree of a graph. These types of problems have important applications in the area of linear optimization (transportation problem, shortest path problem, etc.). This particular case was framed as a problem of minimizing the cost of installing communication lines. After being shown the algorithm, we were given the chance to solve two other problems by hand. The step by step solutions were readily attainable by simply evaluating a cell of expressions in Mathematica.
We were all impressed and we thank Steve for coming by.
Home || The Math Library || Quick Reference || Search || Help