TEKS: Chapter 111. Mathematics See All Teacher Resources
111.46.c.2
(2) Graph theory. The student applies the concept of graphs to determine possible solutions to real-world problems. The student is expected to:
- (A) explain the concept of graphs;
- (B) use graph models for simple problems in management science;
- (C) determine the valences of the vertices of a graph;
- (D) identify Euler circuits in a graph;
- (E) solve route inspection problems by Eulerizing a graph;
- (F) determine solutions modeled by edge traversal in a graph;
- (G) compare the results of solving the traveling salesman problem (TSP) using the nearest neighbor algorithm and using a greedy algorithm;
- (H) distinguish between real-world problems modeled by Euler circuits and those modeled by Hamiltonian circuits;
- (I) distinguish between algorithms that yield optimal solutions and those that give nearly optimal solutions;
- (J) find minimum-cost spanning trees using Kruskal's algorithm;
- (K) use the critical path method to determine the earliest possible completion time for a collection of tasks; and
- (L) explain the difference between a graph and a directed graph.