Unpacked Content
Knowledge
Students know:
- How to make systematic lists to solve problems.
Skills
Students are able to:
- Create a graph that models a given situation.
- Apply an algorithm to find a Hamilton or Euler circuit or path in a graph.
Understanding
Students understand that:
- Graphs can be used to model real-world problems and Hamilton and Euler circuits and paths can provide solutions to such problems.
- An Euler circuit cannot exist in a graph with any odd degree vertices.
- An Euler path cannot exist in a graph without exactly two odd degree vertices.
- No known good algorithm has been established for finding a Hamilton path or circuit since no necessary and sufficient conditions for the existence of a Hamilton path or circuit have been identified.
- The graph must be connected in order for a Hamilton or Euler path or circuit to exist.
Vocabulary
- Degree of a vertex
- Graph
- Bipartite graph
- Grid (a type of bipartite graph)
- Vertex
- Edge
- Circuit (Euler, Hamilton)
- Path (Euler, Hamilton)
- Algorithm
