Networks are a fundamental component of Computer Science, in fact the internet itself is an interconnected network of servers (i.e, a network). The study of networks is therefore of utmost importance, as it is a foundation of the internet. Graph theory is an important tool which enables networks to be modelled mathematically. This is a basic introduction to some simple concepts in graph theory.

What is a graph?

A graph is simply (as discussed) a mathematical model. In the context of networking, a graph is used to model how a network is structured and to some extent show its behaviours. Below is a simple graph.

simple graph

To introduce some terminology, this graph has four edges and four verticies (also can be referred to as nodes); edges are the lines and nodes are the circles. That's it. However there are different variations of graphs.

Types of graphs

  • Simple graph
  • Multi-graph
  • Undirected graph
  • Directed graph

Simple graph

A simple graph, is one that is unweighted (it does not have weight values assigned to nodes), does not contain any loops (edges which connect a node to itself), does not have multiple edges (two edges which connect to the same node) and is undirected. As the name suggests, a simple graph is...simple. It just has nodes which connect to other nodes.

simple graph

Simple graph

Multi-graph

A multi-graph is simply a graph which has two edges that connect to the same node, as shown in the example graph below. This can represent two different communication channels that two servers have, in contrast to a simple graph which would only denote one channel.

multi-graph

Multi-graph

Undirected graph

Both of the example graphs shown thus far, are undirected graphs. This is quite a simple concept, it means that the edge is not moving in one direction (this concept will make sense once a directed graph is shown).

Directed graph

A directed graph is one in which all edges in the graph are directed in one-direction in contrast to going both directions in an undirected graph. This can be seen in the example below.

directed graph

Directed graph

Trees

The main property of a tree is that if a node is removed, then it becomes a disconnected graph. This is because each node has only one edge connecting to another node, therefore if a node is removed then the graph becomes disconnected. Furthermore, trees are graphs and can also be derived from a graph (a graph contains trees, potentially several trees can be derived from one graph). The second property of a tree is that it has no loops (there are no edges in a tree that connect a node to itself).

graph tree example

Tree

Adjacency matrix

An adjacency matrix is a formal way of depicting a graph. It shows the relationship of nodes within a graph in the form of a matrix; below is an example.

adjacency matrix

Adjacency matrix

As shown in this adjacency matrix, one's represent a connection and zero's represent that there is not a connection. Taking node one as an example (the node with the number 1), the adjacency matrix shows: (1, 2) and (1, 4). This is the notation to explain that node one is connected to node two and also node four (as depicted in the matrix).

The cardinality of a graph

This is far simpler than it perhaps sound, cardinality is the number of elements in a set. So in the graph above, the cardinality of the graph G (we've assigned the graph a name 'G' just to give it a reference as if it were a variable, e.g x = 1) is six. This is because there are six verticies (which are nodes) in the graph. The cardinality as denoted by V (the nodes in the graph) is therefore six, whereas the cardinality as denoted by E (the edges in the graph) is nine because there are nine edges in the graph. So it's just a basic addition of a certain set of elements in a graph.

So this is a short introduction to graph theory :)