(Solved): Consider the following algorithm for decreasing cycle length: Choose an arbit ...

???????

Consider the following algorithm for decreasing cycle length: Choose an arbitrary cycle $$v_1?$$ $$v_2?\dots ?v_n?v_1$$. Go through $$i=1$$ to $$i=n?1$$ and check if swapping any $$v_i$$ and $$v_{i+1}$$ will yield a shorter cycle; swapping them if so. After $$i=n?1$$, check if swapping $$v_n$$ and $$v_1$$ will yield a shorter cycle, swapping them if so. Start again at $$i=1$$ and stop when you've checked $$n$$ times consecutively without a swap occurring. i. Each check requires calculating the new total cycle length, where each mathematical operation requires a tiny amount of time. What is the fastest way we could do this check at each stage? [1 mark] ii. Demonstrate an implementation of this algorithm on the following graph, beginning with the cycle $$A?>B?>C?>D?>A$$. [3 marks] $$AB(9),AD(10),BC(11),BD(6),CD(13)$$ iii. Construct a graph where this algorithm does not work. That is, it does not give the shortest $$n$$-cycle. [2 marks]