Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 163/265--Graph Algorithms
Please answer the following questions, each of which is worth 10 points.
1. (CS 163 students only) Using the graph at the following website, make three copies of this graph and darken in each edge of the minimum spanning tree (MST) for each copy (the MST’s will all be the same):
https://i.stack.imgur.com/kJF5K.png
Number the MST edges of the first graph with the order that they would be added in the Prim-Jarnik algorithm. Number the MST edges of the second graph with the order that they would be added in Kruskal’s algorithm. Number the MST edges of the third graph with the round number in which they would be added in Baruvka’s algorithm.
2. Suppose G is a weighted, connected, undirected, simple graph and e is a largest-weight edge in G. Prove or disprove the claim that there is no minimum spanning tree of G that contains e.
3. Suppose you are a manager in the IT department for the government of a corrupt dictator, who has a collection of computers that need to be connected together to create a communication network for his spies. You are given a weighted graph, G, such that each vertex in G is one of these computers and each edge in G is a pair of computers that could be connected with a communication line. It is your job to decide how to connect the computers. Suppose now that the CIA has approached you and is willing to pay you various amounts of money for you to choose some of these edges to belong to this network (presumably so that they can spy on the dictator). Thus, for you, the weight of each edge in G is the amount of money, in U.S. dollars, that the CIA will pay you for using that edge in the communication network. Describe an efficient algorithm, therefore, for finding a maximum spanning tree in G, which would maximize the money you can get from the CIA for connecting the dictator’s computers in a spanning tree. What is the running time of your algorithm?
4. Imagine that you just joined a company, GT&T, which set up its computer network a year ago for linking together its n offices spread across the globe. You have reviewed the work done at that time, and you note that they modeled their network as a connected, undirected graph, G, with n vertices, one for each office, and m edges, one for each possible connection. Furthermore, you note that they gave a weight, w(e), for each edge in G that was equal to the annual rent that it costs to use that edge for communication purposes, and then they computed a minimum spanning tree, T, for G, to decide which of the m edges in G to lease. Suppose now that it is time renew the leases for connecting the vertices in G and you notice that the rent for one of the connections not used in T has gone down. That is, the weight, w(e), of an edge in G that is not in T has been reduced. Describe an O(n + m)-time algorithm to update T to find a new minimum spanning, T 0 , for G given the change in weight for the edge e.
5. Suppose you are given a diagram of a telephone network, which is a graph G whose vertices represent switching centers, and whose edges represent communication lines between two centers. The edges are marked by their bandwidth, that is, the maximum speed, in bits per second, that information can be transmitted along that communication line. The bandwidth of a path in G is the bandwidth of its lowest-bandwidth edge. Give an algorithm that, given a diagram and two switching centers a and b, will output the maximum bandwidth of a path between a and b. What is the running time of your algorithm?
6. (CS 265 students only) Suppose you are given a weighted graph, G, with n vertices and m edges, such that the weight of each edge in G is a real number chosen independently at random from the interval [0, 1]. Show that the expected running time of the Prim-Jarnik algorithm on G is O(n log2 n + m), assuming the priority queue, Q, is implemented with a heap.