{"id":9445,"date":"2020-08-26T07:22:05","date_gmt":"2020-08-26T07:22:05","guid":{"rendered":"https:\/\/www.experfy.com\/blog\/?p=9445"},"modified":"2023-11-15T15:13:46","modified_gmt":"2023-11-15T15:13:46","slug":"what-is-graph-theory-and-why-should-you-care","status":"publish","type":"post","link":"https:\/\/www.experfy.com\/blog\/bigdata-cloud\/what-is-graph-theory-and-why-should-you-care\/","title":{"rendered":"What is Graph Theory, and why should you care?"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\n

From graph theory to path optimization<\/strong><\/p>\n\n\n\n

Graph theory might sound like an intimidating and abstract topic to you, so why should you even spend your time reading an article about it? However, although it might not sound very applicable, there are actually an abundance of useful and important applications of graph theory! In this article, I will try to explain briefly what some of these applications are. In doing so, I will do my best to convince you that having at least some basic knowledge of this topic can be useful in solving some interesting problems you might come across.<\/p>\n\n\n\n

In this article, I will through a concrete example show how a route planning\/optimization task can be formulated and solved using graph theory. More specifically, I will consider a large warehouse consisting of 1000s of different items in various locations\/pickup points. The challenge here is, given a list of items, which path should you follow through the warehouse to pickup all items, but at the same time minimize the total distance traveled? For those of you familiar with these kind of problems, this has quite some resemblance to the famous\u00a0traveling salesman problem<\/a>. (A well known problem in\u00a0combinatorial optimization<\/a>, important in\u00a0theoretical computer science<\/a>\u00a0and\u00a0operations research<\/a>).<\/p>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\n

As you might have realized, the goal of this article is not to give a comprehensive introduction to graph theory (which would be quite a tremendous task). Through a real-world example, I will rather try to convince you that knowing at least some\u00a0basics<\/em>\u00a0of graph theory can prove to be very useful!<\/p>\n\n\n\n

I will start with a brief historical introduction to the field of graph theory, and highlight the importance and the wide range of useful applications in many vastly different fields. Following this more general introduction, I will then shift focus to the warehouse optimization example discussed above.<\/p>\n\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t

\n

The history of Graph Theory<\/h1>\n<\/h1>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

The basic idea of graphs were first introduced in the 18th century by the Swiss mathematician\u00a0Leonhard Euler<\/a>, one of the most eminent mathematicians of the 18th century (and of all time, really). His work on the famous \u201cSeven Bridges of K\u00f6nigsberg problem<\/a>\u201d, are commonly quoted as origin of\u00a0graph theory<\/a>.<\/p>\n\n\n\n

The city of K\u00f6nigsberg in Prussia (now Kaliningrad, Russia) was set on both sides of the Pregel River, and included two large islands \u2014 Kneiphof and Lomse \u2014 which were connected to each other, or to the two mainland portions of the city, by seven bridges (as illustrated in the below figure to the left). The problem was to devise a walk through the city that would cross each of those bridges once and only once.<\/p>\n\n\n\n

Euler, recognizing that the relevant constraints were the four bodies of land & the seven bridges, drew out the first known visual representation of a modern graph. A modern graph, as seen in bottom-right image, is represented by a set of points, known as\u00a0v<\/strong>ertices or nodes, connected by a set of lines known as edges.<\/p>\n\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\n\n

This abstraction from a concrete problem concerning a city and bridges etc. to a graph makes the problem tractable mathematically, as this abstract representation includes only the information important for solving the problem. Euler actually proved that this specific problem has no solution. However, the difficulty he faced was the\u00a0development of a suitable technique of analysis<\/a>, and of subsequent tests that established this assertion with mathematical rigor. From there, the branch of math known as graph theory lay dormant for decades. In modern times, however, it\u2019s applications are finally exploding.<\/p>\n\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t

\n

Introduction to Graph Theory<\/h1>\n<\/h1>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

As mentioned previously, I do not aim to give a comprehensive introduction to graph theory. The following section still contains some of the basics when it comes to different kind of graphs etc., which is of relevance to the example we will discuss later on path optimization.<\/p>\n\n\n\n

Graph Theory<\/em>\u00a0is ultimately the study of\u00a0relationships<\/strong>. Given a set of nodes & connections, which can abstract anything from city layouts to computer data, graph theory provides a helpful tool to quantify & simplify the many moving parts of dynamic systems. Studying graphs through a framework provides answers to many arrangement, networking, optimization, matching and operational problems.<\/p>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\n

Graphs can be used to model many types of relations and processes in physical, biological, social and information systems, and has a wide range of useful applications such as e.g.<\/p>\n\n\n\n

    \n
  1. Finding communities in networks, such as social media (friend\/connection recommendations), or in the recent days for possible spread of COVID19 in the community through contacts.<\/li>\n
  2. Ranking\/ordering hyperlinks in search engines.<\/li>\n
  3. GPS\/Google maps to find the shortest path home.<\/li>\n
  4. Study of molecules and atoms in chemistry.<\/li>\n
  5. DNA sequencing<\/li>\n
  6. Computer network security<\/li>\n
  7. \u2026.. and many more\u2026.<\/li>\n<\/ol>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t

    As mentioned, there are several types of graphs that describe different kind of problems (and the constraints within them). A nice walk-through of various types of graphs can also be found in a\u00a0previous article<\/a>\u00a0by\u00a0Kelvin Jose,<\/a>\u00a0and the below section represents a subset of that article.<\/p>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

    \n\t\t\t\t
    \n\t\t\t\t\t

    \n

    Types of Graphs<\/em><\/h2>\n<\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t\t
    \n\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t

    There are different types of graph representations available and we have to make sure that we understand the kind of graph we are working with when programmatically solving a problem which includes graphs.<\/em><\/p>\n\n\n\n