Graph theory in computer science
Graph theory sounds like some complex math, well it actually is mathematical data structure. Graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. It involves the study of properties and applications of the graph. This is a huge field in math & computer science.
In graph theory, graphs are not like where you have to plot some data on X-axis and Y-axis. It is more like what you see in the above figure. These graphs have a bunch of nodes (colored dots in the above picture ) and edges (lines that connect those dots). The main purpose is to go from one node to another using the minimum lines, finding the shortest possible distance. These graphs have endless applications in both math and computer science. For this article, I will only focus on computer science.
Many algorithms in computer science are based on graph theory, cars navigation system finds the best route using this or to retrieve data faster from a database, etc.
let's start with a puzzle
There is more than one way to solve this problem. This kind of problem is known as the Euler tour, where you start and finish at the same point without using the same line twice. When we are solving this kind of puzzles our first instinct would be to draw a route from one point to another. That would be the right choice to do but let's just imagine there are more than 100 nodes. As the number of nodes keeps getting bigger this kind of problems keeps getting harder and harder. We can make our lives much easier by first finding out if the Euler tour is possible or not!
The Euler route is only possible if every node has an even number of edges. just imagine how much computing time and processing effort we can save just by using this method while finding a route.
let's try to solve a puzzle using this method.
Think about it for a minute, look at all the nodes. And if any node has an odd number of a degree then it's not possible.
If you already thinking that it's not possible then you are on the right track, since there are odd number of edges on 4 nodes. The Euler route doesn't exist.
Hamiltonian path problem
Here’s an awesome explanation for hamiltonian path problem
