Limited access

Upgrade to access all content for this subject

You are given an algorithm that when given a graph, iteratively chooses the $n - 1$ edges of the graph, where $n$ is the number of nodes in the graph, such that the edges are chosen in order of increasing cost but an edge which creates a cycle in the graph with the previously chosen edges is not selected. The list of selected edges is then returned by the algorithm.

Which of the following problems can be solved using this algorithm?

A

You are given a set of classes, some of which overlap with each other. Given a graph where the nodes are the classes and an edge exists between two classes if they overlap with each other, find a schedule with the maximum number of classes that do not overlap with each other.

B

You are given a set of locations, some of which have wireless connections to each other and are separated by positive, distinct distances. Given a graph where the nodes are the locations and the edges are the connections with values equal to their distance, find a connected network of minimum cost.

C

You are given a set of computers, some of which are connected by wires of positive, distinct lengths. Given a graph where the nodes are the computers and the edges are the wires with values equal to their length, find a connected network that costs the least while minimizing congestion on the network.

D

You are given a fluid network of pipes of certain capacities and junctures that connect multiple pipes together. Given a graph where the nodes are the junctures and the edges are the pipes that connect the junctures, find the maximum flow of this fluid network.

E

None of these problems can be solved using this algorithm.

Select an assignment template