INTRODUCTION TO GRAPH

Defination of Graph:

It consist of different points called nodes or vertex which are connected to each other lines called edges.

¤ graph is a set of nodes and vertexes.

¤ graph is denoted by G={ V, E}

where V denotes set of vertexes and E denotes set of edges.

¤ graph is non linear data structure where linked list , array , stack and queue are linear data structure.

¤ graph is widely used for different purposes i.e it has lot of applications.

¤ graph is used when there is a relation ship between pair of data items or elements.

¤Types:

2 types of graph=>

1) directed graph

2) undirected graph

explanation:

¤ directed graph: graph in which each edge assign a direction.

eg=>

¤ undirected graph: graph in which there is no direction assign to each edge.

eg=>

¤Basic definations related to graph.

A) degree of vertex: number of edges incident on that vertex.

Types of degree:

1) indegree of vertex: number of incoming edges in directed graph at that vertex.

2) outdegree of vertex:number of outgoing edges at that vertex.

¤ degree of loop is 2 in undirected graph.

 

¤ in case of directed graph loop is counted in both indegree and outdegree.

¤ indegree and outdegree of vertex is calculated in directed graph.

B) Path: of length n is sequence of n+1 nodes.

A path is said to be simple if all the nodes are distint with exception that first vertex is equal to last vertex.

C) Tree graph: is a graph without cycle. If a graph has m vertex then it must have m-1 edges.

D) complete graph: is a graph in which from every node we reach to every other all nodes.

 If graph has m vertex then it must have half of m(m-1) edges.

eg=>

E) multigraph : it is graph which consist of multiple edges and loops.

¤ loop is that whose staring and ending point same.

¤between the two nodes if there exist two edges then it is said to be muliple edge.

eg=>

F) strongly connected graph: is a graph in which every node is reachable from every other node.

eg=>

G) labeled graph: is a graph in which some variable is assign to edges of the graph.

eg=>

H) weighted graph: graph in which variables assign to edges is now assign specific numbers.
eg=>

Kindly Share The Love »»

Tweet

Save on Delicious