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.

- Transpose
- Square
- 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} =
(^{T}a_{ij}) given by ^{T}a_{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^{2}).

**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 elementvÎ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^{2}
= (V, E^{2}) such that (a, b)ÎE^{2} if and only if for some vertex cÎV, both (u, c)ÎE and (c,b)ÎE. That is, G^{2} 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^{2}from G in the Adjacency-List Representation of GCreate a new array Adj'(A), indexed by V[G]

For eachvin V[G] do

For each u in Adj[v] dohas a path of length 2.

\\ v

\\ 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

^{2}from G in the Adjacency-Matrix representation of G.For

i= 1 to V[G]

Forj= 1 to V[G]

Fork= 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}).

**3. Incidence Matrix**

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

-1 if edge

jleaves vertexj.

b_{ij}= 1 if edgejenters vertexj.

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

Now,

- If
*i*=*j*, then*b*= 1, whenever edge_{ie}b_{je}*e*enters or leaves vertex*i*and 0 otherwise. - If
*i*≠*j*, then*b*= -1, when_{ie}b_{je}*e*= (*i*,*j*) or*e*= (*j*,*i*) and 0 otherwise.

Therefore

BB

^{T}(i,j) = deg(i) = in_deg + Out_degifi=j= -(# of edges connecting

ianj)ifi≠j