Topic: Minimum Spanning Trees of Graph theory and its real life application into the tourism Industry.
Abstract:
My research question for this extended essay is: Minimum Spanning Trees of Graph theory and its real life application into the tourism Industry. The purpose of this research report is to show how some simple mathematical concepts can also be used as a tool for big scale applications. My extended essay opens up with an introduction on why this topic was chosen and my personal approach. Following the introduction, the next section gives background information about Graph Theory and narrowing down to the concepts of Trees. The research was then narrowed into the theory of Minimum Spanning Trees. 2 crucial algorithms for finding the Minimum Spanning Tree of a network, namely Kruskal’s Algorithm and Prim’s Algorithm were used. These algorithms are used to solve for the shortest path that visits each point at least once or a path of minimum cost, in a given set of vertices and edges.
The application of these algorithms into the tourism industry of Singapore involved two different sets of networks, with vertices representing the different attractions. Each network contains 5 different attractions. Following which, raw data such as the distances between each and every attraction were collected before plotting the network. Both algorithms were then compared and contrasted in terms of their effectiveness and identify which is more preferable to be used, in terms of providing a more efficient minimum spanning tree, in terms of the shortest distance and time.
The results showed that Kruskal’s Algorithm showed a more efficient path for both sets of networks as compared to Prim’s Algorithm. Despite the fact that the difference in total weight of the minimum spanning trees obtained were insignificant to affect the planned holiday itinerary, it has been proven