
Copyright (c) 1998, C. Heeren, T. Magliery, and L. Pitt.
This lesson and supporting materials may be copied for nonprofit educational
use only.
Motivation:
A fundamental problem on graphs is that of search (or traversal). A
computer cannot "see" an entire graph at once, no more than you could
see the entire road system of a small town. Suppose your goal was to
visit all of the intersections to check if the stop signs were
properly placed and the traffic signals in working order. Without a map
of the town, can you do it without retracing your steps too many
times? The lesson on Graphs introduced a
number of problems where graph exploration was important. In this
lesson, students explore different graph search strategies, and the
bookkeeping techniques required to do an organized search through a complicated
space.
Materials:

Graph search game: "The Caves of Trémaux", including game
board, playertoken, tunnel cards, instructions (setup and flowchart),
grease pencils, and plastic dixie cups.
If you do not have access to the game (ours is
available for loan), you can
make
your own, or even
easier, you can implement the game at a moment's notice with just
pencil and paper (see description later).
 Overheads of a simple maze, with
some overlays
(1,
2,
3,
4),
and its final graph representation.
Lesson Plan:

Explain the motivation for the lesson.
Tell the students that they are explorers who have
stumbled into a large cave consisting of many different rooms and
tunnels connecting some of the rooms.
The Trémaux trolls were
discovered there  beasts who are as ferocious as they are slow.
It is easy to run away from the trolls, provided you know where you are
going. In order to make the caves safe for future explorers, the students' goal
is to draw a map that completely describes the cave system.
On the playing board, the rooms are represented by numbered ovals 1 through 10,
and during play, the students will be using the grease pencil to draw the tunnels
that have been found between different rooms. The token will show where they
are in the cave at any time.
 The game is not competitive; we suggest students work in small groups (2 or 3)
and cooperate in following the instructions to explore the caves.
 Hand out the instructions for setup (or put them on an overhead), and
hand out an instructional flowchart to each group. Describe how a flowchart
works:

Place a marker (stone, chip, etc.) on the top oval labeled "start".
(This marker is an optional device to help the students remember what
instruction is currently being followed.) The marker is then moved along the arrow
to the next shape. (In this case, it will be the oval labeled "new turn".)

Whenever the marker is moved to a rectangle, the students should follow the
instructions in the rectangle, and then move the marker to the next shape, as
indicated by the arrow.

Whenever the marker is moved to a diamond, the students should read the question.
If the answer to the question is "yes", then the marker is moved along the arrow
labeled "yes" to the next shape. Otherwise, they should move the marker along
the arrow labeled "no".

The game will be played twice.
To play the first version, have them write
the word "bottom" in the blank space on the flowchart
(this will result in a "breadthfirst search"), and then play the
game.

Discussion.
If you have already done the introductory lesson on graphs, then the
students should have no problem seeing why this game is a graphsearch
problem. The analogy between caves/tunnels and vertices/edges is
compelling.

Explain that breadthfirst search
is how a cautious explorer might search. First,
explore all of the rooms the beginning room is connected to, by backing
up immediately after exploring a room, so that you may explore the
next tunnel out of the beginning room. After all of the tunnels out
of the starting room have been explored, then begin to explore all of
the tunnels leading out from one of the rooms you discovered connected
to the starting room. After all tunnels connected to any of those
have been explored, ... etc. Thus, the exploration can be thought of
as emanating outward from the starting location, and slowly
encompassing more and more of the graph "in all directions".
When a computer does breadthfirst search, it keeps a list (represented
by the cups) of rooms that it needs to explore after it finishes exploring
the current room. Thus, as each new room (cup) is encountered, its name is placed
at the end of the list (the bottom of the stack), and it is not explored
until all rooms above it have been completely explored.

What is the meaning of the numbers that are written on the sides of
the cups? Have the students write the numbers that are on the side of
each cup in the corresponding oval on the game board. (Thus, if the
cup with "5" on the top had the number 3 on its side, then the
students would write "3" in the oval for room 5.) What do they
notice? The rooms that are farther away from the starting room have
higher numbers! In fact, the number in a room is exactly the fewest
number of tunnels needed to reach that room from the starting room.
One of the advantages of breadthfirst search is that it automatically
computes the shortest distance (assuming each tunnel has the same
length) from the starting location to every other vertex in the graph.
In fact, the first time a room is encountered, the distance to it from
the starting room using just the tunnels explored so far, is in fact
the shortest distance to it even if other (unexplored) tunnels could
be used. No information later uncovered can result in a shorter path
from the starting room.

Now we explore a different strategy. The students should erase the game boards
and the numbers on the sides of the cups, and write "top" instead of "bottom"
in the blank space on the instruction flowchart. (So now, cups will be placed
on top of the cup stack.)
Replace all of the cards in their respective piles, return the playing token
to the same starting room, and play again.
 Ask the students what is different about the two search strategies.

Explain that this second method is called
depthfirst search:
This type of search is for the bold at heart. To do this, go deeper and
deeper into the graph, not turning back to retrace your path until you
find yourself back at an alreadyvisited location (visible by the
bread crumbs that you've left there). Then, back up along the
edge/tunnel that you've just explored (that led you to the
alreadyexplored room), and try a different edge from that room. If
this leads to a new place, continue being bold. Otherwise, back up
and try another tunnel. Only once all tunnels out of a room have been
explored, do you back up and explore the room you visited before you
visited the now completelyexplored room for the first time.
Since computers cannot leave bread crumbs, they keep a list of vertices
(rooms) that they have explored. In the game, this list is represented by
the stack of cups. Notice that a new cup is placed on the top of the stack
even before all of the tunnels from the current room (cup) have been explored.
This method of keeping a stack is a means of implementing a depthfirst
strategy.

Again, have them write the numbers from the sides of the cups into the
corresponding rooms on the game board. Can they determine a pattern?
Do the numbers correspond to the shortest distance from the start? No!
In a depth first search, information about the shortest distance from
the starting vertex is not readily available.

What advantages does depthfirst search have?
Depthfirst search is useful for determining structural properties of
a graph or a directed graph (one with oneway tunnels). If you did
the satellite example from the introductory graph lesson, recall the
satellites whose failure caused the network to become disconnected 
separating communication between satellites on "different sides" of
the failing satellite. These are called "cut nodes"  a node or
vertex whose removal would separate the graph into two or more pieces.
One can efficiently find cutnodes using depthfirst search (though how to do
would only be suitable for an advanced lesson). This is
important since such nodes correspond to weaklinks in a communication
network.

To demonstrate one context in which depthfirst search is a good
strategy, put up the overhead of the simple maze.
Then show the graph representation of the maze, and following the instructions,
do a depthfirst search of the graph, showing how the search guides us through
the maze. Depthfirst search algorithms were probably first discovered for
solving mazesearch problems. (Trémaux appears to be one of the
earliest references.)
 What advantages or disadvantages are there for some of the
strategies that you've explored? On the internet, if you are seeking
information at a website which has no search facility, you need to
click on hyperlinks to see different web pages. Do you tend to boldly
do a depth first search, or more cautiously use a breadthfirst
strategy? If you have very little idea where the information will be
found, which seems more appropriate? If you have a pretty good idea
of where the item will be found, which seems more appropriate?
Conclusion:
A game demonstrates the fun of graph exploration. People, and
computers, use different strategies to explore properties such as
connectivity, distance between vertices, different paths, etc.
Different strategies are useful for different purposes, and
have different advantages.
Variations:
If you do not have access to the game materials, and do not want to take
the time to construct the game, this lesson can be taught using three
students as follows: One student (called the "gamemaster")
draws a secret graph with up to 10
vertices, and decides what treasure is at each vertex. The gamemaster
tells the players how many tunnels lead out of the first room. The
players choose which tunnel to explore (1st, 2nd, etc.) out of the
first room. (The gamemaster should adopt a method of numbering the
tunnels leading from each room). The gamemaster tells the player
where the chosen tunnel leads to
The players together
draw a map of the caves/tunnels as they explore, until they have
completely reconstructed the gamemaster's graph. (These may look
quite different, although the connectivity relationships should all be
the same.) If there are only two students, one student can be the
gamemaster while the other student explores, and then they can switch
roles. Our board game was derived from this simple pencil and paper
exercise, and is just a snazzy version, that allows the game itself to
slowly reveal a hidden graph.
Many variant games are possible: allow only one step along a tunnel
for each move (this discourages breadthfirst search). Charge for
different edges being explored. Roll a die to determine along how many
edges you're allowed to move the token.
We've tried to think of different reward structures that
encouraged either breadthfirst, or depthfirst search, but none were
completely satisfactory. Your ideas are welcome.
Standards:
 NCTM K4: 1, 2, 3, 4, 8, 9.
 NCTM 58: 1, 2, 3, 4.
 NCTM 912: 1, 2, 3, 4, 12.
Skills:
 Problem solving / reasoning / communication / connections
 Spatial sense
Copyright (c) 1998, C. Heeren, T. Magliery, and L. Pitt.
This lesson and supporting materials may be copied for nonprofit educational
use only.
