问题标签 [spanning-tree]

是否有一种多项式算法可以找到无向网格图的生成树，从而最小化树中的匝数？转弯是当有两条边连接到一个顶点时，它们具有垂直的方向。

在这个问题中，我们在网格中有任意一组单元格，它们形成了一个连通图（不仅考虑了矩形）。

例如，给定一个 4 x 4 的网格图（见下图），我们希望在右侧（有 6 圈）而不是在左侧（有 14 圈）找到一棵生成树：

关于近似算法的想法也可能有用。

我有加权无向图。我需要以尽可能小的成本找到生成树，以便 A 点和 B 点之间的距离尽可能低。例如，我有这个图：graph。A 和 B 之间的最小距离为 2。最小生成树看起来像这样。但这会使 A 和 B 之间的距离 = 3。

现在我正在这样做：

1. 使用 BFS 查找图中 AB 之间的距离。
2. 使用 DFS 从步骤 1 中找到 AB 之间的所有路径。
3. 从步骤 2 中的每条路径生成生成树。
4. 比较它们并获得最小的一个。

一切都很好，直到我得到 AB 距离 = 12 的图表。第二步然后花费太多时间。有没有更快的方法来做到这一点？谢谢。

我有一个无向图，我想迭代地删除每个串行边并用新边替换它。新边的权重代表生成树的数量，计算如下：T_new = (1/a+b) * T_old, 其中a和b是删除边的权重，T_new 是当前迭代中生成树的数量，T_old 是前一次迭代中生成树的数量。这个方程随着图形的变化而迭代地变化，所以如果我们有 4 次迭代，我们将有 4 个方程，每个方程都是前一个方程。一旦图形不再有串行边，我们就会停止。如果最终图由 1 条边组成，则该边的权重是最后一条 T_new，我们将有一个数值 T-old。否则，就 T_new 而言，我们应该有 T_old。这是一个附加的图像，解释了我所说的，以防它没有得到很好的解释。这是我描述问题的代码部分：

** PS：我只需要方程在每次迭代中发生变化的部分，而不是删除和添加新边等要做的事情。这是一个例子：**

如果图 Graph 的某个节点 B 存在边 AB 或 BA，我遇到了这个 cut，它应该返回 true。

问题是我不明白为什么删除这个切口会对返回的解决方案产生任何影响。

据我了解，在 Prolog 语句末尾进行剪切的唯一用途是当有另一个同名的语句 [another node(...)] 如果第一个成功时我们不想被调用. 一个例子是一个函数，它接受 X 和 Y 并返回较大的一个作为第三个参数。

但是，没有其他名为 node(...) 的语句，所以我看不到剪切如何影响解决方案。

这是我的代码。它应该找到一棵生成树。这里有详细解释。编译器是 Linux 上的 SWI-Prolog 7.6.4。

未删减返回的解决方案（正确）

使用 cut 返回的解决方案（不正确）

我需要从节点获取生成树。关系具有数字 update_time 属性。生成树应该只包含最近的关系（update_time >= period_start）。我尝试使用 apoc.path 程序，但似乎它们不允许根据关系属性进行过滤，只能根据关系类型进行过滤。

是否可以使用关系属性运行 apoc.path.spanningTree() ，如果没有，那么最佳解决方案是什么？

我想检查我对生成树（对于无向图和连通图）的理解是否正确。

从，我在网上读到的。生成树是图的子集，它包含图的相同数量的顶点，但它的边数最少。一个图也可以有许多不同的生成树。

我已经看过一些生成树及其图表的插图，所以我试图提出我自己的例子。

房子图

所以这张图片显示了一个房子形状的图表。如果我要去掉那个房子图中的一条边，这将是一棵生成树，因为从一个节点到另一个节点有一条替代路径。

如果我确保两个节点之间仍然存在一条路径，我也可能会摆脱两条边。

我在这个假设中正确吗？

编写一个程序来模拟给定数量的玩家之间的位置游戏，例如连接游戏。

在游戏开始时，棋盘包含具有 n 个顶点的完整图的所有边（所有对由从 1 到 n 的不同数字组成）。每个玩家从棋盘中连续提取边，并且必须用它们创建初始完整图的生成树。当玩家制作生成树（在这种情况下，获胜者获得 n 分，其他人获得 0 分）或从图中删除所有边时（在这种情况下，每个玩家获得的点数等于它们最大的部分树的顶点）。我必须考虑玩家随机选择边缘以及“聪明”玩家应该尝试扩展其最大树同时不允许其他人创建生成树的情况。

我试图说明该陈述是否正确：
在 DFS/BFS 期间，第一次访问的节点形成一棵生成树，无论您使用 DFS 还是 BFS，它都具有相同数量的边。
这是真的吗？谢谢！

假设 e 是加权图中的一条边，它与顶点 v 相关，使得 e 的权重不超过与 v 相关的任何其他边的权重。证明存在包含该边的最小生成树。

1. 编写一个算法来找到具有最大叶子数的生成树。
2. 编写一个算法以找到具有最少节点数的生成树。

我还无法为以下问题提出解决方案。

对于第一部分，我的想法是找到具有最高度数的顶点并将其放置在倒数第二层中，以便最后一层获得最大数量的叶子。