Day 30: Graph terminologies

Hello Dear Students,
 Hope you all are doing good.

So, aaj hum graphs ke baare mein study karenge,

Let's get started...

GRAPH - Graph is a diagram or drawing, jisme various vertices and edges hote hain, jo ki connected hote hain. Vertices is also known as points or nodes. Vertices mein hum data elements ko store karate hain and edges basically lines hoti hai jisse vertices ko connect kiya jata hai. 

G = [ V(G) , E(G) ] , where
G is Graph, V is the Vertex set of graph and E is the edge set of graph G.

For example, 

In the above graph, V={A,B,C,D} and E={AB,BC,CD,BD) and G=(V,E).

GRAPH TERMINOLOGIES -  Graph mein various basic terminologies hain, which are as follows-
  • PATH - Path means ek vertex se doosri vertex tak jaane ka raasta. Path is between edges, from one vertex to another, we move from one vertex to another.  For example, in above graph from A to C, the path can be - {A,<AB>,B,<BC>,C} Here, <AB> means the edge AB. 
  • CYCLE - Cycle wo path hota hota hai jisme starting and ending vertex same hoti hai. For example, if we want to find the path between B to B , then it is called cycle because starting vertex and ending vertex is same i.e. B. So, cycle = {B,<BC>,C,<CD>,D,<DB>B}.
  • LOOP - Loop means jisme starting and ending vertex same hoti hai, ek circle ki tarah hoti hai jo ki only one vertex ke saath hi hoti hai simply. For example,  here in the below graph, D has a loop from {D,<DD>,D}.

  • PARALLEL EDGE - Jab 2 edges ek hi vertex se connected hote hain then wo parallel edges hote hain.  Agar 2 edges have same end vertices(starting and ending vertices), then the edges are called parallel edges. For example, in below graph, 
    parallel edge graph

The edges e1 and e5 are parallel edges because it has same starting and ending vertices i.e. A and B.

  • ISOLATED VERTEX - Isolated means lonely simply. So isolated vertex means jo single lonely vertex ho with no edges connected. 
  • DEGREE OF VERTEX - Degree of vertex means ek vertex ke saath kitne edges connected hain. Agar loop hogi then use 2 count kiya jata hai because wo cycle mein hoti hai. For example,   
Degree of vertices are- 

and if we count the loop graph vertices then, loop is counted twice, for example, 
Degree of vertices are -

  • ODD VERTEX - Odd vertex means jis vertex ki degree odd number hai wo odd vertex. For example, in above graph, d(A) is 1 which means A is odd vertex.
  • EVEN VERTEX - Even vertex means jis vertex ki degree even number hai wo even vertex. For example, in above graph d(B), d(C), d(D) is even which means B,C,and D are even vertices.

Best of luck Students,
Do visit our website regularly for more content and for daily tests.