Understands and applies vertex-edge graphs
Vertex-edge graphs are diagrams consisting of vertices (points) and edges (line segments or arcs) connecting some of the vertices. The term "vertex-edge graph" is used to distinguish this type of graph from other graphs, such as function graphs or bar graphs. Nevertheless, sometimes vertex-edge graphs are simply called graphs, particularly in college mathematics courses. Whatever term is used, a vertex-edge graph shows relationships and connections among objects, such as in a road network or a family tree.
Students should understand, analyze, and apply vertex-edge graphs to model and solve problems related to paths, circuits, networks, and relationships among a finite number of elements, in real-world and abstract settings. The following topics related to vertex-edge graphs should be studied: Euler and Hamilton paths and circuits, the Traveling Salesperson Problem, minimum spanning trees, critical paths, shortest paths, and vertex coloring. These topics should be compared and contrasted in terms of algorithms, optimization, properties, and types of problems that can be solved. In addition, students should represent vertex-edge graphs with adjacency matrices and analyze the matrices in terms of row sums and powers.