SOL Prep

Graph Theory

Virginia SOL DM.GT.4

Recognize and apply algorithms to solve configuration, conflict-resolution, and sorting problems.

Study DM.GT.4 with SOL PrepBack to Discrete Mathematics

What students need to be able to do

  • Recognize algorithms such as nearest neighbor, brute force, and cheapest link as they apply to graphs.
  • Use Kruskal's algorithm to determine the shortest spanning tree of a connected graph.
  • Use Prim's algorithm to determine the shortest spanning tree of a connected graph.
  • Use Dijkstra's algorithm to determine the shortest spanning tree of a connected graph.