Motivation:

Materials:

1. Graph search game: "The Caves of Trémaux", including game board, player-token, tunnel cards, instructions (setup and flow-chart), 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).

2. Overheads of a simple maze, with some overlays (1, 2, 3, 4), and its final graph representation.

Lesson Plan:

1. 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.
2. 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.
3. Hand out the instructions for setup (or put them on an overhead), and hand out an instructional flow-chart to each group. Describe how a flow-chart 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".
4. The game will be played twice. To play the first version, have them write the word "bottom" in the blank space on the flow-chart (this will result in a "breadth-first search"), and then play the game.
5. Discussion. If you have already done the introductory lesson on graphs, then the students should have no problem seeing why this game is a graph-search problem. The analogy between caves/tunnels and vertices/edges is compelling.
6. Explain that breadth-first 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 breadth-first 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.
7. 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 breadth-first 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.
8. 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 flow-chart. (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.
9. Ask the students what is different about the two search strategies.
10. Explain that this second method is called depth-first 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 already-visited 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 already-explored 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 completely-explored 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 depth-first strategy.
11. 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.
12. What advantages does depth-first search have? Depth-first search is useful for determining structural properties of a graph or a directed graph (one with one-way 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 cut-nodes using depth-first search (though how to do would only be suitable for an advanced lesson). This is important since such nodes correspond to weak-links in a communication network.
13. To demonstrate one context in which depth-first 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 depth-first search of the graph, showing how the search guides us through the maze. Depth-first search algorithms were probably first discovered for solving maze-search problems. (Trémaux appears to be one of the earliest references.)
14. 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 breadth-first 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:

Variations:

Many variant games are possible: allow only one step along a tunnel for each move (this discourages breadth-first 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 breadth-first, or depth-first search, but none were completely satisfactory. Your ideas are welcome.

Standards:

• NCTM K-4:  1, 2, 3, 4, 8, 9.
• NCTM 5-8:  1, 2, 3, 4.
• NCTM 9-12:  1, 2, 3, 4, 12.

Skills:

• Problem solving / reasoning / communication / connections
• Spatial sense