Graph Theory

This category is the parent of all articles which have mention of Graphs and Graph related problems.

Fastest Reach in Snakes and Ladders

Introduction For those who are not familiar with the snakes and ladders game. Here is a link for introduction. So the fastest reach in snakes and ladders, is a modified version of the game. So, you are playing the game called snakes and ladders and you have an enchanted dice. You are the master of the dice and you can command it to get any number between 1 and 6 both inclusive. This means that when you throw the dice, the number on the upper face is totally controlled by you. If you ask for a 5, you get a 5 and so on. Problem Statement - Fastest Reach in Snakes and Ladders The problem in ha...
Read More

Single Source Shortest Path For Undirected Graph

Introduction Single source shortest path for undirected graph is basically the breadth first traversal of the graph. Here the graph we consider is unweighted and hence the shortest path would be the number of edges it takes to go from source to destination. You can find posts on the same topic for weighted graphs, and that is solved using Dijkstra's or Bellman Ford algorithms. This post is written from the competitive programming perspective. Here I want to focus on the details of simplified implementations. Problem Statement - Shortest Path for Undirected Graph Most of the times, the probl...
Read More

Hamiltonian Circuit – Seating Arrangement Problem

Here is a problem statement "Twenty members of a club meet each evening for dinner at a round table. They plan to sit such that every member has different neighbors every evening. Find out the number of days for which this arrangement can last." Here is another one "There is a list of 20 cities with roads connecting them, a salesman wants to sell his goods by visiting each city exactly once. Is that possible for a given network of cities?" Many a times we have been given problems like above and it is not really easy to solve them if we are not equipped with the Graph Theory. What ...
Read More

Euler Graphs – Origin of Graph Theory

This should have been my first post in the Graph Theory series but nevertheless I got time to discuss this now. Every one must have heard the famous problem of Seven Bridges of Königsberg. If not, then please take some time to read about the problem either on the Wikipedia or right down below: The city of Konigsberb is located on both the banks of the river Pregel(Kaliningrad, Russia - former Prussia).  The city also included two big islands and these islands were connected to each other and the main land by the means of seven bridges. Something like below: The problem is to devise a...
Read More

Graph Theory Applications – The Instant Insanity Puzzle

[nextpage title="Applications of Graph Theory"] Graph Theory is used in modelling and solving a lot of real world problems, games and puzzles. Here we discuss a very famous puzzle " The Instant Insanity " problem. The goal of this post is to demonstrate that such complicated problem statements can be so easily modeled and solved using Graph Theory. Also I would like to build some more  interest into Graph Theory. If you want to feel more comfortable with the basics of Graph Theory, here is a list of primers you might like to read once. Problem Definition - The Instant Insanity Puzzle The...
Read More