TOOLS FOR LEARNING ABOUT VERTEX-EDGE GRAPHS

A vertex-edge graph is made up of points, called vertices, and straight or curved lines, called edges, connecting them. The illustration shows three examples.

Graphs have many applications, including such diverse uses as circuit diagrams, PERT charts, and message routing diagrams, and there are many algorithms for determining such things as shortest paths between two vertices. One of the best ways to understand an algorithm is to try it out on various graphs, but this can be tedious if you have to re-draw the graph for every step of the algorithm. The GrafPad, a graph-drawing tool, lets you easily make and modify graphs. The Stepper is a sophisticated programmable tool that walks through algorithms step by step, applying them to the graph in the GrafPad. With these two applets, you can easily gain a hands-on understanding of important graph concepts and learn both the power and limitations of an algorithm.

GrafPad AND Stepper were developed under a grant from SciMath Minnesota (www.scimathmn.org). They were part of an ambitious in-service curriculum for Minnesota teachers wanting greater familiarity with discrete mathematics and with inquiry-based learning. For more information, contact Larry Copes, PhD, principal investigator.

To experiment with the GrafPad, click here.

To try out the Stepper with a spanning-tree algorithm, click here.

The full curriculum is here.