Question

Discuss the characteristics of graph data structure; use three examples to demonstrate the kinds of questions that graph can solve.

Answer 1

A Graph is a pictorial representation of finite number of objects in which some of the objects (pairs) are connected by link. The objects which are interconnected through these links are called nodes, vertices, station, host and links thorough which these objects are connected is called edges, branches, wire etc.

By definition a Graph consists finite number set of vertices and edges (V, E). Edges connect the vertices and form a graph.

Various real life of examples are there which can be solved by the graph, from which three most popular of them are explained below:

1.Konigsberg Bridge problem:

Konigsberg bridge problem is one of the famous problem which leads to the inception of graph theory. In 1736 this problem marked as negative by famous mathematician Eular. The Königsberg city is in Prussia (now Kaliningrad, Russia) was situatedon both sides of a river named as Pregel, and had total 4 islands each of which was connected well through seven bridges. The problem was to walk through the city that would cross each of those bridges once and only once. Eular proved that this problem had no solution back in 1736

2. Travelling salesman problem:

This is very famous problem in which a salesman is there to sell some items in several cities, now the what is running inside this salesman's mind is that how to cover all the cities so that the distance which he cover is minimal. It means that salesman have to cover all the city once and come back to the source while covering minimum distance.

3. Shortest path Algorithm:

This algorithm which is implemented on graphs can relate very easily to real life examples and can be implemented to solve problems like how to cover shortest path from a source to destination.

For example:

Consider the graph shown in figure on right side. A TSP tour in the graph is 1-2-4-3-1. The cost of the tour is 10+25+30+15 which is 80.

Hope this may help you

Thank you ?