Euler actually proved that this specific problem has no solution. to a graph makes the problem tractable mathematically, as this abstract representation includes only the information important for solving the problem. This abstraction from a concrete problem concerning a city and bridges etc. A modern graph, as seen in bottom-right image, is represented by a set of points, known as vertices or nodes, connected by a set of lines known as edges. The problem was to devise a walk through the city that would cross each of those bridges once and only once.Įuler, 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. The city of Königsberg in Prussia (now Kaliningrad, Russia) was set on both sides of the Pregel River, and included two large islands - Kneiphof and Lomse - 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). His work on the famous “ Seven Bridges of Königsberg problem”, are commonly quoted as origin of graph theory. The basic idea of graphs were first introduced in the 18th century by the Swiss mathematician Leonhard Euler, one of the most eminent mathematicians of the 18th century (and of all time, really). Following this more general introduction, I will then shift focus to the warehouse optimization example discussed above. 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. Through a real-world example, I will rather try to convince you that knowing at least some basics of graph theory can prove to be very useful! (A well known problem in combinatorial optimization, important in theoretical computer science and operations research).Īs 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). 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 traveling salesman problem. More specifically, I will consider a large warehouse consisting of 1000s of different items in various locations/pickup points. In this article, I will through a concrete example show how a route planning/optimization task can be formulated and solved using graph theory. 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. 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. A graph visualization issued from the Opte Project, a tentative cartography of the Internet
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |