最小生成树问题是取一个连接的加权图，并在保持图形连通的情况下找到其边的子集具有最低的总权重（并因此导致非循环图）。这个最小生成树算法是否正确？
我正在考虑的算法是：
这个版本的动力是一个限制在没有任何迭代构造的“规则满意度”的环境。它也可能适用于疯狂并行的硬件（即一个系统，在这个系统中，你期望有几倍的并行度，然后是周期）。
编辑：
以上是在无状态庄园完成（未在任何周期最大边缘选择了所有边缘/保持/忽略，所有其他被移除）。
如果两个周期重叠会发生什么？哪一个最长边被首先移除？这两个周期之间是否共享每个周期的最长边缘有关系吗？
例如：
V = { a, b, c, d }
E = { (a,b,1), (b,c,2), (c,a,4), (b,d,9), (d,a,3) }
有一个一个 - “乙 - ”ç - >一个周期，和一个 - “乙 - > d - >一
你的算法是不是很明确规定。如果你有一个完整的图，你的算法似乎需要在第一步中除去两个最小元素。此外，列出全部图中的周期可能需要指数时间。
精化：
在具有n个节点的曲线图，每对节点之间的边缘，还有，如果我有我的数学右，正/大小为k的周期，！（2K（NK）！）如果您要统计一个周期为k的节点和k的一些子图，每个节点有度边2.
@ shrughes.blogspot.com：
我不知道如何移除所有而是两个 - 我我一直在勾画出算法的各种运行过程，并假设并行运行可能会多次删除边缘，我无法找到没有生成树的情况。不知道它是否微乎其微。
@Tynan该系统可以描述（有点过于简化）作为描述分类的规则系统。 “事物属于A类，如果它们在B中但不在C中”，“连接到Z中的节点的节点也在Z中”，“M中的每个类别连接到节点N并具有'子类别'，也在M连接到N“的每个节点。这比这稍微复杂一些。 （我已经证明，通过创建不稳定的规则，您可以对一个车床进行建模，但这并不重要）。它不能明确定义迭代或递归，但可以使用第二个和第三个规则的递归数据进行操作。
@Marcin，假设有无限数量的处理器。这是微不足道的，表明该程序可以在O（n^2）中运行，因为n是最长的循环。有了更好的数据结构，这可以减少到O（n * O（设置查找函数）），我可以设想硬件（量子计算机？）可以在恒定时间内评估所有周期。给MST问题提供O（1）解决方案。
Reverse-delete algorithm似乎提供了正确性的部分证明（即所提出的算法不会生成非最小生成树），这是通过论证mt算法将删除反向删除算法将会的每条边而得出的。不过，我不知道如何显示我的算法不会删除更多的算法。
Hhmm ....
好的，这是一个尝试完成正确性的证明。通过类比反向删除算法，我们知道有足够的边将被删除。剩下的就是证明不会去除很多边缘。
移除到许多边可以描述为去除图节点的二进制分区的边之间的所有边。然而，只有一个周期中的边缘被删除，因此，对于要移除的分区之间的所有边缘，需要有一个返回路径来完成周期。如果我们只考虑分区之间的边缘，那么该算法至多可以去除每对边中较大的一个，这永远不会移除最小的桥接边。因此，对于任何任意的二进制分区，算法不能切断边之间的所有链路。
剩下的是证明这扩展到了> 2分区。
其中一个重点是在系统中实现MST的概念，如'first/second'和'before/after'不存在。 – BCS 2011-02-08 17:04:59