- Grasping Graph Theory
- Old and Famous Problems
- Graphs, Computers, and Popular Culture
- Constructing a Simple Graph with Boost
- Adding Values to Vertices and Edges
- Manipulating Property Values
- Adding Vertices and Edges
- Iterating Through the Edges and Vertices
- Solving Problems with Graphs and Boost
- Conclusion
Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Old and Famous Problems
Graphs aren’t just for representing data. They’re often used in problem solving, and, as such, play a central role in many algorithms. Over the years, mathematicians have used graphs to solve many famous problems. One of the most famous is calculating how many colors are needed to color each country on a world map, such that no two adjacent countries share the same color. (If two countries touch at a single point, that point isn’t considered a boundary.) People have long suspected that the answer is four, and thus the problem can be to prove that any map can be colored with only four colors.
This assertion has been proven in various ways. One way employs graph theory—in particular, planar graphs. Remember that a planar graph is simply a graph that can be drawn on paper (that is, in two dimensions) without any edges crossing. The vertices in the graph represent countries, and the edges represent adjacencies. Thus, if a line connects two countries in a graph, the two countries share a common border. By this representation, the assertion becomes the following: Given any planar graph, a number can be associated with each vertex, and only four numbers are needed such that no two adjacent vertices share a single number. That hypothesis can then be proven using graph theory. (I won’t go into the details here, but you can find information on the web if you’re curious. It’s called the "Four Color Theorem.")
Another famous problem that can be proven using graph theory is the "Seven Bridges" problem. The problem is based on the bridges of Konigsberg, Prussia. The problem is whether it’s possible to walk across each bridge in that city once and only once (without cheating by swimming across a river), and ultimately return to the starting point. The famous mathematician Leonhard Euler solved the problem by using graph theory. (Unfortunately, his proof shows that it’s impossible to perform the feat without jumping into one of the rivers.)
In Euler’s proof of the Seven Bridges problem, he let the vertices of a graph represent the land masses, and the edges of the graph represented the bridges. To solve the problem, Euler associated a degree with each vertex; the degree is the number of edges touching the vertex. Euler proved that in order to complete a single circuit (that is, to cross each bridge once and only once and to return to your starting point), all the nodes must have a degree that’s positive. If any nodes have an odd number of edges touching them, then the task is impossible. The seven bridges in Konigsberg were constructed such that four of the nodes have odd degrees.