Graph Theory 101

Post date: June 3, 2017

Computer science, in my eyes, is an interesting, applied discipline from which we learn about a variety of tools and models which can solve problems in other domains or in our own field. One set of these tools are what we call data structures, which are, as the name implies, ways of structuring or representing data. Another name for such structures are abstract data types (ADTs) because these structures have certain properties which are abstract in concept and it is up to the programmer to design and create structures based on these properties.

In this post, I will be talking a bit about one of the structures I use very frequently, and these are graphs (or sometimes called networks).

What Exactly Are Graphs?

A graph is a graphical (yes - pun intended) structure which is mainly used for representing the relationship between different concepts (people, entities, objects, cities, etc.). These concepts, which are often represented as circles or dots (such as in Figure 1), are known as nodes or vertices. Therefore, the set of all nodes/vertices in Figure 1 is {a, b, c, d, e, f}. As you can also see in the figure above, certain pair of nodes are connected by a line; these are called edges. The numbers by the edges describe weights which can be assigned to them, but let us disregard those for now.

These edges can be directed or undirected, which can be looked at a relationship being uni-directional or bi-directional (one-way or two-way). In some cases, certain nodes may have self-loops, where it has edges with itself.

Figure 1 - A simple example of an undirected graph.

Figure 2: A simple graph can be decomposed into a matrix representation form -- also known as an adjacency matrix.

How can we Represent them?

Now that we have covered notation, we can look at one simple yet powerful way for representing a graph - adjacency matrices (NB - plural for matrix). If you are savvy in mathematics, you would be familiar with a matrix; if you are not, a simple way of looking at a matrix is if you are making a grid that is NxN (meaning N rows and N columns). For example, look at a pair of nodes A and B and note that there is an edge between them. In the matrix, we write a 1 in the B-row and A-column and A-row and B-column. If there is no edge between a set of nodes, we write a 0. Since this is an undirected graph, the adjacency matrix produced will be symmetrical. Pretty neat huh?

The reason for talking about these matrices is because they can be used for performing very useful calculations to uncover details about the relationship described by the graph. I will perhaps touch on that in a later posting. Check out the references for a more in-depth study to the science and theory of graphs.

References:

Newman, M., Networks: an introduction. 2010. United Slates: Oxford University Press Inc., New York, pp.1-2.

Steen, M.V., 2010. Graph theory and complex networks.


Notes:

Figure 1 -

Figure 2 - Source: http://btechsmartclass.com/DS/images/Graph%20Adjacency%20Matrix%201.jpg