Mathematics D1 WDM11: Algorithms on Graphs Topical Past Paper Questions

The table shows the least distances, in km, between eight towns. Imani wants to visit all eight towns. She needs to find a route which minimises the distance travelled, starting and finishing at A. (a) Show that there are two nearest neighbour routes starting at A. You must make…

[The total length of the network is 338] Figure 2 Figure 2 represents a network of roads connecting a group of villages. The number on each arc is the length, in km, of the corresponding road. Bolin needs to inspect the network in Figure 2. He must travel along each road at least…

Figure 3 [The total weight of the network is 494] Direct roads between nine factories, A, B, C, D, E, F, G, H and J, are represented in Figure 3. The number on each arc represents the lengths, in kilometres, of the corresponding road. The table below shows the shortest distances,…