Graph Theory Lesson Plan
Abstract
This lesson is designed to develop students' modeling skills by introducing them to graphical representations of
real world data, maps, and graphs.
Standards (NCTM)
Communication
Organize and consolidate their mathematical thinking through communication
Communicate their mathematical thinking coherently and clearly to peers, teachers, and others
Analyze and evaluate the mathematical thinking and strategies of others
Use the language of mathematics to express mathematical ideas precisely
Student Prerequisites
- Educational:
Students should have:
- a firm understanding of maps and how to navigate them.
- Technological:
Students must be able to:
- perform basic mouse manipulations such as point,
click and drag.
- use a browser such as Netscape for experimenting with
the activities.
Teacher Preparation
Teachers will need:
Students will need:
Lesson Outline
- Focus and Review
- Have students work on the
Town of Iceberg
problem as a review of graphs and an introduction to edges and vertices.
- Objectives
Students will lean how mathematics can be used to model real world situations. Students
will be exposed to algorithmic thinking and problem solving.
- Guided Practice
- Have students hypothesize a graphical model of them shaking hands with
everyone in the room.
- After all of the students have a model, allow students to actually get up and act
out the model.
- Record the results up on the board, or allow students to
develop a method to prove their initial model.
- Teacher Input
- Explain the Hand-Shaking Lemma to the students. This is what they just acted out.
- Define edge and vertex.
- Ask the students, "What will happen when more people are added?" or "When less people are present?"
- Define the term complete graph.
Guided Practice
- Split students up into small groups, and have them explore other types of graphs with the
graph applets.
- Assign each group to a specific applet or type of graph.
- Each group should understand their graph well enough to explain its characteristics to the
class.
Teacher Input
- Have students draw an example of their graph on the board and explain its characteristics.
- In our workshop we discussed circuits, wheels, bipartite, and planar graphs.
- Explain that there are other types of graphs as well, and that some graphs can represent
two types of graphs. Venn Diagrams can be introduced here if you desire.
Guided Practice
- Hand out the Different Types of Graphs worksheet.
- Assign groups of students to one of the graphs on the sheet.
- Have students decide what
makes their graph different from the other graphs on the hand-out.
Teacher Input
- Draw a chart on the board with the graph titles along the y-axis and questions along the x-axis.
- Questions -
- Can the graph type have multiple edges going to the same vertex?
- Are loops allowed?
- Is the graph
directed?
- Tell students which graph they have and allow them time to fill in the chart.
- Make the connection that these graphs can be represented by a circuit, wheel, bipartite, or planar
graph.
- Discuss real world applications of these types of graphs.
Guided Practice
- Explain the rules of
Toss n' Sort .
- With the balls, play Toss n' Sort on the big graph outlined on the floor, or ground.
- Let students play the game with different variations. More/Less people/balls. Allowing them to
add more edges or take edges away.
- Toss n' Sort - Illustrates deadlock and routing in computer networks.
Teacher Input
- Discuss what made the game easier and what elements made it harder to play.
- Talk about how the game relates to deadlock and routing in computer networks.
- Explain to the class the difference between a path and a circuit.
- Mention that a path can be of edges or vertices and the same applies to circuits.
- Define the rules for the circuit & path discovery activity.
Guided Practice
- Either with large graphs the students can walk on or smaller graphs drawn on handouts.
- Split the students up into groups and assign them to a particular graph.
- Students should find a path through all the edges, a path through all the vertices, a circuit
through all the edges, and a circuit through all the vertices.
- Graphs do not always contain each of
these four characteristics.
- Students should record their paths and circuits on a piece of paper.
Teacher Input
- Discuss the different types of graphs each student covered.
- Define Euler Path/Circuit and Hamiltonial Path/Circuit.
- Have students describe the paths and circuits they found using vocabulary words.
- Point out that not all graphs will have a Euler Path/Circuit or a Hamiltonian Path/Circuit.
- Talk about the Konigsberg Bridge Problem, and how to tell if a graph has an Euler
Path/Circuit.
- Point out that there are different ways to move between vertices and other elements such as time
or distance, which influence the popularity of each route.
- Introduce the term weighted graph.
- Independent Practice
- Direct students to the Dijkstra's Applet.
- Allow students to play with and make conjectures about how the algorithm works to find
the shortest path.
- Closure
- Discuss what the students think is Dijkstra's Algorithm.
- Define Dijkstra's Algorithm and walk through one example with the class.
- Explain that the algorithm looks for an Euler Path.
- Discuss the shortest Hamiltonian circuit problem and Traveling Sales-Being Problem with the class.
|