Problem $1(20$ points$)$

a$)(5$ points$)$ For the graph shown, run Prim's algorithm starting at node $E$ and write the edges in the order they appear in the minimum spanning tree. Whenever you have a choice of nodes to pick from the queue, always pick the one that is alphabetically first. Draw the resulting tree and its cost.

b$)(5$ points$)$ Run Kruskal's algorithm and write the edges in the order they appear in the minimum spanning tree. Draw the resulting tree and its cost. If two edges have the same weight, pick first the one containing the smallest letter.

c$)(5$ pts$)$ You are given a weighted graph $G(V,E)$ modelling a computer network in which some of the nodes are characterized as faulty $($as they fail from time to time$).$ The set of faulty nodes is denoted by $F.$ You want to compute the best spanning tree connecting the nodes of $G,$ however you don't want the faulty nodes to be interior nodes $($since the tree will be disconnected if any of them fails$).$ Describe a general algorithm for doing this.

Hint: Remove the faulty nodes and find a tree for the remaining ones. Then find a way to include the faulty nodes as leaves.

d$)(5$ pts$)$ Apply your algorithm for part $($c$)$ for the graph shown on the top in which the faulty nodes are $,G$ and draw the minimum spanning tree, if it exists. For full credit, illustrate all the steps of your algorithm, i$.$e$.$ do not just draw the final spanning tree. What is the total cost of this tree?