Just for Fun: Seven Bridges of Konigsberg Problem & an Introduction to Graph Theory

Graph theory, simply put, is unlike anything I have ever learned in the classroom. The basis of graph theory is using graphs to model relations between various points/objects/nodes. Here is an example of a graph:



The coolest part about the graph above is that the numbers 1,2,3,4,5, and 6 can represent pretty much anything. The numbers can represent houses and the sidewalks linking them, they can represent cities and the highways ocnnecting them, they can represent people and the relationships between them.

Each of the numbers, or dots, is called a vertice or node. The lines connecting the vertices are called edges. Now we will examine the problem that inspired the field of graph theory: The Seven Bridges of Konigsberg.



This is a rough drawing of the seven bridges. The question that tourists always had was whether or not they could cross each bridge exactly once while starting and finishing in the same place. To solve this problem, Euler drew a simplified graph of only vertices and edges. He then ended up with a graph like this.



Instead of each vertice representing a person, each vertices represents a landmass and each edge represents a bridge connecting two landmasses. If you count the number of bridges (edges) going to each vertice, you will notice that they all have odd numbers. 5, 3, 3, and 3. The problem of starting and ending at the same place and crossing each edge only once is referred to as a Eulerian circuit problem. A Eulerian circuit only exists if the graph is connected (meaning no isolated vertices), and all the vertices are of an even degree. The degree of vertices in this problem are all odd, making this a non Eulerian circuit, or an impossible problem for the tourist.

While this in itself is an interesting problem, there are ways to "Eulerize" a graph to make an Eulerian circuit. I will leave this challenge up to you. How can you make this graph an Eulerian circuit given the definition of a Eulerian circuit? I will post a hint in the comments.

Other interesting graph theory applications/problems include:
The Chinese Postman Problem-(http://en.wikipedia.org/wiki/Route_inspection_problem)
Nearest Neighbor Algorith, used in the "Which way do I travel to college" posters found in math classrooms at Sidwell-(http://en.wikipedia.org/wiki/Nearest_neighbour_algorithm)