问题标签 [minimum-spanning-tree]

这就是问题，我承认这是一个家庭作业问题，我不是在寻找答案，而是我想知道我是否朝着正确的方向前进，如果我不善意地指出我正确的方向。

问题：证明如果加权图中没有两条边具有相同的权重，则与顶点 v 相关的权重最小的边包含在每个最小生成树 (MST) 中。

我的回答：给定一个顶点（V）和一个加权图（G），我们注意到∃（存在）和与V相关的边（E），这是加权最小的边。请注意，我们将有两个不同的顶点，它们将具有相同的最小加权边。这对我们来说不代表一个问题，如果一个顶点包含在最小生成树中，另一个将是。如果我们开始构建 MST，在一个实例中，最小加权边必须包含在 MST 中，因为必须包含具有最小边的一个（或两个）顶点才能获得 MST（因为定义MST 指出我们必须找到从根到所有顶点的最小路径）

我不太确定我的答案是否有效，你认为我如何证明它就足够了吗？

I am implementing the Christofides algorithm for getting a 3/2-approximation to TSP in graphs that obey the triangle inequality. I already have code for computing a minimum spanning tree using Kruskal's algorithm and an adjacency matrix.

Now, I want to implement Christofides by doubling the edges and finding an Euler tour and then shortcutting duplicate nodes. How do I perform this step? I'd like the algorithm and (optionally) C code.

Thanks!

全部，

我正在阅读所有对最短路径和矩阵乘法之间的关系。

考虑加权邻接矩阵与其自身的乘法 - 除了在这种情况下，我们将矩阵乘法中的乘法运算替换为加法，并将加法运算替换为最小化。请注意，加权邻接矩阵与其自身的乘积会返回一个矩阵，该矩阵包含任何节点对之间长度为 2 的最短路径。

从这个论点可以得出，A 的 n 次方包含所有最短路径。

问题1：

我的问题是，在图中，我们将在路径中的两个节点之间最多有 n-1 条边，作者在什么基础上讨论长度为“n”的路径？

以下幻灯片

www.infosun.fim.uni-passau.de/br/lehrstuhl/.../Westerheide2.PPT

在幻灯片 10 上，它如下所述。

问题 2：作者如何从 Eq 1 得出 Eq 2。

在 Cormen 等人关于算法介绍的书中，提到如下：

实际的最短路径权重 delta(i, j) 是多少？如果图不包含负权环，则所有最短路径都是简单的，因此最多包含 n - 1 条边。从顶点 i 到顶点 j 具有多于 n - 1 条边的路径的权重不能小于从 i 到 j 的最短路径。因此，实际的最短路径权重由下式给出

delta(i,j) = d(i,j) 幂 (n-1) = (i,j) 幂 (n) = (i,j) 幂 (n+1) = ...

问题 3：在上面的等式中，作者是如何得到 n，n+1 条边的，而我们最多有 n-1 条边，以及上面的分配是如何工作的？

谢谢！

我正在尝试使用 Mathematica 找到最小生成树，并且我想使用 Combinatorica 的 MinimumSpanningTree 函数。我正在使用以下代码。

其中 m 是一个矩阵。但是，MinimumSpanningTree 变成红色并且不起作用。输出给出

如何使 MinimumSpanningTree 工作？为什么会变红？

这是我正在努力解决的练习考试中的一个问题：

令 G = (V, E) 是一个加权无向连通图，具有正权重（您可以假设权重是不同的）。给定一个实数 r，定义子图 Gr = (V, {e in E | w(e) <= r})。例如，G0 没有边（显然是断开的），Ginfinity = G（假设是连通的）。问题是找到最小的 r 使得 Gr 是连通的。

描述通过重复应用 BFS 或 DFS 来解决问题的 O(mlogn) 时间算法。

真正的问题是在 O(mlogn) 中完成。这是我所拥有的：

这是一个惊人的 O(m^2 + mn)。将其降低到 O(mlogn) 的任何想法？谢谢！

我有一个无向且未加权（或所有边都加权为 1）的非循环图（G=VxE）。该图的一些节点被选为 sV（sV 是 V 的子集）。问题是，我想找到覆盖所有选定节点的子图。自然可以覆盖一些未选中的节点。但是不在所需子图上的节点受到限制。这些受限节点不应出现在解决方案子图中，除非它们仅位于两个选定节点之间的一条路径上。一个例子：

A、B、C、D 是节点，+ 表示包含边。对于此图，B 和 D 是选定的节点。我想要的这个例子的解决方案如下：子图由节点 B、C、D 和边 (B,C)、(C,D) * 组成。请注意，A 未按预期出现在子图中。什么样的方法可以帮助我找到这种类型的子图？感谢您的想法。

*(X,Y) 表示节点 X 和 Y 之间的边。

我读过 TSP 的近似值之一是执行以下操作： - 计算最小生成树 (MST) - 执行 MST 的 DFS

解决 TSP 的目标是每个顶点都被访问一次。旅行者从“A”点开始，他需要访问图表上的所有其他点，然后返回“A”点（有时，该子句不存在），确保每个点都被访问一次。

假设图 G 的 MST 'T' 如下：

这个 MST 的 DFS 是 ABCED。

我的问题是解决 TSP，我需要旅行者必须访问的所有城市（点）的列表。显然，在 MST 中不存在从“E”到“D”的路径。那么这如何解决问题呢？

假设您有一个有向图，其非负整数边长在 0 到 U - 1 范围内（包括端点）。计算该图的最小生成树的最快算法是什么？我们仍然可以使用现有的最小生成树算法，例如 Kruskal 算法 O(m log n)) 或 Prim 算法 (O(m + n log n))。但是，对于 U 很小的情况，我认为应该可以做得更好。

是否有任何算法可以与更传统的 MST 算法竞争，能够利用边缘长度被限制在某个范围内这一事实？

谢谢！

我正在为k-Minimum Spanning Tree 问题寻找整数 LP 形式化。

我的点子：

• x_ij = 1 表示树中有一条从 i 到 j 的边。
• y_i = 1 表示顶点 i 是树的一部分
• c_ij 是从 i 到 j 的边的成本

目标函数：所有 i,j 的 min sum(x_ij*c_ij)

约束：

1. 总和 y_i = k (1)
2. sum(x_ij) 对所有 j 和一些 i >= yi (2)
3. 所有 j 和一些 i >= yi (3) 的 sum(x_ji)
4. 2*x_ij <= yi+yj

(1) 确保 MST 中恰好有 k 个顶点。(2) 和 (3) 确保如果节点 i 在树中，则至少包含该节点的一条边在树中。(4) 表示如果树中 i 和 j 之间有一条边，那么顶点 i 和 j 也必须在树中。

不幸的是，这并没有按预期工作。有人知道我的错误吗？

我有一个对称的二维数组“myMSTdata[][]”，它表示一个最小生成树 MST，如果没有表示边缘权重的边或实值，则值为 0，现在我需要将此树分成两部分子树（part1，part2），其中切割标准是具有最大权重的边缘。然后不断地对较大尺寸的子树（即节点数较多的子树）进行分区，直到较大尺寸子树中剩余的节点数为K。