Thursday, 26 October 2017

Basic Terminology used in Graph Data Structure

Introduction: A Graph is a non-linear and abstract data structure which is further used to implement relational data.  It is basically a collection of different vertices (v1, v2, v3,..........., vn) and connecting edges (e1, e2, e3,..............,en). They are mostly used to represent any situation where different entities are related to each other in pairs. For example, the following information can be represented by using Graph data structure:
1. Transportation Network
2. Telephone network 
3. Airports Network etc.

Example of a Graph in Data Structure: We represent Graph in data structure as  G = (V, E)
Where V = set of all the vertices of the given graph
              E = set of all the edges between different vertex



Here in this example above we have set of five vertices ( like A, B, C, D, E ) and set of seven edges ( like edge between A-B, A-C, A-D, B-B, C-D, B-E, D-E ).
  
Basic Graph Terminology:

1. Adjacent Nodes: In above graph there is an edge between A-B, Then we can say that these two nodes are adjacent to each other. A is also adjacent to C and D but not adjacent to E because A is not directly connected to C.

2. Degree of a Node: Degree of any node in a graph means how many total edges that particular node contain. In the above graph degree of node A is equal to 3, degree of node E is two and so on. If the degree of any node is zero then that node is known as isolated node.

3. Regular Graph: In such type of graph the degree of each nodes are similar. It may be two or more than  for each node. The above node became a regular graph if the degree of each node are equal. A regular graph with all the vertices of degree n then that graph is known as n-regular graph.

4. Multi-graph : A graph with multiple edges and loops is known as multi-graph. The size of the graph is the total number of edges in it.
5. Closed Path : A path is known as closed path if the edges has the same end-points.

6. Cycle : A path in which the first and last vertices are same. A simple cycle has no repeated edges and vertices ( except the first and last).

7. Connected Graph: If all the vertices of the graph are connected with each other in any way and there is not any isolated node is known as connected graph. A graph without any cycle is known as tree. The above graph is connected graph.

8. Complete Graph: A graph is known as complete graph if all its node are fully connected with each other. the above graph are not fully complete graph because A-E is not present in the graph.

10. Weighted Graph: If in the graph some values are given to the edges then that graph is known as weighted graph. It is also known as leveled graph.

11. Multiple Edges: If in any graph any two edges are connecting the same (starting and end node) then that is known as multiple edges graph.

* the copyright of the above image is remain with the http://btechsmartclass.com

Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput