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.