44 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 (we’ll 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.
Drawing Graphs
Example 1
Here is a portion of a housing development from Missoula, Montana. 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.
Graphs, Vertices, and Edges
A graph consists of a set of dots, called vertices, and a set of edges connecting pairs of vertices.
While we drew our original graph to correspond with the picture we had, there is nothing particularly important about the layout when we analyze a graph. Both of the graphs below are equivalent to the one drawn above.
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.
Example 2
Back in the 18th century in the Prussian city of Königsberg, 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.[1]
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-lur), 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