Jak*_*ake 9 algorithm graph kruskals-algorithm
设G =(V,E)为无向图.如果G的每个循环在F中具有至少一个边缘,则边集的F FE被称为 反馈边集.
(a)假设G未加权.设计一种有效的算法来查找最小尺寸的反馈边集.
(b)假设G是具有正边权重的加权无向图.设计一种有效的算法来找到最小权重反馈边集.
我的解决方案(需要建议):
a)最小尺寸反馈边集:由于图是未加权的,我们可以使用DFS.我们像往常一样从任何顶点开始DFS.当我们遇到后边缘时,我们将其插入一组反馈边缘.当DFS完成时,该集将是答案.
b)最小权重反馈边集:由于图是加权的,我们可以使用Kruskal.但Kruskal通常以最小重量的边缘开始.如果我们可以否定所有边权重,然后运行Kruskal,每当我们在相同组件的顶点之间获得边缘时,我们可以将其保存在反馈边集中.最后,否定边权重.我建议否定边权重的原因是因为我们需要最小权重反馈集.对于负重,Kruskal将从具有最小重量(实际上最大)的边缘开始,并且将发现具有较小重量的相同组件的边缘.
有人能说出这个解决方案是否正确吗？
小智 5
是的,您的解决方案是正确的.最小权重反馈边缘集的无向图是最大权重跨越森林的补充.所有跨越森林都具有相同的基数,因此在未加权的情况下,任何跨越森林(由DFS找到)都可以.(证明草图:拟阵.)
反馈弧设置确实是NP难的,但这是无向的情况.
要找到具有正权重的加权有向图中的最小权重反馈边集：
通过否定权重，观察到它相当于找到最大权重反馈边集。要找到最大权重反馈边集，请使用 Prim 或 Kruskal 算法构建 MST。然后取该 MST 的补集。
为什么它有效？这是基于以下观察：
当且仅当存在一个循环，并且该边相对于该循环中所有其他边具有最大权重时，该边不在任何 MST 中。 或者，换句话说，当且仅当对于该边所属的每个周期，一条边在某个 MST 中，它不比该周期中的所有其他边具有最大权重。
事实上，假设我们有一个最大权重反馈边集，其中的一条边存在一个包含该边和另一条具有更大权重的边的循环，那么用该另一条边替换该边将提供更大权重的反馈边集。
为了完整性，观察结果的证明：
<=) 假设一条边在一个循环中具有最大权重。如果它在某个 MST 中，则用该周期中的另一条边替换该边将提供权重更小的 MST。
=>) 假设对于给定边所属的每个循环，该循环中都存在具有更大权重的边。如果它不在任何 MST 中，则将该边添加到 MST 中将导致 MST 中出现循环。然后从该循环中删除最大权重的边（与给定边不同）将提供具有较小权重的 MST（并包含该给定边）。
小智 -2
您的解决方案 A）将不起作用，因为您没有提供任何逻辑来决定边缘是否具有“后”属性。
你的解决方案 B) 不起作用，因为 Kruskal 不寻找反馈集，而是寻找最小权重覆盖树。K4 图是说明为什么最小加权树不一定包含反馈边集的一个很好的例子。