This unit is designed for Advanced Algebra students at the Secondary level particularly sophomores or juniors in high school. Discrete mathematics topics are traditionally located 'at the end of the text' and tend to be omitted, or treated lightly. The specific topics in graph theory addressed in this unit have clear practical applications. Algorithms are taught as a method, practiced through programming and then used to perform tasks in Euler and Hamiltonian circuits. Algebraic and inductive arguments for Euler's formula are also used in this unit to assist the students in making a transition from a familiar geometry topic {Euler's Formula F + V -E = 2}. The transition moves from properties of polyhedra to the projection of polyhedra onto the plane and the algorithms discovered by Euler, Hamilton and Kruskal to address procedures in traversing edges or passing through vertices of these planar graphs. The language used attempts to be concise but not at the risk of being overpowering to the subject addressed or so lofty that the student fails to see the beauty of the algorithms in practice. Definitions can be found at the end of the unit.

Contents

• Introduction to Algorithms
• Application of Simple Algorithms through TI-92 Programming
• Introduction to Script Writing using Geometer's Sketchpad
• Introduction to Planar Graphs
• An Algebraic Argument of Euler's Formula
• An Inductive Argument of Euler's Formula
• Euler Circuits and Paths
• Euler Circuit Algorithm
• Hamiltonian Paths and Circuits
• History
• Vocabulary and Definitions
• NCTM Task Force Article
• References

Related Links:

• Algorithms and Ice Cream for all
• A new proof of the four color theorem - an algothimic approach
• 15 Proofs of Euler's Formula - ThE gEoMeTrY jUnKyArD

   

  Lisa's Home Page