Using graphs, trees, and networks

Graphs and the other similar structures we introduced in the previous section are versatile modeling tools. This section will be an overview of some of the most common areas where these structures are used in discrete mathematics. Note that some of these topics will be explored much more deeply in some forthcoming chapters.

In Chapter 9, Searching Data Structures and Finding Shortest Paths, we will learn how to search graphs (especially trees) to find certain features or characteristics. One application of these searches is in scheduling problems. For example, consider a directed graph where each vertex represents a task that needs to be done to complete a large project where a directed edge between task A and task B means task A must be completed before task B. In other words, the directed edge represents a dependency.

Clearly, there should be no cycles since that would lead to an infinite loop of tasks to complete! This means the directed graph...