A Treatise on Applied Science, Part 1: Graph Theory
On the occasion of my 10th article at Medium, I am very excited to launch a new series of articles called A treatise on Applied Science. The goal is to present different (mathematical) theoretical concepts, as well as their background — that is, why and how they were developed — and then analyze a bit on their hands-on applications in different branches.
Through these articles, I will try to showcase that these (mathematical) concepts are not just theoretical objects that bear no resemblance to reality and were just developed for the sake of satisfying some crazy mathematician’s inner joy — this is rarely the case, anyway, with mathematical discoveries, which are normally being made on the grounds of deep but otherwise pretty natural and practical questions.
Today’s first example is Graph Theory — which is probably the finest example of how a question so unrelated to mathematics led to the development of one of the most vibrant and active branches of Mathematics. But let’s take things from the beginning.
It all started back in 1726, when Leonhard Euler was invited to join the Russian Academy of Sciences, in Saint Petersburg. Euler, who was a 19-year-old aspiring scientist at the time, received an offer from the Academy, then led by his friend and compatriot mathematician and physicist Daniel Bernoulli. In the Academy, which was founded by emperor Peter the Great, Euler quickly made major scientific advancements within the Mathematics and Physics department, rendering him one of the most promising scientists in Europe at the time.
While spending his time in Russia, one of the problems that occupied this brilliant mind was that of the Seven Bridges of Königsberg. Königsberg, which is now known as Kaliningrad, was a historic city founded as early as 1255. What caught Euler’s eye, however, was that the city of Königsberg was set on both sides of the Pregel River, and included two large islands — Kneiphof and Lomse— which were connected to each other, and to the two mainland portions of the city, by seven bridges.
The problem at hand was to decide whether a walk through the city that would cross each of those bridges once and only once exists. Euler was the first one to present a solution to this problem, in 1736. Despite many efforts that were made to prove that the task is possible, Euler actually proved that it is impossible for such a route to exist. Euler’s proof led the foundations of what we today call Graph Theory.
Euler’s solution is really spectacular, not only because he introduced a new mathematical concept, but also because he challenged Aristotle’s view that mathematics is the science of quantity. Instead, Euler’s analysis showcases that the geometric positions and the rigid shapes of the bridges are completely irrelevant to solving the problem. Instead, the only information his analysis draws from the problem is regarding the relative positions of the seven bridges.
“But, what is graph theory?”, you might still ask. We will not go in formal definitions — for our purposes, it is enough to say that a graph is a collection of different vertices, some of which are connected with edges to each other. Here is an example:
As it can easily be observed, graphs are a very intuitive and simple concept, and they can greatly help in visualizing a lot of different situations. For example:
- Imagine we have a classroom of 20 children, in which each two of them either are friends or not. Now, if we would like to visualize this situation of friendships, a common way to do so is to settle a graph in which the vertices are the 20 children, and we draw an edge between two vertices if the corresponding children are friends. Now, assuming we have drawn this graph, we may elicit a lot of information from it. For example, we may find how many friends each child has, just by counting the number of edges connected to its vertex.
- Assume that we have a map of a country, consisting of several counties. Assume that we associate each county with a vertex, and draw an edge between two edges if the corresponding counties border. Then, we have transformed this map to a graph. In fact, this setting is the first step in the proof of one of the hardest theorems of Mathematics: the four color theorem!
- Assume that we are at a Youth Ball and we want to model the dancing situation. For simplicity, we will for now assume that girls only dance with boys, and vice versa. Hence, a graph as simple as in the above two examples may not work. In this case, we construct a graph consisting of two different classes of vertices. The first class is that of vertices corresponding to boys, while the second is that of vertices corresponding to girls. Here is an example:
This kind of graph, in which the members of each class are not associated to each other (indeed, no girl dances with a girl, and no boy dances with a boy), are graphs so common that they had to receive a special name: they are called bipartite graphs.
While we mentioned that graph theory was firstly introduced by Euler in 1736, this statement is quite a bit inaccurate — in reality, while Euler led the foundations of graph theory, the term graph was firstly coined by the British Mathematicians Sylvester and Cayley in 1878. And now we will see why.
The reason that Sylvester used the word graph to describe such structures, is the direct relation between mathematics and chemical structure (what he called a chemico-graphical image). For example, here is the chemical structure of the molecule of C₃H₈O (1 — propanol):
The foundations of what is now known as chemical graph theory were laid by the pioneering work of these two mathematicians. They attempted to associate each chemical structure with a corresponding graph, and thus enable themselves to describe the chemical structure of a molecule in pure mathematical terms.
More generally, we can make the following two observations:
Observation 1: Graphs can provide a very useful platform in order to interpret situations in which we want to describe the relations between some objects and a property, and the objects have a binary relation with regard to this property. This means that each two objects either have this property (and so we draw an edge), or do not (and so we do not draw an edge). For instance, we give the following examples of objects/properties that can be compiled into graphs:
- students — friendship
- counties — state of border
- chemical components — existence of chemical bond
- roads — existence of intersection between them
- family tree — existence of first-degree relation
- … and so on.
Observation 2: After describing the situation in graph-theoretic terms, we note that most times all these situations are more or less isomorphic. In this instance, this word means that after we have obtained our graph, we no longer care about:
- the initial problem’s structure
- the relative positions of the objects we studied before
- the geometric properties of the objects we studied before
- the name of the children/family members/roads/counties/chemical components
- or anything else regarding the initial situation, since we have managed to elicit all the information initially presented to us and encompass it in our new-born graph.
We must note that the procedure described at the last bullet point is not always that easy. A basic example was presented above, where we needed a special type of a graph to describe the Youth Ball situation (a bipartite graph). In other situations, however, more complex graph-theoretic structures are needed.
However, albeit complex graphs we may obtain, the greatest advantage of graph theory is that we can tackle a lot of seemingly irrelevant problems, all at once! Student Irene and Oxford Street are now deemed to be the same, as well as county Devon and chemical component H₂. They all simply correspond to vertices!
Despite being a relatively new branch of Mathematics (serious advancements on it — apart from those of Euler, Sylvester and Cayley were made after the 19th century), graph theory has evolved to be one of the most active branches of science. The main explanation of this phenomenon is the enormous number of applications it offers to virtually all sciences:
- Physics
- Computer Science
- Chemistry
- Biology
- … and even humanitarian studies! Indeed, the notion of life graph bears some connections with graph theory:
To sum up, graph theory is one of the most vibrant branches of Mathematics today, as the great importance of studying these objects — graphs — on their own has been greatly appreciated and encouraged by the way graph theory seems to offer so many interdisciplinary connections that help scientists analyze different problems better by tracing them to their associated graph structure.
