Standard #: MA.912.D.2.4 (Archived Standard)


This document was generated on CPALMS - www.cpalms.org



Use spanning trees, rooted trees, binary trees, and decision trees to solve problems.


Remarks


Example 1: Suppose that you need to identify a fake coin among 8 coins by using a pan balance. The fake coin is lighter than the other seven coins that all weigh the same. What is the minimum number of weighing needed to guarantee that the fake coin is found? Make a decision tree to represent your solution. Solve the same problem by assuming that the fake coin is either lighter or heavier than the other seven coins.

Example 2: Suppose that you will have a single elimination chess tournament in your classroom. Draw the graph of this tournament until you have a single winner. What type of a tree is this? If there are n contestants in a single elimination tournament, how many matches will be played?

General Information

Subject Area: X-Mathematics (former standards - 2008)
Grade: 912
Body of Knowledge: Discrete Mathematics
Idea: Level 2: Basic Application of Skills & Concepts
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 2: Basic Application of Skills & Concepts - More Information
Date of Last Rating: 06/07
Status: State Board Approved - Archived

Related Resources

Lesson Plan

Name Description
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.

Printed On:6/15/2025 7:02:35 AM
Print Page | Close this window