---
# System prepended metadata

title: 'Lab: Greed'

---

# Lab: Greed

## Problem 1: Fiber

1. The verticies represent the houses and buildings that the ISP needs to access. The edges are the roads oe fields that they are able to put lines down in. The weights are the distances from vertex to vertex. and the MST is the optimal layout of lines to attacht to each building with a minimum distance and cost.

![](https://i.imgur.com/cV8gbJo.jpg)




3. (A, C), (C, D), (D, F), (F, G),(G, H), (H, I), (I, E), (E, B), (I, J)

## Problem 2
a. (G, H), (F, G), (E, I), (A, C), (B, E), (D, F), (H, I), (C, D), (I, J)

b. There are a finite number of edges and you remove one edge each loop, so eventually you will run out of edges and the loop will terminate.

c. **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$.

*Proof*: We procede by induction. Our Induction Hypothesis states that on the kth iteration of Kruskal's Algorithm we have multiple minimum spanning trees. Our goal is to prove that on the k+1 iteration of Kruskal's Algorithm we will still have minimum spanning trees. We will prove by contradiction. Suppose that on the k+1 iteration we choose an edge that is not the least weight. By induction we already have multiple minimum spanning trees, however now that we have added an edge that is not the least weight we no longer have a minimum spanning tree, so it cannot be the case that choosing an edge that is not the minimum will result in a minimum spanning tree. Therefore we must chose the minimum weight edge to create a minimum spanning tree.