Graph theory in computer science

Hamza Javed
Jul 16 · 3 min read

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.

https://qph.fs.quoracdn.net/main-qimg-e4556217e1d0ecb4d3f62a5eaee4c773.webp

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.

https://www.youtube.com/watch?v=eSFA1Fp8jcU

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

Hamza Javed

Written by

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade