Thursday, 26 October 2017

Directed Graphs in Data Structure

A directed Graph G, is also known as a digraph in which each edge has a direction associated with it. An edge of a digraph is given as an ordered pair (u,v) of nodes in G. For an edge (u,v) in the given graph have some rules given below:
1. In the edge (u,v), edge begin from one point like u and end at another point like v. For example in the graph given below edge (A, B), edge start from node A and end at node B.
2. In the given edge (u,v), u is the predecessor of v and v is the successor of u. For example in the graph given below, for edge (A,B), A is the predecessor of B and B is the successor of A.
3. In the given edge (u,v), u and v are adjacent to each other in the graph. For example in the graph given below, for edge (A,B), A and B are adjacent to each other. similarly in the edge (B,C), B and C are adjacent to each other. 



Basic terminology of a Directed Graph:

Out-degree  of a node in the graph: It means the number of edges that originate from a given node. In the above graph the out-degree of node A is 1, out-degree of B is 2, out-degree of C is 1, out-degree of D is 1, out-degree of E is 1. It is denoted with outdeg(u).

In-degree  of a node in the graph: It means the number of edges that terminate at the given node. In the above graph the in-degree of node A is 0, in-degree of B is 1, in-degree of C is 2, in-degree of D is 2, in-degree of E is 1. It is denoted with indeg(u).

Degree of a Node : deg(u) = outdeg(u) + indeg(u). For example in the above graph-
deg(A) = outdeg(A) + indeg(A) = 1 + 0 = 1
deg(B) = outdeg(B) + indeg(B) = 2 + 1 = 3

Isolated Vertex : A vertex with degree zero is known as isolated vertex. For example, deg(u) = o, means u is an isolated vertex in the graph.

Pendant Vertex : A vertex with degree one is known as pendant vertex. In the above graph, A is a pendant vertex as A has degree one.

Cut Vertex : A vertex in a graph which when deleted remain disconnected the remaining graph. In the above graph if  the edge between A and B are deleted then vertex A remain disconnected from the graph. So we can say that A is a cut vertex in the graph.

Source Vertex : A vertex u is known as source vertex if it has a positive out-degree but a zero in-degree. In the above graph A has positive out-degree but a zero in-degree. 

Sink Vertex : A vertex u is known as sink vertex if it has a positive in-degree but a zero out-degree.


Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput