Graph Algorithms

 

Graph Theory is an area of mathematics that deals with following types of problems


The Graph Theory has important applications in Critical path analysis, Social psychology, Matrix theory, Set theory, Topology, Group theory, Molecular chemistry, and Searching.

Those who would like to take a quick tour of essentials of graph theory please go directly to "Graph Theory" from here.
 

 

Digraph    

A directed graph, or digraph G consists of a finite nonempty set of vertices V, and a finite set of edges E, where an edge is an ordered pair of vertices in V. Vertices are also commonly referred to as nodes. Edges are sometimes referred to as arcs.

As an example, we could define a graph G=(V, E)  as follows:

 V = {1, 2, 3, 4}
 E = { (1, 2), (2, 4), (4, 2) (4, 1)}

Here is a pictorial representation of this graph.

 

The definition of graph implies that a graph can be drawn just knowing its vertex-set and its edge-set. For example, our first example


has vertex set V and edge set E where: V = {1,2,3,4} and E = {(1,2),(2,4),(4,3),(3,1),(1,4),(2,1),(4,2),(3,4),(1,3),(4,1). Notice that each edge seems to be listed twice.

Another example, the following Petersen Graph G=(V,E) has vertex set V and edge set E where: V = {1,2,3,4}and E ={(1,2),(2,4),(4,3),(3,1),(1,4),(2,1),(4,2),(3,4),(1,3),(4,1)}.

 

 

 

We'll quickly covers following three important topics from algorithmic perspective.

  1. Transpose
  2. Square
  3. Incidence Matrix

 

1. Transpose

If graph G = (V, E) is a directed graph, its transpose, GT = (V, ET) is the same as graph G with all arrows reversed. We define the transpose of a adjacency matrix A = (aij) to be the adjacency matrix AT = (Taij) given by Taij = aji. In other words, rows of matrix A become columns of matrix AT and columns of matrix A becomes rows of matrix AT. Since in an undirected graph, (u, v) and (v, u) represented the same edge, the adjacency matrix A  of an undirected graph is its own transpose: A = AT.

Formally, the transpose of a directed graph G = (V, E) is the graph GT (V, ET), where ET = {(u, v) VV : (u, v)E. Thus, GT is G with all its edges reversed.

We can compute GT from G in the adjacency matrix representations and adjacency list representations of graph G.

Algorithm for computing GT from G in representation of graph G is

 

ALGORITHM MATRIX TRANSPOSE (G, GT)

For i = 0 to i < V[G]
    For j = 0 to j V[G]
        GT (j, i) = G(i, j)
        j = j + 1;
    i = i + 1

 

To see why it works notice that if GT(i, j) is equal to G(j, i), the same thing is achieved. The time complexity is clearly O(V2).

 

Algorithm for Computing  GT from G in Adjacency-List Representation

In this representation, a new adjacency list must be constructed for transpose of G. Every list in adjacency list is scanned. While scanning adjacency list of v (say), if we encounter u, we put v in adjacency-list of u.

 

ALGORITHM LIST TRANSPOSE [G]

for  u = 1 to V[G]
    for  each element vAdj[u]
    Insert u into the front of Adj[v]

 

To see why it works, notice if an edge exists from u to v, i.e., v is in the adjacency list of u, then u is present in the adjacency list of v in the transpose of G.

 

 

2. Square

The square of a directed graph G = (V, E) is the graph G2 = (V, E2) such that (a, b)E2 if and only if for some vertex cV, both (u, c)E and (c,b)E. That is, G2 contains an edge between vertex a and vertex b whenever G contains a path with exactly two edges between vertex a and vertex b.

 

Algorithms for Computing G2 from G in the Adjacency-List Representation of G

Create a new array Adj'(A), indexed by V[G]
For each v in V[G] do
For each u in Adj[v] do
    \\ v
has a path of length 2.
    \\ to each of the neighbors of u
make a copy of Adj[u] and append it to Adj'[v]
Return Adj'(A).

 

For each vertex, we must make a copy of at most |E| list elements. The total time is O(|V| * |E|).

 

Algorithm for Computing G2 from G in the Adjacency-Matrix representation of G.

For i = 1 to V[G]
    For j = 1 to V[G]
           For k = 1 to V[G]
                c[i, j] = c[i, j] + c[i, k] * c[k, j]

 

Because of three nested loops, the running time is O(V3).

 

3. Incidence Matrix

The incidence matrix of a directed graph G=(V, E) is a VE matrix B = (bij) such that

          -1         if edge j leaves vertex  j.
bij =    1         if edge j enters vertex  j.
           0         otherwise.

 

If B is the incidence matrix and BT  is its transpose, the diagonal of the product matrix BBT represents the degree of all the nodes, i.e., if P is the product matrix BBT  then P[i, j] represents the degree of node i:

Specifically we have

BBT(i,j) = ∑eE  bie bTej  = ∑ebie bje

Now,

 

Therefore

BBT(i,j) =   deg(i) = in_deg + Out_deg         if  i = j

             =  -(# of edges connecting i an j   if   ij