About Petersen

What is Petersen?

Petersen is software written by C. 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

This project is targeted at undergraduate beginning classes in Graph Theory. The students who use the software at UTC, the University of Tennessee at Chattanooga, are mathematics majors for whom it is an elective course and computer science students for whom it is a required course. This is 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. 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 will run under Windows 3.1 or Windows95.

Subject Matter

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 author set out to create a tool that could display a graph quickly on the screen, store graphs so that they can easily be recalled at a later time, manipulate graphs in various ways so that students could use the program as an investigative tool. This was 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 was to augment the class with an experience in doing mathematics by experiment and investigation.

By using the program we attempt to address several learning issues:

The students get the experience of using the computer as an investigative tool. Since it is highly likely that they will have to do this in their future careers it is appropriate to expose them to situations of this nature.
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.

The Use of Hypertext Links

Typically the students take the software home (it will fit on a floppy disk) and access the lessons over the internet. This allows the author to make hyperlinks to definitions of terms that appear in the lessons. Future versions of the lessons will also include animation using Java applets. The author is currently working on this. The author is also working on a new version of the porgram in Java which will allow the use of curved edges, handle directed graphs, and also loops.