A look into the world of Graphs..!!

What are Graphs and various Graph terminologies? Let me take you to the time when I was a little kid. There was this story which my mom used to tell me while going to bed. The Ramayana. Sita ji was kidnapped by Ravana, and taken to Lanka. India and Lanka have no link between them, so how would Rama ji reach to Sita Ji? Hence, Rama ji and his army started building a stone bridge over 2400 Km to connect India to Sri Lanka. Hanuman ji knew how to fly, hence Rama ji and his army started walking on the stone bridge, and Hanuman ji started flying parallelly to the others, and all of them reached Sri Lanka to rescue Sita ji.

 

Now, I will tell you 'some' very basic definitions, and once you are comfortable with them, we will be moving on to some other very basic terminologies of graph theory. Try to relate them with the above example. For now, just remember, a graph G is a collection of vertices and their corresponding edges, i.e., G=(V, E).

 

Directed edge: a is the origin vertex and b is the destination vertex. Flow is one way, a to b. (Fig 1)

 

Directed graph: A graph containing only directed edges. (Fig 1)

 

Undirected edge: Flow is two way, a to b, as well as b to a.(Fig 2)

 

Undirected graph: A graph containing only undirected edges. (Fig 2)

 

Parallel edges: Two or more edges having the same corresponding origin and destination vertices. (Fig 3)

 

Disconnected graph: Fig 4 below is a disconnected graph with two connected components, G={G1, G2} where G1=(V1, E1) where V1={A, B, C} and E1={{A, B}, {B, C}, {A, C}} and G2=(V2, E2) where V2={D, E} and E2={{D, E}}

Connected Graph: A graph is connected if there is a path from every vertex to every another. Fig 5

 

Weighted graph: Fig 6

 

Unweighted graph: Fig 1, Fig 2, Fig 3, Fig 4 and Fig 5 are examples of unweighted graphs

 

Degree of a vertex:Well, this is quite a relative term.

First we will see what it means by degree of a vertex in an undirected graph. Degree of a vertex in an undirected graph means, How many edges are falling on that vertex.

 

Degree of vertex 1: two

Degree of vertex 2: two

Degree of vertex 3: two

Degree of vertex 4: one

Degree of vertex 5: one

 

To be noted, self loop is counted twice in an undirected graph. Therefore, degree of vertex 1 in the below graph will be---------------?

It will be four, one for edge (1,2), one for (1,5), and two for self loop.

 

Now we will see what it means by degree of a vertex in a directed graph.

There are two types of degrees in an undirected graph: Indegree and Outdegree

Indegree: How many edges are coming to the vertex?

Outdegree: How many edges are going out of the vertex?

InDegree of vertex 1: zero

InDegree of vertex 2: two

InDegree of vertex 3: zero

InDegree of vertex 4: two

InDegree of vertex 5: two

InDegree of vertex 6: one

 

OutDegree of vertex 1: two

OutDegree of vertex 2: one

OutDegree of vertex 3: two

OutDegree of vertex 4: one

OutDegree of vertex 5: one

OutDegree of vertex 6: one

 

If you have not yet related the above examples with the mentioned terms, below is the explanation.

 

Now, what do you think should be the vertices of the graph we are about to draw? Ummm..Let India be vertex a, and Sri Lanka be vertex b.

 

India and Lanka have no link between them: Disconnected, Unweighted graph till now. Fig 7

 

Hence, Rama ji and his army started building a stone bridge over 2400 Km to connect India to Sri Lanka: Weighted graph with a single edge of weight 2400, Also we can see, now the graph is connected via directed edge from India to Sri Lanka(because the traffic is one way, Rama going to Lanka), Hence this is a directed, weighted graph now. Fig 8

 

Hanuman ji knew how to fly, hence Rama ji and his army started walking on the stone bridge, and Hanuman ji started flying parallelly to the others: Parallel edges, one is created by Rama and his army(the stone bridge way), and the other is created by Hanuman(the airway). Fig 9

Now, since you are well adapted to the above terms, let us move further.

 

Self loops: An edge that connects itself. Fig 10

Cycle: A path where the first and last vertex is the same one. In Fig 10 below, (1, 2, 0) is a cycle

               

Directed Acyclic Graph: Popularly known as DAG. It goes by its name, no cycle is allowed, and the graph is directed.

                             

Sparse Graph: A graph where the number of edges is much lesser than  V x V

                                                

Dense Graph: A graph where the number of edges is equal or almost equal to  V x V

                                             

Complete Graph: 

Let me ask you to draw a graph: There are 5 friends. Each one is a friend of another. Represent this scenario through a friendship graph.

Any guesses?

Here it is:                            

This graph is called K5(K we use for complete graph, 5 is the number of vertices). Why don't you practice K1 , K2, K3, K4...............

Now, before ending this topic, I will leave you with a closing note. How many edges the K1 , K2, K3, K4, K5 have? If you observe carefully, you can see that a complete graph of 'n' vertices has [n(n-1)]/2 edges.

 

 

Contributor's Info

Created:
0Comment