When you read the word graph in the title, what was the first thing that came to your mind? I bet it was a pie chart a bit like this:
...or perhaps graph of a function:
...or a histogram, like this:
But, perhaps surprisingly, in this article we won't be discussing any of these “graphs”, but rather a distinctively different kind of graph. So let me first describe these amazing objects. In mathematics, a graph is a very simple structure consisting only of vertices and edges, which connect the vertices to each other. Graph theory is a field of mathematics that explores properties of these structures. More poetic names are frequently used for elementary components of graph, like "nodes" or "points" for vertices, and "arcs" or "lines" for edges.
Since graphs are so simple, you may be wondering is there also a simple way to represent them visually so that we don’t have to lose our minds pondering about abstract objects? The answer is: "of course". That’s why it’s so cool! We can very easily draw any graph...
Now when we know how to draw graphs, we may think of ways they can be used in practical means. It is clear that they can perfectly describe relations between objects of any kind. For example, if we imagine vertices represent people, then edges can tell us what are the friendships among those people (think of a social network like Facebook, Instagram or Twitter). Another model for which the graphs are used is representation of road network, with vertices as cities and adges as roads. Also graphs are used in probability theory, computer science, neural networks modelling, AI, economics, chemistry and in many other sciences:
It is always exciting to return to the source of a theory or an invention, a place where it all started from. So let us find ourselves in the Russian city of Koenigsberg in the year 1735. We are in the pleasant company of famous Swiss mathematician Leonhard Euler and we have decided to go for a walk together. This is a map of the city:
As you can see there are seven bridges in this city. Euler now asks you a very tricky question: “My friend, can we return to the starting point while crossing every bridge exactly once?” After some thinking and rambling around the city, you would have to admit that you can not find such a walk. He would then certainly have shown you why it is not possible, since he solved this problem, which turned out later to be the beginning of graph theory. Euler himself didn’t use the word graph though, but it was much later introduced by James Joseph Sylvester.
Another surprising use of graph theory is known as the map-colouring problem. Geographers and historians in the 19th Century had a hard time keeping track of the current state of the borders between the countries of the world. One method they used to make a clear demarcation between two neighbouring countries was, and indeed still is to represent them in different colours. Soon though an interesting question arose: what is the least number of colours for which it is possible to colour any map in that way. That problem turned out to be quite a bit more difficult than you would think, and it took mathematicians more than 100 years to solve. Nowadays, the famous result stated in the four color theorem by Kenneth Appel and Wolfgang Haken in 1970 is considered to be a great breakpoint in logical reasoning in mathematics, since it was the first theorem proved using computer.
Another famous example of the graph-colouring problem is the popular game "Sudoku". Both of these problems can be transformed into graph theory problems very easily under a common name vertex coloring problems.
These days, a major use of graph theory is in computer science and programming, especially in the design of algorithms for solving optimisation problems. In these kinds of problems, as the name suggests, we are required to construct the optimal - meaning cheapest or most profitable - way of doing something. For example, suppose we are going to spend our holidays in some distant resort. In order to get there, we have to travel through many cities which are connected with many roads, and every road has a cost attached to using it. We would like to minimise the cost of our travel, so that we are left with the most money to spend enjoying the holiday. This problem is modelled using "weighted" graphs, in which we assign a positive value to each edge, representing the cost (weight) of that road. It is known as the shortest path problem, since our goal is to minimize the total distance (cost in our terms) of our path, and it is very effectively solved by many algorithms, including Dijkstra’s and Bellman-Ford’s.
And for the end of this short overwiev of graph theory, we are going to consider perhaps the most interesting and challenging problems in this field. The following two problems are very easy to describe but infinitely more complicated to solve completely. The first describes a problem which every travelling salesman faces regularly, which is how to choose the shortest route between the locations he needs to visit before returning to his storehouse. It is relatively easy to find approximate solutions, but there is no algorithm which can give the exact answer in reasonable amounts of time for every graph. The reason for this surprising fact is the extremly rapid growth (even larger than exponential!) number of possible routes with every new location we add in our graph.
The travelling salesman problem (TSP) is one of the examples of NP-hard problems, which stands for “non-deterministic polynomial” algorithm complexity class. On the other hand, postmen have a very similar problem. They are supposed to visit every street in a city in order to deliver mail to every house. Their goal is to minimise the distance, or the cost, of their route. This problem is known as the Chinese postman problem, and there have been found algorithms which solve this problem in polynomial time, so this problem is considered to be solved efficiently enough.
Wrapping the story up, we have to point out the extensive use of graphs in research concerning Artificial Intelligence, which is considered to be the greatest scientific and technical field of study in near future. Even Siri and Cortana themselves use a graph called a Decision tree to make intrelligent choices...
Comments
Add a comment