6-3. Assume that all edges in the graph have distinct edge weights (i.e. , no pair of edges have the same weight). Is the path between a pair of vertices in a minimum spanning tree necessarily a shortest path between the two vertices in the full graph? Give a proof or a counterexample.

Solution Let’s start with an example.

Our minimum spanning tree is marked by the thick edges. We are interested in the path between B and D. We’re interested in the weight b. If b is smaller than 5, the MST (minimum spanning tree) isn’t the shortest path. Would this change our MST? It depends. We could form the graph from B -> D -> C instead of B -> C -> D. It would be our MST if , i.e. In conclusion, the MST isn’t the shortest path if

6-6. Suppose we are given the minimum spanning tree T of a given graph G (with n vertices and m edges) and a new edge e = (u, v) of weight w that we will add to G. Give an efficient algorithm to find the minimum spanning tree of the graph G + e. Your algorithm should run in O(n) time to receive full credit.

Solution

We are interested into each path going from u to v. In this example there is the initial path u->t->v and the new one u->v. Now we can check which one is shorter and take this one. The rest of the tree isn’t affected by this.

6-7. (a) Let T be a minimum spanning tree of a weighted graph G. Construct a new graph G′ by adding a weight of k to every edge of G. Do the edges of T form a minimum spanning tree of G′? Prove the statement or give a counterexample.

(b) Let P = {s, . . . , t} describe a shortest weighted path between vertices s and t of a weighted graph G. Construct a new graph G′ by adding a weight of k to every edge of G. Does P describe a shortest path from s to t in G′? Prove the statement or give a counterexample.

Solution (a) The order of the weights aren’t affected by the addition therefore it still forms the MST: .

(b) No, see the counter example in the comments by Matus Goljer. Thanks for that!

6-23. Arbitrage is the use of discrepancies in currency-exchange rates to make a profit. For example, there may be a small window of time during which 1 U.S. dollar buys 0.75 British pounds, 1 British pound buys 2 Australian dollars, and 1 Australian dollar buys 0.70 U.S. dollars. At such a time, a smart trader can trade one U.S. dollar and end up with 0.75 × 2 × 0.7 = 1.05 U.S. dollars—a profit of 5%. Suppose that there are n currencies c1 , …, cn and an n × n table R of exchange rates, such that one unit of currency ci buys R[i,j] units of currency cj. Devise and analyze an algorithm to determine the maximum value of

R[c1, ci1] · R[ci1, ci2] · · · R[cik−1, cik] · R[cik, c1]

Solution Here’s the example as a graph.

The first problem is that maximum path algorithms don’t multiply the values the add them. This problem can be solved by using logarithms:

EDIT: Please see the entry in the comments. Thanks