Problem 1: Fiber

When a telecommunications company like Mahaska Communication Group provides fiber access, they must lay down fiber-optic cables so that they can reach all of the houses in the town. Due to geography, zoning laws, etc., they are constrained to laying down fiber along fixed paths such as roads or clear fields. Naturally, some paths are more expensive to lay down fiber along than others which leads to a natural question: what is the cheapest fiber network the company can lay down that services all of the houses in a town.

1. Describe how this problem relates to the minimum spanning tree problem. In particular, identify what vertices, edges, weights, and a MST correspond to.

2. Consider a town with 10 houses labeled \(A\) through \(J\). The telecommunications company has identified that they could lay down fiber between the following houses for the following costs:

   • \((A, B), 8\)
   • \((A, C), 3\)
   • \((B, C), 11\)
   • \((B, D), 5\)
   • \((B, E), 4\)
   • \((B, F), 6\)
   • \((C, D), 7\)
   • \((C, G), 13\)
   • \((D, F), 5\)
   • \((E, F), 7\)
   • \((E, I), 3\)
   • \((F, G), 2\)
   • \((F, H), 4\)
   • \((F, I), 5\)
   • \((G, H), 1\)
   • \((H, I), 6\)
   • \((I, J), 22\)

   Draw a graph of this situation according to your answer to the previous part.

3. Use Prim’s algorithm to find the cheapest fiber network for this town. List the sequence of edges you add to the MST as you execute Prim’s and give the final cost of the MST.

Problem 2: Alternatives

An alternative algorithm for discovering a minimum weight spanning tree is Kruskal’s algorithm. Kruskal’s proceeds on a graph \(G = (V, E)\) as follows:

• Initially, create a set of trees \(F\), i.e., a forest, composed from the different vertices from \(V\). Each tree is simply a vertex drawn from \(v\) with no connecting edges. Thus, the number of trees is the number of vertices in \(V\).
• While the forest does not contain a single tree:
  • Remove the minimum weight edge from \(G\). If that edge would connect two different trees from \(F\), then add it to the forest, joining two trees together in \(F\).

At the conclusion of Kruskal’s algorithm, \(F\) contains a single tree that is a MST for \(G\).

1. Execute Kruskal’s on the graph from problem 1. List the sequence of edges you add to the MST as you execute Kruskal’s and give the final cost of the MST.

2. Observe that Kruskal’s algorithm loops until the forest contains a single tree. Consequently, it is conceivable that, perhaps, Kruskal’s algorithm could go into an infinite loop. Argue in a few sentences that this is not the case, i.e., argue why Kruskal’s always terminates.

3. In the reading, we saw how a greedy exchange argument can be made to show that Prim’s produces a MST. Let’s adapt the argument to show the following property of Kruskal’s:

   Claim (Minimality of Kruskal’s Algorithm): Let \(G = (V, E)\) be an undirected graph with weight function \(h : E \times \mathbb{N}\) where each edge has a unique weight. Let \(E_k \subseteq E\) be the set of edges chosen by Kruskal’s algorithm on the \(k\)th iteration of the algorithm. Then \(E_k\) is a subset of the edges of the minimum spanning tree of \(G\).

   To do this, argue by induction on the number of iterations of the algorithm \(k\). In the inductive case, make a greedy exchange argument that not choosing the minimal weight edge leads to a provably worse spanning tree. Use this picture to guide your reasoning:

      T3 ?? T4
     /        \
    /          \
   T1 -------- T2

   Here, suppose the edge connecting \(T_1\) and \(T_2\) is the minimal weight edge that we would choose. But instead, in our greedy exchange/proof by contradiction, we assume that this is not chosen and instead some other edge, say \(T_1\) to \(T_3\) is chosen. In the spanning tree that is eventually created by that choice, suppose that we finally connect to \(T_2\) by way of some other tree, say \(T_4\).