23-1 Second-best minimum spanning tree

Let \(G = (V, E)\) be an undirected, connected graph whose weight function is \(w: E \rightarrow \mathbb R\), and suppose that \(|E| \ge |V|\) and all edge weights are distinct.

We define a second-best minimum spanning tree as follows. Let \(\mathcal T\) be the set of all spanning trees of \(G\), and let \(T'\) be a minimum spanning tree of \(G\). Then a second-best minimum spanning tree is a spanning tree \(T\) such that \(W(T) = \min_{T'' \in \mathcal T - \\{T'\\}} \\{w(T'')\\}\).

a. Show that the minimum spanning tree is unique, but that the second-best minimum spanning tree need not be unique.

b. Let \(T\) be the minimum spanning tree of \(G\). Prove that \(G\) contains edges \((u, v) \in T\) and \((x, y) \notin T\) such that \(T - \\{(u, v)\\} \cup \\{(x, y)\\}\) is a second-best minimum spanning tree of \(G\).

c. Let \(T\) be a spanning tree of \(G\) and, for any two vertices \(u, v \in V\), let \(max[u, v]\) denote an edge of maximum weight on the unique simple path between \(u\) and \(v\) in \(T\). Describe an \(O(V^2)\)-time algorithm that, given \(T\), computes \(max[u, v]\) for all \(u, v \in V\).

d. Give an efficient algorithm to compute the second-best minimum spanning tree of \(G\).

a. To see that the second best minimum spanning tree need not be unique, we consider the following example graph on four vertices. Suppose the vertices are \(\\{a, b, c, d\\}\), and the edge weights are as follows:

Then, the minimum spanning tree has weight \(7\), but there are two spanning trees of the second best weight, \(8\).

b. We are trying to show that there is a single edge swap that can demote our minimum spanning tree to a second best minimum spanning tree. In obtaining the second best minimum spanning tree, there must be some cut of a single vertex away from the rest for which the edge that is added is not light, otherwise, we would find the minimum spanning tree, not the second best minimum spanning tree. Call the edge that is selected for that cut for the second best minimum spanning tree \((x, y)\). Now, consider the same cut, except look at the edge that was selected when obtaining \(T\), call it \((u, v)\). Then, we have that if consider \(T - \\{(u, v)\\} \cup \\{(x, y)\\}\), it will be a second best minimum spanning tree. This is because if the second best minimum spanning tree also selected a non-light edge for another cut, it would end up more expensive than all the minimum spanning trees. This means that we need for every cut other than the one that the selected edge was light. This means that the choices all align with what the minimum spanning tree was.

c. We give here a dynamic programming solution. Suppose that we want to find it for \((u, v)\). First, we will identify the vertex \(x\) that occurs immediately after \(u\) on the simple path from \(u\) to \(v\). We will then make \(\max[u, v]\) equal to the max of \(w((u, x))\) and \(\max[w, v]\). Lastly, we just consider the case that \(u\) and \(v\) are adjacent, in which case the maximum weight edge is just the single edge between the two. If we can find \(x\) in constant time, then we will have the whole dynamic program running in time \(O(V^2)\), since that's the size of the table that's being built up. To find \(x\) in constant time, we preprocess the tree. We first pick an arbitrary root. Then, we do the preprocessing for Tarjan's off-line least common ancestors algorithm (See problem 21-3). This takes time just a little more than linear, \(O(|V|\alpha(|V|))\). Once we've computed all the least common ancestors, we can just look up that result at some point later in constant time. Then, to find the \(w\) that we should pick, we first see if \(u = \text{LCA}(u, v)\) if it does not, then we just pick the parent of \(u\) in the tree. If it does, then we flip the question on its head and try to compute \(\max[v, u]\), we are guaranteed to not have this situation of \(v = \text{LCA}(v, u)\) because we know that \(u\) is an ancestor of \(v\).

d. We provide here an algorithm that takes time \(O(V^2)\) and leave open if there exists a linear time solution, that is a \(O(E + V)\) time solution. First, we find a minimum spanning tree in time \(O(E + V \lg(V))\), which is in \(O(V^2)\). Then, using the algorithm from part c, we find the double array max. Then, we take a running minimum over all pairs of vertices \(u\), \(v\), of the value of \(w(u, v) - \max[u, v]\). If there is no edge between \(u\) and \(v\), we think of the weight being infinite. Then, for the pair that resulted in the minimum value of this difference, we add in that edge and remove from the minimum spanning tree, an edge that is in the path from \(u\) to \(v\) that has weight \(\max[u, v]\).

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用