CS202: Discrete Structures

We begin with a top-level view of graphs by looking at definitions, structure, and dynamics.

Now that you have the general idea, we proceed with the formality required to gain an intuitive idea of what graphs are and what could potentially be done with them.

Transitioning to practicality, we now learn about how data can be structured so that graphs are correctly formed for application.

Which nodes are connected, directly or indirectly? Between which nodes is there a path from one node to another? Those are the questions we deal with now. This is part of the topic of graph traversal, encountering a series of connected nodes in a graph or subgraph.

At times, we need a way to encounter every node in a graph. This page discusses how to do just that by using two important kinds of graphs.

A common thread that connects all the topics in this unit is the opportunity to optimize (maximize or minimize) some quantity that is associated with a graph. For instance, we may decide to select a path from one node to another based on the weight of the connections between those nodes. The weights refer to some aspect of the situation at hand, like distance, cost, or importance.

Annotating a graph so that it contains additional information is very important as the complexity of an application increases. Generally, the more complex the technology, the more precise needs to be its descriptive information.