Graph Theoretic Algorithm

Image source: Merian-Erben
Image source: Merian-Erben

What is graph theory?

Graph theory is the study of object relationships. These objects, like the landmasses above, can be represented as dots, and their relationships as lines (like the bridges). The dots are referred to as vertices or nodes, and the lines are referred to as edges or links. A graph is the connection of all the vertices and edges and can be represented as an image, such as the ones below:

What are real life applications of graph theory?

With examples from real-world situations, I present four different graph theory problems in this section. Since they can occasionally become too complex for this introductory blog, I encourage the reader to look up the various algorithms that can be used to calculate their solution. Furthermore, the answers to such problems might not be original or precise. Due to the dependence of graph theory algorithms on the size and complexity of the graph, some solutions may only be very close approximations of the true solution. Approximations are the best solution because some problems haven’t even been solved.

Airline Scheduling (Flow problems)

The field of flow problems, which includes practical situations like airline scheduling, includes one of the most well-known applications of graph theory. Every flight an airline operates needs an operating crew to take off and land safely. Not every flight has access to every member of the staff because they may be stationed in a specific city. Graph theory is used to schedule the flight crews.

Crew planning and scheduling

Directions in a map (Shortest path)

These days, we constantly use our smartphones to assist us in our daily activities. It benefits me personally by providing cycling directions from my location to a restaurant or bar. But how are these calculations done? This problem, which belongs to the category of defining the shortest path, has an answer in graph theory.

Google Maps

Search Engine Algorithms (PageRank algorithm)

We can easily navigate the World Wide Web thanks to search engines like Google. The search engine looks for websites that match the query after receiving a query to look up a specific set of words. How does the engine rank the millions of matches it has found so that the most popular ones are displayed first?

Social Media Marketing (Community detection)

Facebook had 2.9 billion active users in January 2022. As a social media platform, advertising generates the majority of the platform’s income. With so many users, it will be very expensive for advertisers to place their advertising campaigns in places where everyone can see them. Targeting only those who might be interested in your product is another option. How do you describe a target audience like that?

Conclusion

In this blog, we discussed how a straightforward mathematical puzzle gave rise to graph theory. You now understand the fundamental elements of the subject as well as the primary issues that graph theory can be used to address. As an introduction to the subject, this blog’s primary objective is to persuade readers to approach problems in the same way that graph theory does by abstracting them and leaving behind any irrelevant details. Finding a solution will be much simpler as a result.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store