The A Quick Introduction to Graphs and Their Properties

Graphs have become extremely useful tools which have become essential in a variety of applications, from telecommunication (most notably finding the maximum flow in a network given the maximum flow of each link) to many of the classic NP-incomplete algorithms in the ICT world, such as that of finding the shortest path between two arbitrary points. This article acts as a quick introduction to the topic by introducing the 4 main kinds of graphs ICT experts deal with on a daily basis, and is mainly directed to ICT students.

A non-weighted graph,or simply graph (picture 1) is a pair of sets (V, E), where V is the set of the vertexes and E is the set of the edges. A vertex (or node, or point) is usually represented graphically as a point, while an edge (or line) can be regarded as a connection between two specific dots, and is generally represented with a line connecting two edges.

In picture 2, note that even if e.g. the A-G and the D-C edges intersect, that does not mean one more node has to be added. In fact, one could easily draw the same graph with no edge intersections at all.

How do we know the two pictures portray two identical (or rather equivalent) graphs? Because of the definition we gave earlier, which states that a graph is nothing but a pair of sets. Two sets are equivalent when all of their elements are identical. We can easily verify that both pictures contain the vertexes A-F; as for the edges, we can proceed as follows: since an edge associates two particular vertexes, we can pick the nodes one by one and see to which nodes they are connected to. If each connection of the first graph is also a connection of the second (and vice versa), then the two graphs are identical.

In the previous pictures, A connects to C and F; B to E and F; C to A, D and E; D to C; E to be and C; F to A and B. In a computational program, it is often convenient to represent the connection either through a boolean triangular matrix (where the element (i,j) is TRUE if there is a connection between element i and j, and FALSE otherwise) or through a linked list in which each element points to those it's connected to.

A directed graph (picture 3) is a graph in which a vertex not only associates two particular edges, but also has an orientation. We can establish the orientation by defining such graph as a pair of sets (V,A) where V is the usual set of vertexes and A is the set of directed edges (or arcs, or arrows). An arc e = (x,y) is considered to be directed from x to y; y is called the head and x is called the tail of the arc.

Note that there is a two-way connection between A and C: if you think about it, this means that to represent a generic directed graph in a computational context, a triangular matrix isn't enough, so we need a square one - 4x4 in our example - in which we'll set the element (i,j) as TRUE if the arc is oriented from the node i to the node j, and FALSE otherwise. On the other hand, the linked list representation seems to be the most convenient as a pointer in a linked list is already, to some extent, a one-way connection between two items.

Generally speaking, the linked list representation is the most convenient in a wide range of applications as it tends to save memory (consider the case of a sparse graph, a graph that is represented through a sparse square matrix) and is suitable to represent a graph in which the number of vertexes is not known a-priori. However, the matrix representation may be easier to understand at first, so we will refer to both approaches in the rest of the article, unless one representation (typically the matrix one) is highly inappropriate to achieve the desired results.

A weighted non-directed graph (picture 4) is a graph whose edges are characterized by a weight value. We can think of a weighted graph as the representation of a LAN network in which edges weights are the maximum, two-way transfer rates allowed, or as the description of road network connecting various locations (the vertexes) through bridges that can allow only a limited amount of load at any given time.

The natural matrix to represent it is a triangular one. Note that we don't need a square one, since all links are bi-directional, and thus we would have a symmetric matrix. What we need to change is instead the type in which we represent the edges, from boolean to integer. For instance, in an upper triangular matrix, the element (1,2) will be 23, while the element (1,3) can either be 0 or the conventional value of -1 to indicate the absence of an edge between B and D.

In the linked list representation, we now need to use two kinds of structures, one describing the vertexes, and another one for the edges (picture 5).

This way of representing a graph may seem overcomplicated at a first glance - especially when compared to the matrix representation - but it is also quite powerful, in that it allows us to easily solve many of the typical graph problems in a much more elegant and efficient way.

The vertex list elements (on the left) each contain a pointer to an edges sublist that enumerates the edges starting from the current node. Each element in that sublist has a field pointing directly to the destination vertex (such pointers are drawn in red in the picture above).

Note that Picture 5 doesn't necessarily portray a non-directed graph. In non-directed graphs, all edges have to be two-way, so there also has to be a symmetric pointer from B, one from C and one from the last element of the nodes list, all pointing to node A with the appropriate node weight. This results in a memory waste because we have to allocate couples of symmetric edges, but this approach is still preferable to that of the adjacency matrix in most cases. There are, of course, ways to avoid the memory waste, but we won't discuss them here for the sake of brevity.

As you can easily imagine, a weighted directed graph is a weighted graph whose edges are not necessarily symmetrical and only represent a one-way connection between nodes. Picture 5 is, again, an example of such type of graphs.

If we had to represent it through an adjacency matrix, it would have to be a square one containing integer elements. This approach is highly inefficient if #V >> #E (sparse graph).

On the other hand, we now see that the adjacency list is the ideal way to deal with such types of graphs: it avoids memory waste (because we only allocate the existing edges) and it makes wide use of pointers, which, as stated earlier, are the best way to describe a one-way connection between nodes.