问题标签 [spanning-tree]

假设有人找到了一种在 O(n^3) 时间内给定 CNF 布尔表达式创建图的方法，并且这个特殊图的任何生成树都将是 CNF 方程的解。

该场景似乎暗示某人已经找到了 SAT 问题的解决方案，并通过使用仅在 O(n^3) 时间内运行的小工具（减少）将 SAT 问题简化为生成树问题来解决 P=NP。

但是，如果他们的算法创建的图有 n！还是 2^n 个节点和边？

在这种情况下，虽然诸如 DFS 或 BFS 之类的生成树算法可以在节点/边的数量上以线性时间运行，但它不会在布尔表达式的输入数量上以多时间运行。所以这个人不会找到解决 SAT 问题的有效算法，因为运行完整的解决方案需要 n！评估的时间。

这个推理正确吗？

是否有一种算法可以找到无向图的生成树，以最小化连接到多个边的顶点数？

例如，给定一个 4 x 4 的网格图，我们想在左边找到一棵生成树（它有 7 个顶点连接到多个边）而不是右边的生成树（有 12 个）：

编辑：如果我们只考虑平面图（甚至只考虑网格图），这个问题会更简单吗？

我试图更改 cisco 交换机上的默认端口优先级，但由于检测到无效输入而出现错误。有人可以解释这段代码中的错误吗！

有一个有N个节点和N-1个连接链路的计算机网络。每个连接链接都有一个与之关联的时间。

我们得到了一个初始网络设置，如图所示。计算机通过双向链路连接。

网络时间定义为任何一对节点（计算机）之间的最大时间。

在给定的图中，网络时间为 25（节点 5、2、3、6）。

我们的任务是通过删除确切的一条边并在任何其他地方添加这条边来最大化这个网络时间。条件是：

1. 边缘的一端或两端都可以移除和添加。

2. 经此操作后的网络将是一棵生成树，每对顶点之间仅存在一条路径。

上述网络可以转换为下图，以实现最大网络时间为 25。 约束条件是：N，计算机（节点）的数量在 4 到 2000 之间。理想：执行时间在 1 秒内的最佳解决方案（C 和 C++）。

我在第三版算法介绍练习中遇到了这个问题。

因此，当最小生成树的最大边大于瓶颈树的最大边时，我的做法是试图通过剪切和粘贴参数来反驳这种情况。

但是，如果我删除最大的边缘，则没有必要存在将这些断开的部分连接成一个的边缘！

然后，我尝试使用 Kruksal 算法作为基础来证明它，因为最大边缘将所有其他边缘限制为小于或等于该最大边缘，但无法成功。

有什么帮助吗？

给定一个权重为 w(e) 的加权无向图 G(v,e)，找到边的集合，使得每对顶点 (u,v)∈G 是连通的（简而言之，spanning tree），并且选择的权重范围边是最小的（或者最小权重和最大权重之间的差是最小的）。

我尝试了贪婪的方法，其中根据权重对边进行排序，然后在排序后的数组中选择连续边之间权重差异最小的两条边（g[index = current_left]，g[index+1 = current_right]），随后我根据 (current_left,current_left- j) 或 (current_right,current_right+ j) 之间的最小差异向左或向右移动，其中j递增直到我们找到具有至少一个未访问顶点的边。

例如：

这里我们可以得到的最小范围是通过选择权重为 {2,3,5} 的边，范围是 3。

请指出一个建议算法失败的测试用例，并建议一种算法来寻找这种生成树。

编辑：

预期时间复杂度为 O(|E|log|E|) 其中 |E| 是边数。

所以以同样的方式这个层次结构

可以用这个 XML 表示

是否有一种数据格式（与 XML、JSON、CSV 等相同的类别）可以表示生成树（或图论中具有边/桥的点网络），如下所示： 以便以编程方式读取、解析，并像 XML 和其他一样被操纵（最终是为了测试它们的算法）？

我被要求编写一个算法，在图 G 中找到最小生成树，但条件是 G 的每个顶点都是生成树 T 中的一个叶子。如果图有两个以上的元素，这怎么可能？假设 G 包含顶点 a、b 和 c，生成树可能类似于 a--b--c，因此在这种情况下 b 不是叶子。

我不是在寻找算法的解决方案，我只想了解生成树如何完全由叶子组成。

这是问题的确切措辞

谢谢您的帮助

如何在图中找到不是最小值的生成树（如果可能）

我喜欢在有向图中（有时可能有循环）中找到最小生成树（甚至森林）。这里解释的有一些错误。Python中的这个算法是否有任何包/代码实际有效？