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

• Connection problems
• Scheduling problems
• Transportation problems
• Network analysis
• Games and Puzzles.

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, G^T = (V, E^T) is the same as graph G with all arrows reversed. We define the transpose of a adjacency matrix A = (a_ij) to be the adjacency matrix A^T = (^Ta_ij) given by ^Ta_ij = a_ji. In other words, rows of matrix A become columns of matrix A^T and columns of matrix A becomes rows of matrix A^T. 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 = A^T.

Formally, the transpose of a directed graph G = (V, E) is the graph G^T (V, E^T), where E^T = {(u, v) Î V×V : (u, v)ÎE. Thus, G^T is G with all its edges reversed.

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

Algorithm for computing G^T from G in representation of graph G is

ALGORITHM MATRIX TRANSPOSE (G, G^T)

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

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

Algorithm for Computing  G^T 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 vÎAdj[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 G² = (V, E²) such that (a, b)ÎE² if and only if for some vertex cÎV, both (u, c)ÎE and (c,b)ÎE. That is, G² 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 G² 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 G² 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(V³).

3. Incidence Matrix

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

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

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

Specifically we have

BB^T(i,j) = ∑_eÎE  b_ie b^T_ej  = ∑_eÎE  b_ie b_je

Now,

• If i = j, then b_ieb_je = 1, whenever edge e enters or leaves vertex i and 0 otherwise.
• If i ≠ j, then  b_ieb_je = -1, when e = (i, j) or e = (j, i) and 0 otherwise.

Therefore

BB^T(i,j) =   deg(i) = in_deg + Out_deg         if  i = j

             =  -(# of edges connecting i an j )     if   i ≠ j