- Recognize graph components: vertices, edges, loops, and vertex degrees
- Identify both a path and a circuit through a graph
- Determine whether a graph is connected or disconnected
- Find the shortest path through a graph using Dijkstra’s Algorithm
Analyzing Geographical Maps with Graphs
When graphs are used to model and analyze real-world applications, the number of edges that meet at a particular vertex is important. For example, a graph may represent the direct flight connections for a particular airport as in the figure below. Representing the connections with a graph rather than a map shifts the focus away from the relative positions and toward which airports are connected. In the figure below, the vertices are the airports, and the edges are the direct flight paths. The number of flight connections between a particular airport and other South Florida airports is the number of edges meeting at a particular vertex. For example, Key West has direct flights to three of the five airports on the graph. In graph theory terms, we would say that vertex [latex]FYW[/latex] has degree [latex]3[/latex]. The degree of a vertex is the number of edges that connect to that vertex.
Graphs are also used to analyze regional boundaries. The states of Utah, Colorado, Arizona, and New Mexico all meet at a single point known as the “Four Corners,” which is shown in the map in below.
Map of the Four Corners
In the figure below, each vertex represents one of these states, and each edge represents a shared border. States like Utah and New Mexico that meet at only a single point are not considered to have a shared border. By representing this map as a graph, where the connections are shared borders, we shift our perspective from physical attributes such as shape, size and distance, toward the existence of the relationship of having a shared boundary.