Solve The Travelling Salesman Problem With Graph Theory

The problem of finding the shortest path between two places is a common challenge faced by companies such as Google Maps, Ola, and Uber. These companies have developed algorithms that can efficiently calculate the fastest route to take in order to reach a destination. Similarly, there are other startups such as Zomato, Swiggy, Zepto, and Country Delight that deliver groceries and face the same task. One of the fundamental problems that these businesses face is the Travelling Salesman Problem (TSP), which is a well-known combinatorial optimisation problem that seeks to find the shortest route to a given location and returns to the starting point. The TSP is a crucial problem in logistics, planning, and optimisation, with a broad range of practical applications in real-world scenarios.

For a student of Class 12, studying TSP and Graph Theory is essential as it helps in developing problem-solving skills, logical thinking, and computational thinking. These skills are crucial for students who plan to pursue careers in computer science, engineering, mathematics, or any field that requires analytical and critical thinking. By understanding TSP and its solutions using Graph Theory, students will learn to appreciate how mathematics is used in solving real-world problems.

Graph Theory

Graph Theory is a branch of mathematics that deals with the study of graphs, which are mathematical structures used to represent networks, relationships, and connections. In other words, a graph is a way to show information using points (nodes) and lines (edges) that connect them. Each line connects two points, and it has a specific name based on the two points it connects. Sometimes, the line has a number assigned to it to show how important it is. Here is an example of a graph:

Characteristics Graphs

Graphs have two important characteristics i.e. Adjacent nodes, Node degree

Adjacent nodes - are nodes that are connected by an edge.

Node degree - the number of edges that connect to a node.

In undirected graphs, the degree is the number of nodes that are connected to a node. In directed graphs, the in-degree is the number of edges that point towards a node, and the outdegree is the number of edges that point away from a node.

Also check - Understanding the Theory of Relativity and Time Dilation

Types Of Graphs

Directed Graph: A directed graph is a type of graph where edges have a direction pointing to a specific node. A Directed Acyclic Graph (DAG) is a special kind of directed graph with no loops or cycles. This means that for any given vertex, there are no edges that start and end at that same vertex. DAGs are useful for things like analysing critical games, evaluating expression trees, and evaluating games. A tree is a type of graph that is like a DAG, but each child can only have one parent.

Undirected Graph: A graph where we don't say which direction the lines go. If there's a line between two places, you can go from one place to the other and back.

• Connected graph: A graph where you can get from any place to any other place by following the lines. There's no place you can't get to.

• Complete graph: A graph where every place is connected to every other place. It has lots of lines. A complete graph would have n(n-1)/2 edges.

• Biconnected graph: A graph where you can't break it up by taking away one place. All the places are connected to each other in more than one way.

Applications Of Graph Theory

Graph theory is a tool that we use in real life to help solve problems.

• Social Network: We can use graph theory to represent social networks. Each person is a dot on the graph, and the lines between them represent their connections, activities, and friendships.

• Google Maps: We can use graph theory to help us find the quickest way to get from one place to another. We represent the different places as dots on the graph and the roads as lines between them.

• Recommendations on e-commerce websites: We can use graph theory to help suggest things that a person might like to buy. We look at the things they have bought before and the things that are similar to them and then suggest other items that might be of interest.

• Graph theory is also used in chemistry and physics to help us study how molecules are put together.

Travelling Salesman Problem

The Travelling Salesman Problem (TSP) is a well-known optimisation problem in graph theory that involves finding the shortest possible route that visits each city in a given list exactly once and returns to the starting city. Here's an example of how to solve the TSP with graph theory for a set of four cities: City 1, City 2, City 3, and City 4.

The first step is to create a graph that represents the cities and the distances between them. In this case, we can represent the cities as nodes and the distances between them as edges. Here's a table that shows the distances between each pair of cities:

We can show this information in a table format.

Path Choose by salesman

Path 1: 1→2→3→4→1 distance travelled is 10 + 9 + 12 + 20 = 51

Path 2: 1→3→2→4→1 distance travelled is 6 + 13 + 10 + 20 = 49

Path 3: 1→4→3→2→1 distance travelled is 20 + 9 + 13 + 5 = 47

Path 4: 1→4→2→3→1 distance travelled is 20 + 8 + 9 + 6 = 43

Path 5: 1→2→4→3→1 distance travelled is 10 + 10 + 9 + 6 = 35

The salesman should choose the route that is shown below because it has the shortest distance.

The distance travelled is 35 units.

Also check - Exploring The Cosmos: How Mathematics Powers Space Travel