Leadership Program:

During the summer institute, program participants learn about discrete mathematics and review and prepare materials that they can use to introduce these topics in their classes. The following web sites will help teachers to explore the topics farther.

Day 1 - Coloring Maps and Resolving Conflicts

Day 2 - Drawing Graphs with One Line

Day 3 - Hamilton Circuits and the Traveling Salesperson Problem

Day 4 - Making the Right Connections

Day 5 - What's the Shortest Route?

Day 1 - Coloring Maps and Resolving Conflicts

• The Most Colorful Math of All - MegaMath
  Coloring is a profound mathematical topic with multi-million-dollar industrial applications. The problem presented here has been of interest to mathematicians for over a hundred years. How many colors do you need? With a few crayons or markers and some hand-drawn maps, children can quickly find themselves grappling with some of the same conundrums that contemporary mathematicians do. Four-color map problem, Activities, Background Information, From the MegaMath Test and Development Site.
• Colorful Mathematics - Canada's SchoolNet
  An educational software series presenting advanced mathematical concepts to K-12 students in a game-oriented approach. The five games offered use simple coloring and/or drawing techniques to illustrate mathematical concepts from graph theory. Downloadable software and a "teacher's corner" are provided. From Canada's SchoolNet. Games: The Four Color Map Problem; the Chromatic Number of a Graph; the Edge Chromatic Number of a Graph; the Two-Player Chromatic Game; the Dominating Number of a Graph. Available for IBM compatibles only. Version in French. You need the WinZip utility to unzip the files. A free trial version is avaiable at http://www.winzip.com/.
• Graph Theory Tutorials - Chris K. Caldwell
  A series of short interactive tutorials introducing the basic concepts of graph theory, designed with the needs of future high school teachers in mind and currently being used in math courses at the University of Tennessee at Martin. An Introduction to Graph Theory tutorial uses three motivating problems to introduce the definition of graph along with terms like vertex, arc, degree, and planar. Includes a glossary and a partially annotated bibliography of graph theory terms and resources. Euler Circuits and Paths; Coloring Problems (Maps).
• Perry-Castañeda Library Map Collection - The University of Texas
  A large collection of maps stored as JPEG and GIF images which can be printed for classroom use. Since the maps scanned by the General Libraries are in the public domain, no permissions are needed to copy them. You may download them and use them as you wish giving the site credit.
• Figure This Math Challenge - National Council of Teachers of Mathematics
  The four-color theorem presented in a “problem-of-the-week” format. Further examples and discussion can be found by going to “Try these”, “Think about this”, or “Did you know?”

Day 2 - Drawing Graphs with One Line

• Graph Theory Tutorials - Chris K. Caldwell
  A series of short interactive tutorials introducing the basic concepts of graph theory, designed with the needs of future high school teachers in mind and currently being used in math courses at the University of Tennessee at Martin. An Introduction to Graph Theory tutorial uses three motivating problems to introduce the definition of graph along with terms like vertex, arc, degree, and planar. Includes a glossary and a partially annotated bibliography of graph theory terms and resources. Euler Circuits and Paths; Coloring Problems (Maps).
• Leonhard Euler (1707-1783) - Alexander Litvak and Alina Litvak
  A brief history of the life of Leonhard Euler from Pacific Institute for the Mathematical Sciences High School Mathematics Magazine Pi in the Sky March 2003 issue.
• Games on Graphs - Mega Math
  From MegaMathematics: View a story involving graph theory and try to solve an unsolved problem. Several games as well. Students use algebraic methods to explore, model, and describe patterns and functions involving numbers, shapes, data, and graphs in problem-solving situations and communicate the reasoning used in solving these problems. Big Ideas and Key Concepts include pages on Graphs; Properties of mathematical objects; Modeling; and Abstraction. See also The Painter of Lines in the Street.
• The Bridges of Königsberg - Department of Mathematics Iowa State University
  Concise presentation of the Königsberg Bridge Problem and several related puzzles
• The Beginnings of Topology - The Math Forum at Drexel University
  A kid-friendly introduction to Euler and Königsberg Bridge Problem.
• Euler Curcuits - Center for Teaching and Learning, The University of Alabama
  Very clear explanation of Euler Paths and Circuits, with examples. Includes historical context and terminology section.
• Finding Euler Curcuits - David J. Wright, Oklahoma State Mathematics
  Interactive Java applet for drawing vertices, edges, and Euler Circuits (if they exist).
• Network Graphs - Mathematics for Elementary Teachers, MacGraw Hill
  Over 25 practice problems related to map coloring and Euler Circuits, with well-written explanatory text and answers provided. Excerpts are from the text book Mathematics for Elementary Teachers: A Conceptual Approach, Bennett and Nelson, Fifth Edition, MacGraw Hill/
• Numb3rs Activity: The Königsberg Bridge Problem - Numb3rs
  An Eulerian lesson plan (with worksheets), related to the TV hit Numb3rs!
• Euler's Königsberg Bridge Problem - Contra Costa College, San Pablo, CA
  Practice with Euler and doorways.
• Mathematization: A Walk in the Park - Susan K. Eddins, Illinois Mathematics and Science Academy
  There is a park, Jardin de la Ville Amélia, in Barcelona, Spain, where most mornings the older men of the neighborhood meet to walk and visit. The challenge presented to you is to use the drawing of the Jardin de la Ville Amélia to mathematize the situation and to determine whether Dr. Perez-Pardo could walk along every path in the park exactly one time during his morning stroll.

Day 3 - Hamilton Circuits and the Traveling Salesperson Problem

• Powers of Ten - Matthew J. Parry-Hill, Christopher A. Burdett and Michael W. Davidson
  View the Milky Way at 10 million light years from the Earth. Then move through space towards the Earth in successive orders of magnitude until you reach a tall oak tree just outside the buildings of the National High Magnetic Field Laboratory in Tallahassee, Florida. After that, begin to move from the actual size of a leaf into a microscopic world that reveals leaf cell walls, the cell nucleus, chromatin, DNA, and finally, into the subatomic universe of electrons and protons. Matthew J. Parry-Hill , Christopher A. Burdett and Michael W. Davidson - National High Magnetic Field Laboratory, The Florida State University, Tallahassee, Florida.
• Sir William Rowan Hamilton (1805 - 1865) - Cheryl Haefner and Robert H. Orr, Indiana University Purdue University Indianapolis
  Short bibliography of Sir William Rowan Hamilton including his accomplishments in quaternions and graph theory.
• Games on Graphs - Mega Math
  From MegaMathematics: View a story involving graph theory and try to solve an unsolved problem. Several games as well. Students use algebraic methods to explore, model, and describe patterns and functions involving numbers, shapes, data, and graphs in problem-solving situations and communicate the reasoning used in solving these problems. Big Ideas and Key Concepts include pages on Graphs; Properties of mathematical objects; Modeling; and Abstraction. See also The Mail Carrier's Tour.
• The Traveling Monkey - Ivars Peterson
  One of the classic problems of planning ahead concerns a traveling salesman who must visit customers in a number of cities scattered across the country and then return home. The problem is to find the shortest possible route visiting each city only once. It turns out that vervet monkeys can also solve the traveling salesman problem -- albeit to a limited extent. In the May 29, 1997 edition of Nature, Audrey E. Cramer and C.R. Gallistel of the University of California at Los Angeles report that, rather than always heading for the nearest foodsupply, the monkeys apparently plan their next three visits to minimize distance and travel time.
• The Shoelace Problem - Ivars Peterson
  How should shoes be laced? This seemingly simple question, rooted in everyday life, can provoke passionate argument - and evoke a mathematical response. There are at least three common ways to lace shoes, as illustrated: American (or standard) zigzag, European straight, and quick-action shoe store. Which lacing style a person uses depends on a variety of factors, ranging from aesthetic appeal to tying efficiency. The shoelace question represents a special, restricted instance of the classic traveling salesman problem.
• Travelling Salesman's Problem
  Algorithms to solve the travelling salesman's problem (a travelling salesman is to visit a number of cities; how to plan the trip so every city is visited once and just once and the whole trip is as short as possible?) Links to Java applets; the shell principle.
• Solving Traveling Salesman Problems - Vašek Chvátal and William Cook
  The traveling salesman problem, or TSP for short, is this: given a finite number of "cities" along with the cost of travel between each pair of them, find the cheapest way of visiting all the cities and returning to your starting point. In these pages view reports on ongoing projects to solve large-scale instances of the TSP.

Day 4 - Making the Right Connections

• The Ice Cream Stands Problem - Mega Math
  Where shall we locate ice cream stands in our town so that no one has to travel too far to buy a treat? The problem-solving strategies for this problem apply to many other situations that require planning for facilities. Students will have a chance to grapple with the notion of proof and decide what makes a solution satisfactory. They are also exposed to an important unsolved problem in mathematics.
• Soap Films and Grid Walks - Ivars Peterson
  A simple, physical demonstration of a mathematical truth can produce a lasting impression - one that inspires new questions and speculations. For Christopher C. Chang, a student at Henry M. Gunn Senior High School in Palo Alto, Calif., and one of 40 finalists in this year's Westinghouse Science Talent Search, that demonstration involved soap films and a classic problem invented nearly two centuries ago by Jakob Steiner, a professor at the University of Berlin. When Chang started to work on the Steiner problem, instead of finding Steiner points on a plane in which roads can go in any direction, he looked for them on a grid, meaning that the roads can go only in certain directions. This put the problem into the realm of discrete geometry.
• Minimum Spanning Trees - University of Saskatchewan Department of Computer Science
  A nice explanation of Minimum Spanning Trees and two of the most widely used algorithms (Kruskal's and Prim's) for finding them.

Day 5 - What's the Shortest Route?

• Plan the Best Route for a Shopping Trip - Math Forum PoW
  A shortest route problem from the Middle School Problem of the Week Archive.
• Pascal Web Unit - Math Forum
  A Web unit designed to support workshops given by the Math Forum for the Urban Systemic Initiative (Philadephia and San Diego). Read about the history of Pascal's triangle and learn to construct it; view illustrations of number patterns to be discovered; carry out interactive investigations in Java script or the Geometer's Sketchpad, and explore this famous triangle through lesson plans that feature questions, answers, discussion, and student worksheets.
• Oh, which way do I go? - Figure This - Math Challenges for Families!
  Several practice problems involving shortest paths on grid graphs.
• The Subway Navigator - Paris Transportation Authority
  Use the Subway Navigator to create original “best path” or “traveling tourist” problems in major cities all over the world! Create your own reasonable “weighting” (time) from one subway stop to the next and also build in extra time for transfers from one subway line to another. A terrific website for anyone planning to travel and make use of public transportation.
• Graph Theory Glossary - Chris Caldwell, University of Tennessee at Martin
  Detailed glossary that reviews most of graph theory vocabulary discussed in Week One.

DIMACS || Leadership Program || LP Web Pages || The Math Forum

Created by Judy Ann Brown, Brian Rollfinke, and Gail Holmes
Last Update: April 21, 2008