Introduction to graph theory


Biological network analysis historically originated from the tools and concepts of social network analysis and the application of graph theory to the social sciences.

Wikipedia (1) defines graph theory as:

“[…] the study of graphs, mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices, nodes, or points which are connected by edges, arcs, or lines”.

In practical terms, it is the set of abstract concepts and methods that can be used to visualise and analyse networks.


Notes The history of graph theory

Graph theory and the idea of topology was first described by the Swiss mathematician Leonard Euler as applied to the problem of the seven bridges of Königsberg. Königsberg consisted of four islands connected by seven bridges (Figure 2).  No one had ever found a path that visited all four islands and crossed each of the seven bridges only once. Naturally, people assumed that no such path existed, but there was no mathematical proof of this.

Figure 2 The seven bridges of Königsberg. Images are from Wikimedia Commons and used under Creative Commons Attribution-Share Alike 3.0 Unported license. 

Euler showed that, to solve the problem, only the relations between the land masses are relevant, not the shape or actual distances on the map. These relationships can be represented in the form of a graph where the land masses are the nodes and the bridges are the edges of the graph. Euler used this graph and its topological features to prove that the path did not exist.

Euler’s formulation of this problem provided the basis of a whole area of mathematics and it is the foundation of all the tools and concepts we will explore in this course.

You can read more about Euler’s solution to this problem on Wikipedia (2).

Let’s learn a bit more about graph theory and the main concepts we will use in this course.