Graph Theory !!

Algorithms are my first love. If Puzzles involve algorithms, they give me double the kick. Recently I came across this blog by MarkCC a Phd working at Google. This guy writes interesting blogs Math. In the past few days he blogged on Graph Theory, I was so happy to hit across his blog. The clarity and lucidity with which he explains this difficult stuff is simply amazing.

First take a look at the above picture. Now let me state the problem. This problem is supposed to be first major use of what would be graph theory.

"Back in the 18th century, Euler lived in the city of Königsberg in Prussia. Königsberg is a city built around a fork in a river: it's got parts of the city on the banks of the river, and parts on two islands. To get around the city, there were seven bridges connecting the parts of the city. Is it possible to take a trip through the city of Königsberg, crossing each bridge exactly once? More generally, given a city like Königsberg, how can you figure out whether it's possible to tour the city crossing each bridge exactly once?"

It's an interesting problem which can also be solved using Graph Theory. Mark has these posts on Graph Theory. In the first one titled "Basic Graphs" he introduces us to Graphs and the basic terminology associated.

In his next post "The First Graph Theory Problem", he discusses the problem with which I started this post.

The latest post is on Graph Coloring, he discusses maps and the problems related to coloring maps. How many colors are required to color countries on a map, such that no two countries sharing a border have the same color? Have a look at an atlas and you will see the beauty of it. In fact this was one thing I always wondered about in school days.

I am sure he has more posts up his sleeve and I promise you to update this post as and when he comes up with more. Now coming back to my interests in Graph Theory, I was first introduced to Graph Theory in my 2nd semester in college. Though it was taught in a quite boring fashion as every where else. But a latent interest gets rekindled whenever I see some practical applications.

There are many practical situations where we humans use graph theory unconsciously. Take for example finding the best route to a destination given a choice of routes. Which is the best way to send your mail (using a courier, speed post, normal post etc.). There are many such up teem number of applications where one uses Graph Theory. In fact check out my previous post on Traveling Sales Person problem where I discuss some interesting scenarios.

What do you think are more areas where Graph Theory is applied in our lives?