MA.912.D.2.1Archived Standard

loading spinner
Export Print
Use Euler and Hamilton cycles and paths in graphs to solve routing problems.

Remarks

Example 1: There are two islands in the River Seine in Paris. The city wants to construct four bridges that connect each island to each side of the riverbank and one bridge that connects the two islands directly. The city planners want to know if it is possible to start at one point, cross all five bridges, and end up at the same point without crossing a bridge twice. Use a graph to help solve this problem. Explain your answer.

Example 2: A city planner is planning a bus route. She drew the following route, where each vertex represents a bus stop. She wants to make sure that the bus starts from the terminal, vertex a, travels all the roads exactly once and returns back to the terminal. Is this possible? If not, add additional bus stops (vertices) or roads (edges) to make it possible. What is your strategy?

Example 3: A sales person needs to travel to each city shown on the following graph. He wants to start at city a, visit each city exactly one time, and then return to the initial city (city a). Is this possible? If yes, find such a cycle for him.
General Information
Subject Area: X-Mathematics (former standards - 2008)
Grade: 912
Body of Knowledge: Discrete Mathematics
Idea: Level 3: Strategic Thinking & Complex Reasoning
Standard: Graph Theory - Understand how graphs of vertices joined by edges can model relationships and can be used to solve various problems with relation to directed graphs, weighted graphs, networks, tournaments, transportation flows, matching, and coverage.
Date Adopted or Revised: 09/07
Content Complexity Rating: Level 3: Strategic Thinking & Complex Reasoning - More Information
Date of Last Rating: 06/07
Status: State Board Approved - Archived

Related Access Points

Alternate version of this benchmark for students with significant cognitive disabilities.

Related Resources

Vetted resources educators can use to teach the concepts and skills in this benchmark.

Lesson Plan

Who Do You Know? The Theory Behind Social Networking:

This video lesson will introduce students to algorithmic thinking through the use of a popular field in graph theory—social networking. Specifically, by acting as nodes in a graph (i.e. people in a social network), the students will experientially gain an understanding of graph theory terminology and distance in a graph (i.e. number of introductions required to meet a target person). Once the idea of distance in a graph has been built, the students will discover Dijkstra's Algorithm. The lesson should take approximately 90 minutes and can be comfortably partitioned across two class sessions if necessary (see the note in the accompanying Teacher Guide). There are no special supplies needed for this class and all necessary hand-outs can be downloaded from this website.

Type: Lesson Plan

Student Resources

Vetted resources students can use to learn the concepts and skills in this benchmark.

Parent Resources

Vetted resources caregivers can use to help students learn the concepts and skills in this benchmark.