(稀疏图的最小生成树) 对于非常稀疏的图G=(V, E)来说， 我们可以对Prim算法进行进一-步改善，改善后的时间将优于使用斐波那契堆时的O(E+V lgV)的运行时间。改善所用的方法就是对图G进行预处理来减少结点的数量，然后在减少结点数量后的图G,上运行Prim算法。具体来说，对于每个结点u,我们选择与结点u邻接的边中最小权重的边(u,v)，将其加入到正在构建的最小生成树里。然后对所有选择的边进行收缩。不过，我们不是一条一条地收缩每条边，而是首先找出连接到同一个新结点的结点集合。然后创建一个新的图，这个新的图就如每次收缩这样一条边所得出的一样，但我们是通过“重新命名”来实现。重新命名是根据每条边的端点所在的结点集合来进行。原始图中的多条边可能被重命名为同样的名。在这种情况下，重名的边中只有一条边留下，这条边对应原始边中最小权重的边。
在初始时，我们把将要构建的最小生成树T设为空，对于每条边(u, v)∈E,对其属性进行如下的初始化操作: (u, v).orig= =(u, v), (u, v).c=w(u，v)。 我们使用orig属性来引用原始图中与收缩后的图的边相关的边。属性c记录边的权重， 随着边的收缩，我们根据上面选择边权重的方法来更新这个属性。下面的MST-REDUCE算法以图G和树T作为输入，返回一个收缩后的图G'和更新后的属性orig'与c'。该算法同时选出图G中的边来构成最小生成树T。
MST-REDUCE(G,T) 1for each v EG. V 2v. mark= FALSE 3MAKE- SET(v) 4 for each uG.V 5if u. mark== FALSE 6choose v
12for each(x,y)
G'. E 16 G'. E=G. E U (u,v) 17 (u,v). orig' = (x,y). orig 18 (u,v).c= (x,y).c 19 else if(x.y)
(u,v). c 20 (u,v). orig' = (x,y). orig 21 (u,v).c'=(x,y).c 22 construct adjacency lists G' :Adj for G' 23 return G' and T
a.设T为算法MST-REDUCE所返回的边的集合，设A为调用MST-Prim(G', c', r)所生成的图G'的最小生成树， 这里c'是G'.E中边的权重属性，r是G'. V中的任意结点。证明: TU{(x, y).orig' :(x, y)∈A}是图G的一-棵最小生成树。
b.证明: G'.V|≤lV|/2。
c.请说明要如何实现算法MST-REDUCE,才能让其运行时间为O(E)。 (提示:使用简单的数据结构。)
d.假定运行MST-REDUCE算法k次，使用前一次输出的图G'作为下一次的输人图G,并在T中将边累积起来。证明:算法运行k次的总时间为O(kE)。
e.假定在运行MST-REDUCE算法k次后，就如在本题的(d)部分那样，我们通过调用算法MST-Prim(G'，c', r)来运行Prim算法， 这里图G'是最后一个阶段所返回的图，其权重属性为c'，r是G'. V中的任意结点。请说明应当如何选择k,才能使得整体的运行时间为O(ElglgV)。并证明你所选择的k使得总体的渐近运行时间为最短。
f.对于|E|的何种取值(以|V|为单位来度量)，这种带预处理的Prim算法的时间在渐近意义上要优于没有预处理的Prim算法的运行时间?
d.假定运行MST-REDUCE算法k次，使用前一次输出的图G'作为下一次的输人图G,并在T中将边累积起来。证明:算法运行k次的总时间为O(kE)。
e.假定在运行MST-REDUCE算法k次后，就如在本题的(d)部分那样，我们通过调用算法MST-Prim(G'，c', r)来运行Prim算法， 这里图G'是最后一个阶段所返回的图，其权重属性为c'，r是G'. V中的任意结点。请说明应当如何选择k,才能使得整体的运行时间为O(ElglgV)。并证明你所选择的k使得总体的渐近运行时间为最短。
f.对于|E|的何种取值(以|V|为单位来度量)，这种带预处理的Prim算法的时间在渐近意义上要优于没有预处理的Prim算法的运行时间?
