Graph G is a pair (V, E), where V is a finite set of **vertices** and E is a finite set of **edges**. We will often denote **n = |V|, e = |E|.**

A graph is generally displayed as figure 6.5.1, in which the vertices are represented by **circles** and the edges by **lines**.

An edge with an orientation (i.e., arrow head) is a **directed edge**, while an edge with no orientation is our **undirected edge**.

If all the edges in a graph are undirected, then the graph is an **undirected graph**. The graph in figure 6.5.1(a) is an undirected graph. If all the edges are directed; then the graph is a **directed graph**. The graph of figure 6.5.1(b) is a directed graph. A directed graph is also called as **digraph**. A graph G is connected if and only if there is a simple path between any two nodes in G

A graph G is said to be **complete** if every node a in G is adjacent to every other node v in G. A complete graph with n nodes will have **n(n-1)/2** edges. For example, Figure 6.5.1.(a) and figure 6.5.1.(d) are **complete graphs**.

A directed graph G is said to be **connected**, or **strongly connected**, if for each pair (u, v) for nodes in G there is a path from u to v and also a path from v to u. On the other hand, G is said to be **unilaterally connected** if for any pair (u, v) of nodes in G there is a path from u to v or a path from v to u. For example, the digraph shown in figure 6.5.1 (e) is strongly connected.

We can assign weight function to the edges: Wg(e) is a weight of edge e ∈ E. The graph which has such function assigned is called **weighted graph**.

The number of incoming edges to a vertex v is called **in–degree** of the vertex (denote indeg(v)). The number of outgoing edges from a vertex is called **out-degree** (denote outdeg(v)). For example, let us consider the digraph shown in figure 6.5.1(f),

indegree(v1) = 2

outdegree(v1) = 1

indegree(v2) = 2

outdegree(v2) = 0

A path is a sequence of vertices (v1, v2, . . . . . , vk), where for all i, (vi, vi+1) ε E. A path is simple if all vertices in the path are distinct. If there is a path containing one or more edges which starts from a vertex Vi and terminates into the same vertex then the path is known as a cycle. For example, there is a cycle in figure 6.5.1(a), figure 6.5.1(c) and figure 6.5.1(d).

If a graph (digraph) does not have any cycle then it is called **acyclic graph**. For example, the graphs of figure 6.5.1 (f) and figure 6.5.1 (g) are **acyclic graphs**.

A graph G’ = (V’ , E’ ) is a sub-graph of graph G = (V, E) iff V’ ⊆ V and E’ ⊆ E.

A **Forest** is a set of disjoint trees. If we remove the root node of a given tree then it becomes forest. The following figure shows a forest F that consists of three trees T1, T2 and T3.

A graph that has either self loop or parallel edges or both is called **multi-graph**.

Tree is a connected acyclic graph (there aren’t any sequences of edges that go around in a loop). A **spanning tree** of a graph G = (V, E) is a tree that contains all vertices of V and is a subgraph of G. A single graph can have multiple spanning trees.

Let T be a spanning tree of a graph G. Then

- Any two vertices in T are connected by a unique simple path.
- If any edge is removed from T, then T becomes disconnected.
- If we add any edge into T, then the new graph will contain a cycle.
- Number of edges in T is n-1.

**Representation of Graphs:**

There are two ways of representing digraphs. They are:

- Adjacency matrix.
- Adjacency List.
- Incidence matrix.

**Adjacency matrix:**

In this representation, the adjacency matrix of a graph G is a two dimensional n x n

matrix,

The matrix is **symmetric** in case of **undirected graph**, while it may be **asymmetric** if the

graph is **directed**. This matrix is also called as** Boolean matrix or bit matrix.**

Figure 6.5.2(b) shows the adjacency matrix representation of the graph G1 shown in

figure 6.5.2(a). The adjacency matrix is also useful to store multigraph as well as

weighted graph. In case of multigraph representation, instead of entry 0 or 1, the entry

will be between number of edges between two vertices.

In case of weighted graph, the entries are weights of the edges between the vertices.

The adjacency matrix for a weighted graph is called as cost adjacency matrix. Figure

6.5.3(b) shows the cost adjacency matrix representation of the graph G2 shown in

figure 6.5.3(a).

**Adjacency List**:

In this representation, the n rows of the adjacency matrix are represented as n linked

lists. An array Adj[1, 2, . . . . . n] of pointers where for 1 < v < n, Adj[v] points to a

linked list containing the vertices which are adjacent to v (i.e. the vertices that can be

reached from v by a single edge). If the edges have weights then these weights may

also be stored in the linked list elements. For the graph G in figure 6.5.4(a), the

adjacency list in shown in figure 6.5.4 (b).

**Incidence Matrix:**

In this representation, if G is a graph with n vertices, e edges and no self loops, then

incidence matrix A is defined as an n by e matrix, say A = (ai,j), where

Here, n rows correspond to n vertices and e columns correspond to e edges. Such a

matrix is called as vertex-edge incidence matrix or simply incidence matrix.

Figure 6.5.4(b) shows the incidence matrix representation of the graph G1 shown in

figure 6.5.4(a).