L is a list of integers representing a set of navigable (by canoe) lakes. P is an array of length |L|, where for each u ∈ L, P[u] is a linked list containing pairs (v, x) where v represents a lake in L having a portage (footpath) between u and v, and x is the (positive) length of the portage between lakes u and v. Each portage has a distinct length, and every pair of lakes has, at most, one portage between them. It is also possible to make a trip between any pair of lakes using one or more portages. Each trip between a pair of lakes has a toughness: the length of the longest portage on the trip (i.e., longest footpath of the trip where canoeists must haul canoes and gear on their backs). Each pair (i, j) of lakes has a rating, which is defined as the minimum toughness of any trip between lakes i and j. Canoeists want to determine for each pair of lakes (i, j), the rating of (i, j) and a trip with this rating between these two lakes. The next three questions show how to do it efficiently.

a). Explain, in precise English, how to represent this set-up as a weighted undirected graph G = (V, E).

b). Prove that if G = (V, E) contains a cycle C and e = (u, v) is the maximum weight edge in C, then the rating of all pairs of lakes is the same in G and G0 = (V, E − e).

c). Let T be any MST for G. Prove that for each pair of lakes (i, j), the rating of (i, j) in G is also the rating of (i, j) in T. Note that this implies that the rating of (i, j) in G is the toughness of the unique (!) trip between lakes i and j in the MST T of G. In other words, the MST T of G gives the best trip (the one with the smallest toughness) between any pair of lakes in G.

Answer rating: 100% (QA)

a Explain in precise English how to represent this setup as a weighted undirected graph G V E Weighted Graphs Implementation Dijkstra Algorithm Lesson Transcript Instructor Apostolos Ntokos This lesso... View the full answer