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.
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
- Undirected graph
- Directed 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.
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.
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).
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.
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).
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.
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 :)