This question explores how graph algorithms can be applied to a graph with an unknown edge weight.
Graph W is shown in the following diagram. The vertices of W represent tourist attractions in a city. The weight of each edge represents the travel time, to the nearest minute, between two attractions. The route between A and F is currently being resurfaced and this has led to a variable travel time. For this reason, AF has an unknown travel time x minutes, where .

Write down a Hamiltonian cycle in W.
Daniel plans to visit all the attractions, starting and finishing at A. He wants to minimize his travel time.
To find a lower bound for Daniel's travel time, vertex A and its adjacent edges are first deleted.
Use Prim's algorithm, starting at vertex B, to find the weight of the minimum spanning tree of the remaining graph. You should indicate clearly the order in which the algorithm selects each edge.
Hence, for the case where x<9, find a lower bound for Daniel's travel time, in terms of x.
Daniel makes a table to show the minimum travel time between each pair of attractions.

Consider the case where x=3.
Use the nearest neighbour algorithm to find two possible cycles.
Find the best upper bound for Daniel's travel time.
Consider the case where x>3.
Find the least value of x for which the edge AF will definitely not be used by Daniel.
Hence state the value of the upper bound for Daniel's travel time for the value of x found in part (e)(i).
The tourist office in the city has received complaints about the lack of cleanliness of some routes between the attractions. Corinne, the office manager, decides to inspect all the routes between all the attractions, starting and finishing at H . The sum of the weights of all the edges in graph W is (92+x).
Corinne inspects all the routes as quickly as possible and takes 2 hours.
Find the value of x during Corinne's inspection.

















