Graphs For Beginners - Part-1

Introduction

Let's start with a description:

"There are several cities in a country. Suppose N cities for now. Suppose there are M roads,each of which connects some 2 pair of cities. "

A very common description found in a huge number of problems. But what is this actually? How to usefully use this information, which seems to be a very obvious thing in out real life?

Well, lets model this in terms of what we call "Graph theory". Not that it has much connection to the canonical definition of a graph that we generally encounter in our schools.

The two main, MAIN, concepts in graph theory is a "node" and an "edge". Nodes can be said to be a "place" and edge can be thought of as a way to get from one "place" to another "place". In the above problem, we basically have N nodes, and M edges. Each edge just connects two nodes.

Here the nodes are depicted by circles, and the edges are denoted by the straight lines.

SideNote : Sometimes nodes are referred to as vertices. But both are the same thing.

Simple enough, right?

Let's step up a bit.

Suppose when going from one city to another, you incur some cost. Let's say the cost is proportional to the distance that you need to travel. But how to incorporate this new additional information in our rather simple-to-understand model of this city-system? Well, turns out people already have thought of that. The solution? just add a weight to the edges.

Bingo! Now we can also see the distance between the cities.

SideNote : It is common to refer to nodes using numbers rather than actual names. For example, we generally write about "going from node 1 to node 7" rather than "going from node London to node New York

But suppose we want to have even more information. If, say, each time we visit a city, we have to pay and additional tax to the city governer. Well, just like we added a weight to the edge, turns out, it is perfectly alright to add weights to nodes as well.

But then again, it's perfectly legal to have a graph where nodes dont have any weights. Or edges dont have any weights.

Directedness : Another important classification of edges is whether they are directed or not. So what does directed mean? Well, in our previous model, if there was an Edge between Node A to Node B, then that mean we can either go from A to B or form B to A. This is what we call an undirected edge. In a directed Edge, we can only travel in one way. The other way is blocked. For example, if we have an edge from A to B, that means we can ONLY go from A to B. NOT from B to A. However, in this scenario, we can add two edges: one from A to B and one from B to A. This will work in the same way as an undirected edge, because here again, we can go from both A to B and B to A. But these two should not be treated as the same. Here is a simple explanation why: As we know, edges might have weights. In case of an undirected edge, when going from B to A or A to B we will incur the same cost, that is, the cost of the undirected edge. However, in this case, we should be careful to observe that in case of a directed graph, since there are 2 independent edges between A to B and from B to A, they may actually have different Edge weights. So, going from A to B might be of cost 7.. while the back trip is of cost 8. 

That's about it for the basics. We just have to remember, Nodes are kindof the "places" where we want to go, or where we can stop. Edges are the roads connecting these places. Edges can be weighted or unweighted. directed or undirected. Moreover, even nodes can have weights.