APPLIED MATHEM ATICS /PURE MATHEM ATICS 3240
APPLIED GRAPH THEORY
AM/PM 3240: Applied Graph Theo
If the grid on the right represents a network of roads and the
numbers represent distances between intersections, what’s
the shortest route from A to B? Are you sure?
Suppose you are the operator of a snow plough. After a
severe storm, you have to clear all the streets in the
network shown. Can you plan a route which avoids
travelling along a street you have already cleared? If not,
what route minimizes the total distance you have to travel?
Consider the grid from a different viewpoint. Suppose there
is a town at each intersection and the numbers represent
the distances between towns. Your job is to pave the roads
as economically as possible so that it is possible to travel
between any two towns along pavement. What roads should
Graph theory is not like calculus or linear algebra, subjects you may have already studied. It is much less
structured; there are far fewer to learn. But it is a rich subject with many applications at least some of which
we hope will standard techniques intrigue you to the extent that you’ll want to learn more about them.
Text. Discrete Mathematics by E. G. Goodaire and M. M. Parmenter has been used as a text for this
Marks. Typically 55% of the final grade in this course is awarded for performance on a final examination,
30% to performance on a midterm and 15% for homework.
Calendar description. Algorithms and complexity, definitions and basic properties of graphs, Eulerian and
Hamiltonian chains, shortest path problems, graph coloring, planarity, trees, network flows, emphasis on
applications including scheduling problems, tournaments, and facilities design.
Prerequisite: Either M 2051 or PM 2320.
NOTE: Credit cannot be obtained for both AM/PM 3240 and Computer Science 3741.
Department of Mathematics and Statistics, Memorial University of Newfoundland, St. John’s, NL, A1C 5S7