Discrete Mathematics Teaching Software Project, Robert Morris University

Proposed Software Requirements Document, Revised 2005 – Graphs, Trees, and Networks

Discrete Math Tools Requirements

This document provides the requirements of a software tool intended to aid in the instruction and analysis of several topics in the Discrete Mathematics (Discrete Structures) classroom.

  1. Graphs, Trees, and Networks
  2. Finite Automata (future)
  3. Set Theory (future)
  4. Group Theory (future)

This requirements proposal was drafted for the discrete mathematics teaching software project, Robert Morris University, by Lauren Lilly, Boise, ID, in 2003, with input from Valerie J. Harvey, Robert Morris University. Revised 2005 by Valerie J. Harvey with input from Raymond T. Boute, University of Ghent.

1. Graphs, Trees, and Networks

There seems to be a limited set of tools available to support the drawing and analysis of graphs. The few tools that are available may be limited in capabilities and some are difficult to use. We intend to support the needs of professors as they illumine graph theory and of students as they investigate the nature of graphs, trees, and networks.

General Requirements

This tool shall be easy to use. Entry of nodes and edges shall be accomplished graphically, through the supported matrix forms, data entry, and imported from some file format or formats. The automated experience shall be as consistent with the textbook forms as possible. For example, it should be possible to generate a graph by stating V (the set of vertices) and E (the set of edges) as sets and to see this representation if the graph is generated by direct graphic manipulation.

This tool shall support graphs (including multigraphs); directed and non-directed, trees, Hasse diagrams, state-transition diagrams, and Petri nets.

The tool shall support pseudo-random generation of (relatively simple) graphs and trees (for evaluation by students).

This tool shall support matrices related to graphs; adjacency matrices and incidence matrices. Changes made to these matrices shall affect the graphical display and vice versa.

This tool shall support directed graphs (digraphs) and their representation as ordered pair lists. Changes made to such ordered pair lists shall affect the graphical display and vice versa.

This tool shall support partial orders, such as database designs, related to Hasse diagrams. Changes made to these partial order structures (ordered pair lists) shall affect the graphical display and vice versa.

This tool shall support bipartite graphs and partitions and equivalence relations and identification of equivalence classes.

This tool shall support determination of whether a (relatively simple) graph is reflexive, symmetric, antisymmetric, asymmetric, transitive, cyclic, or acyclic.

The tool shall support 2D representations. 3D representations may be represented as capabilities permit.

The tool shall support weighted edges and appropriate determination of path length for a highlighted path for weighted and unweighted graphs.

The tool shall support evaluation of connectedness for undirected and directed graphs.

The tool shall support network (flow or transport) models with appropriate weighting.

The tool shall support algorithms for analysis and manipulation of graphs; Kruskal, tree traversal, planar and non-planar embedding, checking for isomorphism and correctness of student-generated graphs (as in redrawing of trees using an arbitrarily chosen vertex as the root of the new drawing, for example).

The tool shall identify (to some extent) spanning trees, cycles, and paths, and elements/structures of trees: ancestors, descendents, siblings, root node, terminal (leaf) nodes), cutpoints, bridges.

The tool shall aid in graphical layout of graphs. Multiple techniques may be supported. For example, solving the "rat's nest" problem.

The tool shall support a tutorial mode in which a student may be led through the steps of creating a simple graph and manipulating it.

The tool shall support labeling of edges and nodes. More detailed information about the objects shall be supported. This may include comments or explanations. Labels shall be displayed so as not to interfere with the objects being displayed. Labeling capabilities should be adequate to support full names, as in, for example, “Bacon Number” graph models with actors’ names or database Hasse diagrams with table names. In some cases properties should be capable of being displayed, such as degree of a vertex, level in a tree, flow properties of a network.

The tool shall support graph reduction (or vertex elision) and evaluation.

It shall be easy to change from display to non-display of labels, weights, etc. It shall be easy to highlight a path from one node to another, equivalence classes, domain and range, (proper) subgraphs, cliques, subtrees, neighborhood (of a vertex), etc. It shall be easy to represent the underlying (undirected) graphs of a digraph or underlying graph of a multigraph.

The tool shall support determining whether one graph (tree) is an isomorphism of another (so that a student could propose an isomorphism to a graph for evaluation).

The tool shall not introduce artifacts that would interfere with interpretation of formal structures or are contrary to definitions, for example, an ordering property that would affect the representation of sets.

Visual Requirements

The tool shall graphically display nodes (vertices) and edges (arcs). Labels for these must be displayed optionally. Labeling options shall be adequate to support the variety of routine labeling requirements and styles used for relation/function arrow diagrams, Hasse diagrams, deadlock resource diagrams (see HOLT1971), networks models,

The tool shall allow for large sets of objects.

The tool shall allow for an infinite workspace supported by a scrolling window.

The tool shall allow for the graphical display and the selected matrices (or other underlying structures, such as database schemas for Hasse diagrams, for example) simultaneously.

All versions of the display shall update upon changes to the data by any means.

Automation

The tool shall support simple animation and/or step-by-step animation. Highlighting certain objects one at a time, for example, as in following a path. This animation may be adjusted for speed. This animation shall be displayed one step at a time or timed.

The tool shall demonstrate various tree-traversal algorithms.

The tool shall elucidate breadth-first and depth-first searches in trees.

Computations

The tool shall compute spanning trees, minimal spanning trees for small trees.

The tool shall use Kruskal and Prim's algorithms to find minimal spanning trees.

The tool shall aid in comparing trees and identifying isomorphisms and planar graphs.

The tool shall support and elucidate many of the common theorems of graph theory.

The tool shall aid in finding cycles, paths, simple paths, simple cycles, Hamiltonian cycles, Euler cycles.

The tool shall provide for matrix multiplication, thus An computations given n. This would be followed by the graphical display of the new (An) matrix.

The tool shall support typing of (visually distinguished) nodes/vertices as in deadlock resource graphs (processes and resources) and cycle identification or extraction.

Environmental Requirements

The tool shall be available to as many hardware/operating system platforms as reasonable. These shall include Windows 95+, Linux, and Macintosh.

It shall be possible to export graphics created by the tool to image form to use in other applications.

The tool shall provide access for other programming languages to the data structures of the tool. The tool shall exercise real-time refresh of its own structures as a result. This might be provided by means of a technology such as COM or CORBA, but SOAP (http://www.w3c.org/2000/xp/Group/) is becoming a more generic solution.

References and Resources

[ANDE2004] James A. Anderson, Discrete Mathematics with Combinatorics, 2nd ed. (Prentice Hall, 2004)

[BARN1998] Stephen Barnett, Discrete Mathematics: Numbers and Beyond (Prentice Hall/Addison-Wesley, 1998).

[BOLO1979] Béla Bolobás, Graph Theory: An Introductory Course (Springer, 1979).

[DIES2000] Reinhard Diestel, Graph Theory, 2nd ed. (Springer, 2000).

[DOS2002] John A. Dossey, Albert D. Otto, Lawrence E. Spence, and Charles Vanden Eynden, Discrete Mathematics, 4th ed. (Addison Wesley, 2002).

[EPP2004] Susanna S. Epp, Discrete Mathematics with Applications, 3rd ed. (Brooks/Cole, 2004).

[FOUL1992] L. R. Foulds, Graph Theory Applications (Springer, 1992)

[GARN2003] Rowan Garnier and John Taylor, Discrete Mathematics for New Technology, 2nd ed. (Institute for Physics, 2002)

[GERS2003] Judith L. Gersting, Mathematical Structures for Computer Science: A Modern Treatment of Discrete Mathematics, 5th ed.(W. H. Freeman, 2003)

[GOOD2002] Edgar G. Goodaire and Michael M. Parmenter, Discrete Mathematics with Graph Theory, 2nd ed. (Prentice Hall, 2002)

[GOSS2003] Eric Gossett, Discrete Mathematics with Proof (Prentice Hall, 2003)

[GRAS1996] Winfried Karl Grassmann and Jean-Paul Tremblay, Logic and Discrete Mathematics: A Computer Science Perspective (Prentice Hall, 1996)

[GRIE1993] David Gries and Fred B. Schneider, A Logical Approach to Discrete Math (Springer, 1993)

[GROS2003] Jonathan L. Gross; Jay Yellen , Handbook of Graph Theory (CRC Press, 2003) Table of contents online at: http://www.graphtheory.com/handbook-of-graph-theory-table-of-contents.htm .

 [HARV2003] Valerie J. Harvey, Brian Harris, E. Gregory Holdan, Mark M. Maxwell, David F. Wood, eds., Discrete Mathematics Applications for Information Systems Professionals (Pearson, 2003). Supplement to [JOHN2001].

[HEIN2002] James L. Hein, Discrete Structures, Logic, and Computability, 2nd ed. (Jones and Bartlett, 2002)

[HOLT1971] Richard C. Holt, Some deadlock properties of computer systems,” Proceedings of the third ACM symposium on Operating systems principles (1971), pp. 64-71.

[JOHN2004] Richard Johnsonbaugh, Discrete Mathematics, 6th ed. (Prentice Hall, 2004). [JOHN2001] 5th ed.

[MATO1998] J. Matoušek and J. Nešetřil, Diskrete Mathematik: Eine Entdeckungsreise (Springer, 1998)

[MOTT1986] Joe L. Mott, Abraham Kandel, and Theodore P. Baker, Discrete Mathematics for Computer Scientists & Mathematicians (Reston Prentice Hall, 1986)

[NEHR2003] Werner Nehrlich, Diskrete Mathematik: Basiswissen für Informatiker (Fachbuchverlag Leipzig, 2003).

[ROSS2003] Kenneth A. Ross and Charles R. B. Wright, Discrete Mathematics, 5th ed. (Prentice Hall, 2003)

[SAND2005] Daniel P. Sanders, Graph Theory White Pages [URL: http://www1.cs.columbia.edu/~sanders/graphtheory/

 [TREM1975] J. P. Tremblay and R. Manohar, Discrete Mathematical Structures with Applications to Computer Science (McGraw-Hill, 1975)

[TRUS1999] John Truss, Discrete Mathematics for Computer Scientists, 2nd ed. (Addison-Wesley, 1999)

[WALL2000] W. D. Wallis, A Beginner’s Guide to Graph Theory (Birkäuser, 2000).

RMU, C&IS as of 02/28/2005