first time post on Mathematics.
I am an ICT teacher in a secondary school, currently delivering a unit in Mathematics and IT to one pupil in order to get him accepted onto his University degree. I have hit a difficult point. I have explained about Adjacent and Distance matrices and I am able to answer the first 3 questions myself and therefore explain with other examples how he should approach the questions. I am however 'stumped' on the last question as I feel it cannot be answered as I don't have any weightings on the edges (unless I use '1' as the weighting for each edge but that would not be logical or efficient?
The question involves finding out the shortest route from Embankment station to Bond Street station. To be able to do this I know it has to be drawn out as a discrete graph but my problem is that I do not know if you are to use all the stations given or just a portion and what weightings to write on the edges attached to the nodes. I have attached what I think are answers to questions 1-3.
I have no idea what other information I need to provide to make this an acceptable question as I am stumped. Please let me know.
I have attached the screenshot of the question.
Using the advice Jaap Scherphuis gave I have attempted this question. I am still not entirely sure I am approaching it correctly? I do understand Prim's Algorithm but I think I am collating too much information which is skewing my results? Attempt is attached as image. I also have a Distance Matrix for all the stops if anyone would like to see it which is attached.
To be honest, the more I think about how Question 4 is worded, the more confusing I find it.
The outcome of Prim's algorithm is a minimum spanning tree, i.e. a tree that connects all the vertices A-T, and has the smallest total weight. This tree is not unique.
You are free to choose any particular vertex to start the algorithm on. It does not matter which, since every vertex will become part of the tree (it has to span the graph).
Also, each time you choose another edge to add to the tree, you are free to choose from any of the adjacent edges that have the minimal possible weight value. This graph has many weight 1 edges, and so there are many possible spanning trees that can result. There is no real reason to choose any one edge over the other as long as they have the same weight.
For example, one spanning tree could be built with Prim's algorithm in this order:
It has 19 edges of course, because there are 20 vertices. Each edge connects a new vertex to the growing tree. The total weight of the finished spanning tree is just 21.
The two stations mentioned in the question (A=Embankment, M=Bond Street) are connected in my spanning tree by a path that happens to be of weight/length 6, through A-F-H-I-K-L-M.
I don't really understand what the question expects from these two stations. A spanning tree is possible that contains the shortest path between those two stations (which is 3 edges long and of total weight 3), but Prim's algorithm is not designed to find the shortest path between two vertices. That is what Dijkstra's algorithm is for.