![[graph]](Tutorials.files/kbrgraph.gif)
Graph Theory Tutorials
Chris K. Caldwell (C)
1995
This is the home page for a series of short interactive
tutorials introducing the basic concepts of graph theory. They are designed with
the needs of future high school teachers in mind and are currently being used as
a supplement to our
Mathematical Modeling course (Math 451).
These tutorials are created using the Web Tutor so that most
of the pages of this tutorial require that you pass a quiz before continuing to
the next page, while others ask for a written comment. The Web Tutor must
be able to keep track of your progress, so you will need to register for
each of these courses by pressing the [REGISTER] button on the bottom of
the first page of each tutorial. (You can use the same username and
password for each tutorial, but you will need to register separately for each
course.)
- Introduction
to Graph Theory (6 pages)
- Starting with three motivating problems, this tutorial introduces the
definition of graph along with the related terms: vertex (or node), edge (or
arc), loop, degree, adjacent, path, circuit, planar, connected and component.
[Suggested prerequisites: none]
- Euler
Circuits and Paths
- Beginning with the Königsberg bridge problem we introduce the Euler paths.
After presenting Euler's theorem on when such paths and circuits exist, we
then apply them to related problems including pencil drawing and road
inspection. [Suggested prerequisites: Introduction
to Graph Theory]
- Coloring
Problems (6 pages)
- How many colors does it take to color a map so that no two countries that
share a common border have the same color? This question can be changed to
"how many colors does it take to color a planar graph?" In this tutorial we
explain how to change the map to a graph and then how to answer the question
for a graph. [Suggested prerequisites: Introduction
to Graph Theory]
- Adjacency
Matrices (Not yet available.)
- How do we represent a graph on a computer? The most common solution to
this question, adjacency matrices, is presented along with several algorithms
to find a shortest path... [Suggested prerequisites: Introduction
to Graph Theory]
Related Resources for these Tutorials:
Other Graph Theory Resources on the
Internet:
Chris Caldwell
caldwell@utm.edu