问题标签 [spanning-tree]

如果我应该证明或寻找反例，请提供任何提示，至少要知道该往哪个方向走......

考虑以下两张图：

和顶点的权重函数w: (E1 \untion E2) -> R

和的2 个最小生成树T1, T2。G1G1

我们定义一个新图：G(V, E1 \untion E2)

说T新图中总是有一个最小生成树G（使用相同的w函数）是真的吗，这样T 的所有边都来自T1或T2？

如果每个 T 都有一条不包含在 T1 或 T2 中的边 e，则该声明是错误的，现在在 G1 中，我们可以删除这条边 (e)，T1 的问题就解决了。但是我也不能从 G2 中删除边 e，这意味着我必须接受它并且声明是正确的，我错了吗？

注：无需详细解答，只求知道什么是对的，自己深思熟虑。

我知道解决这个问题的蛮力方法可以给出：

1. 遍历所有边
2. 取一个集合（或列表）（假设 s）
3. 如果将边添加到 s 不会形成循环，则将边添加到 s
4. 如果迭代在所有边上完成，则结束。

但我想要一个有效的解决方案（时间+空间）来解决这个问题。

所以，任何帮助将不胜感激............

我有以下设置

1. 人是组织的一部分
2. 人出席会议
3. 会议在一个地点举行

• 多人可以参加会议
• 多个人可以属于同一组织
• 来自不同组织的人可以参加同一个会议
• 多个会议可以在同一地点举行

在所有位置中，有一个非常常用的位置（大本营）。

这意味着当我“展开生成树”时，当我到达那个位置时，我的图表“爆炸”

我使用的示例代码：

我希望在使用 terminatorNodes 时路径会在那个特定节点处停止并忽略“超出”的所有内容..但这不是发生的事情，实际上我看到所有节点“超出”

我也尝试过使用 endNodes，但是看起来代码一碰到那个特定的节点就会爆炸，并且在其他任何地方也停止生成树！

我也想为特定组织（我的！）获得相同的效果，但一步一步！

我真正想要实现的是通过会议检索与起始人员相关的所有人员。即“起始人”A 与来自不同组织的另外 3 人参加会议，然后我想看到这些人返回，以及他们的组织，然后是所有与他们的组织相关联的人。以上只是一个开始，因为我还有其他节点标签要处理，但目的相同。

我正在 Open vSwitch 中实现 RSTP。我正在按如下方式配置网桥：

我如何查看或检查上述配置，就像在 cisco 交换机中一样，我可以通过 switch# show spanning-tree 查看。

在 OVS 数据库中，这些条目如下所示：

如何从数据库或表中读取？

我正在研究生成树协议攻击，我想了解一件事。根在树的“顶部”，我们如何利用它来实施攻击？在某种程度上，我们可以成为 root，但是我们会获得什么特权呢？我不知道根是否可以读取所有数据包，因为我认为如果两个主机连接在树的“子部分”中，根看不到任何消息，还是我错了？

所以这很有用，因为我有更多机会阅读更多消息，但我永远不会看到所有消息，对吧？

另一件事，我怎样才能将 arp 欺骗攻击作为根？

谢谢

我正在研究 MST 算法。我很想知道 prims 和 boruvka 的算法之间的主要区别，但是网上的资源除了它们的实现和算法之外没有太多要说的。如果有人可以解释，那将是很大的帮助。谢谢！

我正在 CORE 模拟器中实现 RSTP。考虑每个节点都是一个 2 端口无线交换机。

方案一：考虑下图，请检查以下

在这里，将 n7 配置为根桥 (RB)。从 n19（源）和 n17（目标）看，生成树由黄线定义。从 n19 (n19) ping 到 n17。在 n9、n10 和 n2 捕获数据包，没有发现 ICMP 数据包。再次，在 n5、n6、n7 和 n3 捕获数据包并找到 ICMP 回复和请求数据包。这意味着，生成树完美地工作。

情景二（困惑）：现在考虑下图，请检查下面

这里，根桥是 n11（绿色方块），从 n19 到 n17 的生成树用黄线表示。作为方案 I，从 n19 ping 到 n17。在一些节点抓包后发现，n6和n11（RB）中没有ICMP包。从 n5 开始，数据包通过 n2 转发到 n17（红线）。我认为，由于生成树在 n6 的 wlan0 和 n1、n2 处合并，因此 n5 和 n6 在同一跳中，因此数据包直接从 n5 转发到 n2，而不通过 n6 转发到 RB。根据生成树算法可以吗？这种解释有效吗？

我正在尝试在 Python 上实现 Edmond 的最大分支算法。

最大分支问题。给定一个有向图 G=(V,E,w)，其中 w 是权重函数。对于V中的一个根r，确定一个有根r的分支G'=(V,E')，即G'不包含环，并且所有顶点的入度最大为1，总权重最大。

Edmond 算法可以在这里找到：http ://www-di.inf.puc-rio.br/~poggi/mba.html

你有针对这个问题的 Python 实现吗？

编辑：

感谢你们。我只是在 Stackoverflow 上模仿一个解决方案并在这里得到答案： https ://colab.research.google.com/drive/1kFynHGSXxYlr__2M3zl1kJtdPZTy5Ly7?usp=sharing

当我们使用邻接矩阵而不使用优先队列来实现该算法时，时间复杂度为 O(V^2)，其中 V 是总数。顶点数，E 是总数。的边缘。

但是当我们使用优先级队列（使用二叉堆）和邻接表来实现它时，时间复杂度是 O((V + E)*logV)。

在最坏的情况下，这个 TC 比 O(V^2) 好多少 E = O(V^2) ？

我无法得到它。请澄清我的疑问。

我有一个玩具图g，然后我通过拉普拉斯算子的辅因子找到了生成树的数量。数字是 11。

我有n=5顶点，我绘制了原始图：

graph.bfs()然后使用函数创建了 5 个生成树：

我需要绘制所有生成树。例如，不创建根 = 5 的下一棵树：

问题。为小型随机图生成所有树的可能方法是什么？