What is a graph?

A graph is a collection of nodes (also called vertices) connected to each other through edges. For example, the below figure is a graph with 6 vertices and 9 edges.

 

Mathematically, Graph G is an ordered pair of V vertices and E edges, ie. G = (V,E).

 

An edge from a vertex a to vertex b is an ordered pair (a,b) if there is a directed edge between the two and an unordered pair {a,b} if there is an undirected edge between the two.

A directed edge between a and b means we can move from a to b only and never from b to a. An undirected edge between a and b means we can go from a to b and also from b to a.

The above graph has only the undirected edges between its vertices.

The vertices set V of above graph will be:

V = { 1, 2, 3, 4, 5, 6}

And the edges set E will be:

E = { {1, 2}, {1, 5}, {1, 4}, {2, 3}, {2, 5}, {2, 6}, {3, 6}, {4, 5}, {5, 6} }

 

Now, Let’s consider an example of a graph with directed edges and write it’s set V and set E.

The set of vertices will be same:

V = { 1, 2, 3, 4, 5, 6}

But the set of edges will differ:

E = { (1, 2), (1, 5), (1, 4), (1, 6), (2, 3), (3, 6), (4, 5), (5, 6) }

 

Directed and Undirected Graphs

 

A directed graph is a graph which has directed edges while an undirected graph is a graph which has only undirected or bi-directional edges. For example, Fig 1 is an undirected graph and Fig 2 is a directed graph.

 

Weighted and Un-Weighted graph

 

If there is a cost/weight associated with all edges in a graph, then that graph is a weighted graph. If there is no weight associated with the edges like in Fig 1 and Fig 2, then it is an un-weighted graph. Fig 3 is a weighted graph where edges have a weight of 5, 10 or 15 associated with them.

 

 

 

In the next post, we will implement graphs in Java and perform operations on them.