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:
  • Access to a browser



Lesson Outline

  1. Focus and Review
    • Have students work on the Town of Iceberg problem as a review of graphs and an introduction to edges and vertices.
  1. Objectives
  2. Students will lean how mathematics can be used to model real world situations. Students will be exposed to algorithmic thinking and problem solving.
  1. 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.
  1. 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.
  1. 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.
  1. 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.

Main Page
Coloring Extension
Resources