9 13 Each vertex in this graph represents a city, and edge weights represent the cost (in millions of dollars) of running a high-capacity fiber optic cable between the cities. For example, it costs $2 million to run a cable between City A and City B a) (2 pts) A set of cities is considered to be fully connected if there exists a path between any two cities in the set. What is the minimum number of cables that must be run in order for the set of all cities in the graph to be fully connected? b) (6 pts) Imagine you are on the planning board that will decide which cables to run, and your goal is to fully connect the cities at minimum cost. You decide to use Kruskal's Algorithm on the above graph to choose the set of cables (i.e. edges). You break ties by the edge with the alphabetically-lowest endpoint, so that an edge CA would be chosen before an edge BD in the event of a tie i) (2 pts) Which edge is chosen first by Kruskal's Algorithm? i) (2 pts) Which edge is chosen last? ii) (2 pts) What is the total cost of connecting all cities? million dollars iv) (2 pts) Suppose the volume of network traffic between Cities A and E is high enough that a direct cable between them is justified even if it ends up costing more overall. If the edge between A and E must be selected, what is the new minimum total cost of connecting all cities? million dollars