Introduction to graphs and graph terminology

 A graph is a data structure that is used to represent a relational data. For example, a set of terminals in a network or a roadmap of all cities in a country. Such complex relationships can be represented using a graph data structure. Mathematically, a graph can be defined as follows

A graph G = (V, E) consists of two sets V and E. The elements of V are called the vertices and the elements of E the edges of G. Each edge is a pair of vertices.

Let us consider the graph G1 in the above figure. Here 

V={v1,v2,v3,v4} is vertex set ( nodes)

E={ (v1,v2),(v1,v3),(v1,v4),(v2,v3),(v3,v4)} is a edge set.

Terms associated with Graphs

1. Adjacent vertex: A vertex Vi is adjacent to ( or neighbor of ) another vertex say, Vj of there is an edge from Vi to Vj. 

  For example, in the above graph G1, V4 and V3, V3 and V2, V4 and V1, V1 and V2 are adjacent nodes because they are connected by an edge / line.

2. Self loop: If there is an edge whose starting and end vertices are same then it is called a self loop or simply loop.

3. Parallel edges: If there us more than one edge between the same pair of vertices, then they are know as the parallel edges.

4. Isolated Vertex: A vertex is isolated if there is no edge connected from any other vertex to the vertex.

5. Degree of vertex: The number of edges connected with vertex Vi is called the degree of vertex Vi and is denoted by degree(Vi).

For a directed graph, there are two degrees exist: indegree and outdegree

indegree: Number of edges which are incoming to that node. In the above figure, graph G2, the number of incoming edges for V1 are 2, there fore indegree(V1)=2

outdegree: The number of outgoing edges from a node V is called out degree of that node. For example, in the above graph G2, node V3 has 2 outgoing edges from it. There fore outdegree(V3)=2.

6. Pendant vertex: A vertex Vi is pendant if its indegree is one and out degree is zero.

7. Path: A path is a sequence if different vertices, each adjacent to the next.