Graph Theory Lessons
The Petersen Program
What is Petersen?
Petersen is software written by Chris Mawata that can draw, edit and manipulate simple graphs, examine properties of the graphs, and demonstrate them using computer animation. It can display information about a graph like the number of vertices and their degrees, the adjacency matrix, the number of components, and articulation points. It can find complements of graphs, line graphs, find the chromatic number of a graph, check if a graph is bipartite, check if two graphs are isomorphic or if one graph is a subgraph of another and find the dual graph of a planar graph in many cases. Petersen also demonstrates Euler and Hamilton circuits, searches, and algorithms for finding minimum spanning trees.
Intended Users and Hardware requirements
Chris Mawata started the project while on the faculty at UTC, the University of Tennessee at Chattanooga, when he could not find suitable software for beginning Graph Theory classes. The initial users were mathematics majors for whom it was an elective course and computer science students for whom it was a required course. This is still the primary target population although other students, say students of mathematics appreciation or history of mathematics would surely find it useful, perhaps with a different set of exercises. Many high schools have also found the program useful with the instructor re-structuring the presentation for that audiance.
The author has since moved on into training Java programmers and consulting but still makes the original material available at the UTC website and new development at this site. As much of the material as possible will remain free as long as revenues from site licenses justify the expense of maintaining the site.
It is assumed that the students using the software and lessons have some measure of mathematical sophistication; for instance that they are able to write an induction proof etc. They have done second semester calculus and a course in computer programming. The prerequisite courses give an indication of the level of mathematical maturity assumed. The program runs under Jave 6 so any operating system that supports Java 6 or later can run the program.
The subject matter addressed are topics typically found in undergraduate graph theory and discrete structures classes like null graphs, the handshaking lemma, isomorphism, complete graphs, subgraphs, regular graphs, platonic graphs, adjacency matrices, graph coloring, bipartite graphs, simple circuits, Euler and Hamilton circuits, trees, unions and sums of graphs, complements of graphs, line graphs, spanning trees, plane graphs, shortest paths, minimal spanning trees. These topics are central to graph theory and essential to further learning in the area.
The Pedagogical Problem
In writing the software the author was trying to solve several educational and instructional problems. The examples of abstract graphs used in a typical graph theory class tend to be small and trivial for several reasons. One reason is that large and complicated graphs take a long time to draw. Once drawn they are difficult to edit as there are so many edges that it is difficult to erase just the edges you want to erase. Getting information from a large graph (like counting edges, or finding paths and son on) is tedious and long. Because graphs are awkward to manipulate one cannot readily experiment with them without the aid of a computer.
The algorithms in the software are not novel. The only difference between Petersen and commercial and research applications is that in the latter the main aim is to get the results as quickly as possible. On the other hand in an educational setting the primary goal is for the student to be able to visualize the concepts being taught so it is an advantage to use graphics intensively even at the cost of speed. In a nutshell then the author wanted to improve on the complexity of the examples, increase the number of examples available, the types of problems that could be posed, and to introduce multimedia and visualization in the course, thus making it more interesting for the students. The associated web site uses Java Web Start to attain the same goals.
Doing Mathematics By Experiment And Investigation
The author set out to create a tool that can display a graph quickly on the screen, store graphs so that they can easily be recalled at a later time, generate and manipulate graphs in various ways so that students can use the program as an investigative tool. This is not intended to replace any of the traditional activities like lectures, students solving the textbook problems and writing short programs to implement algorithms and so on. Rather, the intention is to augment the class with an experience in doing mathematics by experiment and investigation.
The program helps the instructor to address several learning issues:
- The students get the experience of using the computer as an investigative tool.
- The program allows one to obtain drawings of graphs that are otherwise difficult or impossible to draw. This allow the use of many examples to illustrate ideas.
- The use of animation, impossible to duplicate on a chalk board allows the easy illustration of some concepts.
- The investigation of patterns in order to formulate hypotheses is a way to give students training in problem solving.
- In writing up formal proofs of their conclusions, the students learn the art of writing correct mathematical proofs.
© C. Mawata