Michelle Homp, Alyssa Seideman, Sean Gravelle, Andrew Hayes,
Section15.1Introduction to Graph Theory
In the modern world, planning efficient routes is essential for business and industry, with applications as varied as product distribution, laying new fiber optic lines for broadband internet, and suggesting new friends within social network websites like Facebook.
This field of mathematics started nearly 300 years ago as a look into a mathematical puzzle (well look at it in a bit). The field has exploded in importance in the last century, both because of the growing complexity of business in a global economy and because of the computational power that computers have provided us.
Example15.1
Here is a portion of a housing development from Missoula, Montana. 1Image source: Sam Beebe (CC-BY) As part of her job, the development's lawn inspector has to walk down every street in the development making sure homeowners' landscaping conforms to the community requirements.
Naturally, she wants to minimize the amount of walking she has to do. Is it possible for her to walk down every street in this development without having to do any backtracking? While you might be able to answer that question just by looking at the picture for a while, it would be ideal to be able to answer the question for any picture regardless of its complexity.
To do that, we first need to simplify the picture into a form that is easier to work with. We can do that by drawing a simple line for each street. Where streets intersect, we will place a dot.
This type of simplified picture is called a graph.
Definition of a graph
In graph theory, the term graph refers to an object built from vertices and edges in the following way.
A vertex in a graph is a node, often represented with a dot or a point. (Note that the singular form is vertex and the plural form is vertices.)
The edges of a graph connect pairs of vertices. We usually represent the edges as straight or curved lines.
In graph theory, a graph is a set of vertices and edges.
Two vertices are adjacent if they are connected to each other by an edge.
We often give the vertices labels (such as letters or names). Edges can be named by listing the two vertices the edge connects. For instance, the edge AB would connect two vertices labeled A and B.
In graph theory, it is very important to keep in mind that a graph is determined only by its set of vertices and set of edges. In other words, the only information we care about is which vertices are connected to each other. For example, consider the following pair of graphs:
Figure15.2Two representations of the same graph
The two diagrams in Figure15.2 represent the exact same graph. In geometry, they are different shapes (a rectangle and a triangle). In graph theory, the geometry doesn't matter; only the connections are important. Since they both include the same four vertices connected in the same way, they represent the same graph.
Because of this, graphs are is useful when we want to model a situation for which connections are important and geometry is not. For instance, the graph from Example15.1 is shown below on the left. The diagram on the right represents the same graph, arranged in a different way. They are the same because they show the same vertices and the same edge connections, even though they are laid out differently.
It is also important to note that vertices only occur when a dot is explicitly placed on the graph (not necessarily where two edges cross). In our alternate drawing of the graph from Example15.1 (the diagram on the right-hand side above), the edges cross at many points in the middle. However, none of the crossings on the inside of the diagram represent vertices; the vertices are only the points indicated with labels around the outside of the diagram.
Imagine a freeway overpass: the freeway and side street cross, but it is not possible to change from the side street to the freeway at that point, so there is no intersection and no vertex would be placed.
Finally, you probably already noticed that we are using the term graph differently than you may have used the term in the past to describe the graph of a mathematical function. In graph theory, the term graph always refers to these types of graphs specifically.
Now that we've introduced the idea of a graph, we can discuss some of their properties.
Degree of a vertex
The degree of a vertex is the number of times it meets an edge. If a vertex is not connected to any edges, it has a degree of 0. See the diagram below for an illustration of the degrees of several vertices.
Loops
A loop is an edge that connects a vertex to itself. In the graph below, the edge shown in red is an example of a loop. Note that vertex b has degree 4: the loop meets vertex b twice, in addition to the two other edges.
Weighted edges
We can sometimes assign numbers to the edges of a graph, called weights. Not all graphs have weighted edges; this is only done when the weights describe something relevant to a problem the graph is being used for. Hence, what the weights represent will depend on the context of the problem. This could be anything; some possibilities are the distance between two locations, the travel time, or the travel cost. It is important to note that the weight of an edge does not necessarily correspond to the actual length of the edge when we draw it as a picture.
Example15.3The Bridges of Knigsberg
Back in the 18th century in the Prussian city of Knigsberg, a river ran through the city and seven bridges crossed the forks of the river. The river and the bridges are highlighted in the picture to the right. 2Image source: Bogdan Giuc
As a weekend amusement, townsfolk would see if they could find a route that would take them across every bridge once and return them to where they started.
Leonard Euler (pronounced OY-ler), one of the most prolific mathematicians ever, looked at this problem in 1735, laying the foundation for graph theory as a field in mathematics. To analyze this problem, Euler introduced edges representing the bridges:
Since the size of each land mass it is not relevant to the question of bridge crossings, each can be shrunk down to a vertex representing the location:
Notice that in this graph there are two edges connecting the north bank and island, corresponding to the two bridges in the original drawing. Depending upon the interpretation of edges and vertices appropriate to a scenario, it is entirely possible and reasonable to have more than one edge connecting two vertices.
While we haven't answered the actual question yet of whether or not there is a route which crosses every bridge once and returns to the starting location, the graph provides the foundation for exploring this question.
Paths and Circuits
A path is a sequence of distinct, adjacent edges. A path may be named by listing the vertices in the path in the order they are visited.
A circuit is a path that starts and ends at the same vertex. The start/end vertex should be listed at the start and end of the name of a circuit, so that we know it's a circuit.
The length of a path is the number of edges in the path. Since a circuit is a type of path, we define the length of a circuit the same way.
Example15.4Paths and Circuits
The following graph shows a path by highlighting the edges in red. Viewed as a path from vertex A to vertex M, we can name it ABFGHM.
Figure15.5The path ABFGHM
The path ABFGHM has length 5, since it traverses 5 edges. If we instead view it as a path from M to A, it could be named MHGFBA. Since the graph does not specify a direction the path has to be traversed, we consider ABFGHM and MHGFBA to be the same path.
The following diagram shows another path, ABFGLKJEA, on the same graph.
Figure15.6The circuit ABFGLKJEA
The path ABFGLKJEA is also a circuit, since it starts and ends at A. Notice that we wrote A at both the start and end of the name; otherwise, we would have ABFGLKJE, which is just a path from A to E.
The circuit ABFGLKJEA has length 8, since it traverses 8 edges.
Because a circuit forms a complete loop, there are many equivalent names for any given circuit. Let's identify some for the circuit ABFGLKJEA. For example, if we start at F and move counter-clockwise, we traverse the vertices in the order FBAEJKLGF. On the other hand, if we start at K and move clockwise, we obtain KJEABFGLK. These three names all refer to the same circuit. See if you can find other names for this circuit!
Connected and Disconnected Graphs
We say that a graph is connected if it's all one piece. Using paths, we can describe more exactly what we mean by this.
A graph is called connected if there is a path between each pair of vertices.
A graph that is not connected is called disconnected.
The different pieces of a disconnected graph are called components. Each component is, itself, connected, while no component is connected to another component.
A bridge in a graph is an edge whose removal would create a new component.
Exploration15.1
The graph below shows 5 cities. The weights on the edges represent the airfare for a one-way flight between the cities.
How many vertices and edges does the graph have?
Is the graph connected?
How many components does the graph have?
What is the degree of the vertex representing LA?
If you fly from Seattle to Dallas to Atlanta, is that a path? Is it a circuit? If it is a path or circuit, what is its length?
If you fly from LA to Chicago to Dallas to LA, is that a path? Is it a circuit? If it is a path or circuit, what is its length?
