Graph Theory has a special influence in our daily lives. Unbeknown to most people, many aspects of our day-to-day life are modelled by graphs: the GPS we use every day, our Facebook friend suggestions, and even the web and the operating systems we use.
How can a concept that looks so simple - models describing relations between objects - become so powerful?
We are going to try and present some of the reasons behind this and explain some very interesting properties and facts about Graph Theory during a new entry in The Magic of Computing series - "Why is Graph Theory so amazing?"
A little bit of history
The idea of a graph was firstly introduced by a very influential Swiss mathematician by the name of Leonhard Euler. During the first half of the 18th century, Euler made attempts to solve the famous Königsberg bridge problem (the city is in Russia and is now called Kalinigrad), eventually suceeding in 1735.
(image courtesy of Encyclopedia Britannica, Inc)
In the photo above we can see a visual representation of how the bridges the problem speaks about were set. The question was whether a citizen could cross the bridges in such a way that each bridges was crossed exactly once. Nowadays, this kind of traversal is called an Eulerian path.
Euler demonstrated that such a path cannot be achieved in this setting. He firstly supposed that a path existed. When attempting a traversal, each time a citizen encounters a landmass, apart from the start and finish encounters, two bridges should be accounted for - the one on which the citizen just passed, and another one to take him to another landmass, so the number of bridges on each landmass should be an even number. However, the picture shows that there are no landmasses with an even number of bridges. Therefore, such a traversal is impossible in the current setting.
Although Euler was one of the first to unknowingly experience with what was to become graph theory, graphs were only formally defined after 1870. In the formal definition, a graph is described by two sets. One set, called V, containing vertices (or nodes), and E, a set edges - pairs of vertices which can be unordered (resulting in an undirected graph), or ordered (resulting in a directed graph).
Graphs in the modern context
Graph theory became exponentially more useful with the release of consumer computers. The concept is simple enough to easily represent in code and memory, and people even came up with various methods that aim to optimise how graphs are handled. Although the other entries in the series contain C++ snippets, handling graphs in C++ needs more code and I think it would make the article harder to read.
Let G be a graph with N nodes and E edges. Below, we will showcase two different methods to create a Python class to handle this graph, using two different forms of graph representation. Both representations will be of undirected graphs.
Adjacency matrix
A handy mode to represent G is by using a square boolean matrix of size N * N. Let this matrix be called A. Then, A[i][j] will be true if there is an edge between nodes i and j and false otherwise. In an undirected graph, matrix A is symmetric, as the edge from i to j is bidirectional, so A[i][j] = A[i][j] for any i and j.
One advantage of this is that determining whether an edge (i, j) is in the graph can be done in constant time. However, if we aim for example to store a graph with a lot of nodes and a relatively small number of edge, this method might prove inefficient from a memory standpoint (this graphs are also called sparse graphs). That leads us to another popular method of representing graphs.
Adjacency lists
This method aims to represent a graph by using N lists, enumerating the neighbours of each node.
While when using this method, checking whether a given edge exists is not constant (having an O(E) worst case), looping through all the neighbours of a node is much time-efficient in sparse graphs, and there are also other benefits which we will see in future articles.
Other methods
Alternatively, graphs can also be represented by using a list of edges or a so-called incidence matrix.
The incidence matrix is a boolean E * N matrix, with one line for each edge. The columns representing the two extremities of the edge are marked with 1 on its corresponding line.
All methods have their own advantages and disadvantages as we shall see in other articles.
In the next article, we will delve deeper into graph theory, showing some interesting graph-related algorithms and their applications. Until then, be sure to check out other articles in The Magic of Computing!
Top comments (0)