 ## Graph Algorithms 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, 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) Î V×V : (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]
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 cÎV, 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

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 V×E 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) = ∑eÎE  bie bTej  = ∑eÎbie bje

Now,

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

Therefore

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

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