A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as **vertices**, and the links that connect the vertices are called **edges**.

Formally, a graph is a pair of sets **(V, E)**, where **V **is the set of vertices and **E **is the set of edges, connecting the pairs of vertices. Take a look at the following graph −

In the above graph,

V = {a, b, c, d, e}

E = {ab, ac, bd, cd, de}

##### Graph Data Structure

** **Mathematical graphs can be represented in data structure. We can represent a graph using an array of vertices and a two-dimensional array of edges. Before we proceed further, let's familiarize ourselves with some important terms −

**Vertex**− Each node of the graph is represented as a In the following example, the labeled circle represents vertices. Thus, A to G are vertices. We can represent them using an array as shown in the following image. Here A can be identified by index 0. B can be identified using index 1 and so on.**Edge**− Edge represents a path between two vertices or a line between two In the following example, the lines from A to B, B to C, and so on represents edges. We can use a two-dimensional array to represent an array as shown in the following image. Here AB can be represented as 1 at row 0, column 1, BC as 1 at row 1, column 2 and so on, keeping other combinations as 0.**Adjacency**− Two node or vertices are adjacent if they are connected to each other through an In the following example, B is adjacent to A, C is adjacent to B, and so on.**Path**− Path represents a sequence of edges between the two In the following example, ABCD represents a path from A to D.

##### Basic Operations on Graph

** **Following are basic primary operations of a Graph −

**Add Vertex**− Adds a vertex to the graph.**Add Edge**− Adds an edge between the two vertices of the graph.**Display Vertex**− Displays a vertex of the graph.

##### Types of Graph:

** **

**Finite Graphs:**A graph is said to be finite if it has finite number of vertices and finite number of edges.**Infinite Graph:**A graph is said to be infinite if it has infinite number of vertices as well as infinite number of edges.

**Trivial Graph:**A graph is said to be trivial if a finite graph contains only one vertex and no edge.**Simple Graph:**A simple graph is a graph which does not contains more than one edge between the pair of vertices. A simple railway tracks connecting different cities is an example of simple graph.

**Multi Graph:**Any graph which contain some parallel edges but doesn’t contain any self- loop is called multi graph. For example A Road Map.**Parallel Edges:**If two vertices are connected with more than one edge than such edges are called parallel edges that is many roots but one destination.**Loop:**An edge of a graph which join a vertex to itself is called loop or a self-loop.

**Null Graph:**A graph of order n and size zero that is a graph which contain n number of vertices but do not contain any edge.

**Complete Graph:**A simple graph with n vertices is called a complete graph if the degree of each vertex is n-1, that is, one vertex is attach with n-1 edges. A complete graph is also called Full Graph.

**Pseudo Graph:**A graph G with a self loop and some multiple edges is called pseudo graph.**Regular Graph:**A simple graph is said to be regular if all vertices of a graph G are of equal degree. All complete graphs are regular but vice versa is not possible.

**Bipartite Graph:**A graph G = (V, E) is said to be bipartite graph if its vertex set V(G) can be partitioned into two non-empty disjoint subsets. V1(G) and V2(G) in such a way that each edge e of E(G) has its one end in V1(G) and other end in V2(G).

The partition V1 U V2 = V is called Bipartite of G.

Here in the figure:

V1(G)={V5, V4, V3}

V2(G)={V1, V2}

**11. Labelled Graph: **If the vertices and edges of a graph are labelled with name, data or weight then it is called labelled graph. It is also called *Weighted Graph*.

**12. Digraph Graph: **A graph G = (V, E) with a mapping f such that every edge maps onto some ordered pair of vertices (Vi, Vj) is called Digraph. It is also called *Directed Graph*. Ordered pair (Vi, Vj) means an edge between Vi and Vj with an arrow directed from Vi to Vj.

Here in the figure: e1 = (V1, V2)

e2 = (V2, V3) e4 = (V2, V4)

**13. Subgraph: **A graph G = (V1, E1) is called subgraph of a graph G(V, E) if V1(G) is a subset of V(G) and E1(G) is a subset of E(G) such that each edge of G1 has same end vertices as in G.

Types of Subgraph:

**Vertex disjoint subgraph:**Any two graph G1 = (V1, E1) and G2 = (V2, E2) are said to be vertex disjoint of a graph G = (V, E) if V1(G1) intersection V2(G2) = null. In figure there is no common vertex between G1 and G2.**Edge disjoint subgraph:**A subgraph is said to be edge disjoint if E1(G1) intersection E2(G2) =null. In figure there is no common edge between G1 and G2.

**Note: **Edge disjoint subgraph may have vertices in common but vertex disjoint graph cannot have common edge, so vertex disjoint subgraph will always be an edge disjoint subgraph.

**14. Connected or Disconnected Graph: **A graph G is said to be connected if for any pair of vertices (Vi, Vj) of a graph G are reachable from one another. Or a graph is said to be connected if there exist atleast one path between each and every pair of vertices in graph G, otherwise it is disconnected. A null graph with n vertices is disconnected graph consisting of n components. Each component consist of one vertex and no edge.

**15. Cyclic Graph: **A graph G consisting of n vertices and n> = 3 that is V1, V2, V3…Vn and edges (V1, V2), (V2, V3), (V3, V4)….(Vn, V1) are called cyclic graph.

##### Application of Graphs:

**Computer Science:**In computer science, graph is used to represent networks of communication, data organization, computational devices etc.**Physics and Chemistry:**Graph theory is also used to study molecules in chemistry and physics.**Social Science:**Graph theory is also widely used in sociology.**Mathematics:**In this, graphs are useful in geometry and certain parts of topology such as knot theory.**Biology:**Graph theory is useful in biology and conservation efforts.