最小生成树图

Question

假设我选择V(H)={a,e,f}和e(H)={ae,af,fe}

E12={ab,bc,bd,ed} 
E23={eg,ef} E31={fc,fd}                            
c'(ae)=min{c(ab),c(bc),c(bd),c(ed)}=4
c'(af)=min{c(fc),c(fd)}=9
c'(fe)=min{c(eg),c(ef)}=8

现在，对于每条边e∈e(H)，我们用e'记下了（来自原始图G的）
达到这个最小值的边。所以E'={bc,df,eg},因为bc=4,df=9,eg=8,是连接我的元件的最小边。我在H中有一个相对于代价函数C′的最小生成树，而a′是这棵树的边集。

但是我的A'的边和E'的没有一条是一样的。

Answer 1

看来你在实现Boruvka的算法。如果你看一下记号，它说如果在原图G中有一对相邻的节点x∈C₁和y∈C₂,那么从一个新节点V_{C1到一个新节点VC2就有一条边。换句话说，如果两个新节点在G'中对应的连通分量在G中相邻，那么两个新节点之间就有一条边。在它们之间运行的边的代价是在原图G中这些CC之间运行的任何边的代价中最低的。}