Student Learning Map

  • Topic:Graph Theory
  • Subject(s):Math
  • Days:10
  • Grade(s):10, 11, 12
Key Learning:

Nontraditional/Discrete Graph Theory allows for unique problem-solving strategies.
Unit Essential Question(s):
 
 

How are simple graphs, multigraphs, planar graphs, and digraphs distinguished?

How is it determined if graphs contain walks, paths, trails, circuits, and/or cycles?
   
Concept: Graphs
LA.1112.1.6.1   LA.1112.1.6.2   LA.1112.1.6.5   MA.912.G.8.2   MA.912.G.8.3   MA.912.G.8.4  
Concept: Walks and Paths
MA.912.G.8.2   MA.912.G.8.3   MA.912.G.8.4  
Concept: Euler Paths and Circuits
MA.912.G.8.2   MA.912.G.8.3   MA.912.G.8.4  
Lesson Essential Question(s):

What is the difference between a multigraph and a simple graph?

 (A)

How is it determined if a graph is complete?

 (A)

Lesson Essential Question(s):

What are the distinctions between walks, trails, paths, circuits, and cycles?

 (A)

How is it determined whether a graph is connected?

 (A)

Lesson Essential Question(s):

What is the difference between Euler\'s circuit and path?

 (A)

What does Fleury\'s Algorithm help to determine?

 (A)

Vocabulary:

simple graph, multigraph, parallel edges, loops, incident, isolated, degree, complete graph

Vocabulary:

walk, trail, path, circuit, cycle, connected, disconnected, bridge

Vocabulary:

Euler circuit, Euler Path Algorithm, Fluery's Algorithm

Concept: Shortest Paths and Minimal Distance
MA.912.G.8.2   MA.912.G.8.3   MA.912.G.8.4  
Concept: Trees
MA.912.G.8.2   MA.912.G.8.3   MA.912.G.8.4  
Concept: Graphs and Matrices
MA.912.G.8.2   MA.912.G.8.3   MA.912.G.8.4  
Lesson Essential Question(s):

What are the differences in the two methods for finding the shortest path?

 (A)

Lesson Essential Question(s):

What is a spanning tree?

 (A)

How is minimal spanning tree found using Kruskal\'s Algorithm?

 (A)

Lesson Essential Question(s):

How can digraphs be used to solve real-world application problems?

 (ET)

How can a digraph be converted to a matrix?

 (A)

Vocabulary:

weighted multigraphs, bredth-first search algorithm, weight of a path, minimal path, minimal distance, Dijkstra's Algorithm

Vocabulary:

tree, subgraph, spanning tree, minimal spanning tree, Kruskal's Algorithm

Vocabulary:

directed graph, digraph, indegree, outdegree, reachable, directed path, critical path, adjacency matrix

Additional Info:

Resources:

View As PDF
Student Learning Map of Unit
Vocabulary Report

Culminating Activities:

1. Untitled Culminating Activity

Student Assessment(s):

1. Untitled Student Assessment

Vocabulary Report

  • simple graph -
  • directed graph -
  • tree -
  • weighted multigraphs -
  • Euler circuit -
  • walk -
  • bredth-first search algorithm -
  • Euler Path Algorithm -
  • subgraph -
  • trail -
  • digraph -
  • multigraph -
  • path -
  • Fluery's Algorithm -
  • weight of a path -
  • indegree -
  • parallel edges -
  • spanning tree -
  • minimal spanning tree -
  • outdegree -
  • loops -
  • circuit -
  • minimal path -
  • minimal distance -
  • Kruskal's Algorithm -
  • incident -
  • cycle -
  • reachable -
  • directed path -
  • Dijkstra's Algorithm -
  • isolated -
  • connected -
  • critical path -
  • degree -
  • disconnected -
  • bridge -
  • complete graph -
  • adjacency matrix -