Overview

This is the first, of two, weeks that will focus on graphs, graph theory, and network constrained spatial analysis. As we saw previously, the method used to compute the distance between two points and the geometric shape over which that distance is computed can have significant impact on the accuracy of the final solution. We saw that the use Euclidean distance for the distance between two cities could introduce significant inaccuracy. Likewise, the true distance between two geographic elements can be inaccurate if the path of travel is not a straight line (or great circle). Geographers draw heavily from the mathematical fields of graphy theory and topology to develop methods to represent and analyze spatial interactions. The next two weeks provide an overview of these ideas and methods.

Objectives

At the conclusion of this chapter and the associated assignment, you will be able to:

• describe the elements that compose a graph;
• identify different types of graphs and compute different summary measures to describe a graph;
• describe uses of traditional graphs for spatial analysis;
• utilize different metrics of network travel distances to compute shortest paths.