这个最小生成树算法正确吗?

如果两个周期重叠会发生什么?哪一个先去掉最长的边?两个循环之间是否共享每个循环的最长边有关系吗?

例如:

V = { a, b, c, d }
E = { (a,b,1), (b,c,2), (c,a,4), (b,d,9), (d,a,3) }

有一个a->b->c->a循环和一个a->b->d->a循环

@shrughes.blogspot.com网站:

我不知道删除所有的,除了两个-我已经勾勒出各种运行的算法,并假设并行运行可能删除一个边缘不止一次,我无法找到一个情况下,我离开了生成树。我不知道它是否是最小的。

要使其工作,您必须详细说明如何查找所有循环,显然没有任何迭代构造,因为这是一项非常重要的任务。我不确定那是否可能。如果你真的想找到一个不使用迭代构造的mst算法,看看 Prim's 或 Kruskal's 算法,看看你是否可以修改这些以满足你的需要。

同样,递归在这个理论架构中被禁止了吗?如果是这样的话,可能实际上不可能在图上找到mst,因为您根本没有办法检查图上的每个顶点/边。

我不知道是否有效,但不管怎样 你的算法甚至不值得实现 . 发现 全部的 周期将是致命的巨大瓶颈。如果没有迭代也不可能做到这一点。为什么不实现一些标准算法呢? Prim's .

你的算法不是很清楚。如果您有一个完整的图,那么您的算法在第一步中似乎需要除去除两个最小元素之外的所有元素。同时,列出 全部的 图中的循环可能需要指数时间。

详述:

在一个有n个节点和每对节点之间的边的图中,如果我的数学正确的话,有n个节点!/(2K(N-K)!)大小为k的圈,如果将一个圈计算为k个节点和k个边的子图,而每个节点的阶数为2。

@tynan这个系统可以被描述为一个描述分类的规则系统。”如果事物在B中而不是C中,则为A类;“与Z中的节点连接的节点也在Z中”,“M中的每个类别都连接到节点N,并且具有“子”类别,对于与N连接的每个节点,也为M”。比这个稍微复杂一点。(我已经证明,通过创建不稳定的规则,您可以对一个旋转机器建模,但这不重要。)它不能显式地定义迭代或递归,但可以使用第二个和第三个规则对递归数据进行操作。

@marcin,假设有无限数量的处理器。证明程序可以在o(n^2)中运行是很简单的,因为n是最长的周期。有了更好的数据结构,这可以简化为o(n*o(set lookup function)),我可以设想硬件(量子计算机?)它可以在恒定时间内计算所有循环。给出mst问题的o(1)解。

这个 Reverse-delete algorithm 似乎提供了正确性的部分证明(所提出的算法不会产生非最小生成树),这是通过论证mt算法将移除逆删除算法将要移除的每一条边而得出的。不过,我不知道如何证明我的算法不会删除超过该算法。

嗯…

好的,这是一个完成正确性证明的尝试。与反向删除算法类似,我们知道将删除足够多的边。剩下的是显示不会有太多的边被移除。

删除到多条边可以描述为删除图节点的二进制分区边之间的所有边。但是,一个循环中只有边被移除,因此,要移除分区之间的所有边,需要有一个返回路径来完成该循环。如果我们只考虑分区之间的边,那么算法最多可以移除每对边中较大的边,这永远无法移除最小的桥接边。因此,对于任意的二进制分区,算法不能切断边之间的所有链接。

剩下的是显示这扩展到了双向分区。