graph-theory - 最小生成树

Question

我有一个关于图形和最小生成树的作业

假设对于给定的图 G1，我们计算了最小生成树 T1。现在，为 G1 添加了一条新边。我们称这个带有添加边 G2 的新图。描述一种通过调整 T1 来有效计算 G2 的最小生成树 T2 的算法。

Answer 1

尝试在 T1 中添加新边，比如 e'，这将在 T1 中形成一个循环。您的问题已简化为在 T1 + e' 的唯一循环中找到最大加权边缘。

如果您从 T1 + e' 中删除您通过前面过程找到的边，您将获得 T2。