最小瓶颈生成树和最小生成树有何不同？

Question

一个加权图 G 的最小瓶颈生成树是指 G 的一棵生成树，使得生成树中任意边的权重最大值最小化。最小瓶颈生成树不必然是最小生成树（MST）。

请给一个例子以便更好地理解这些定义。

- Nikunj Banka

Answer 1

请查看维基百科上的最小生成树示例以供参考:

生成树的瓶颈是指该树中的最大权重边。在一个生成树中可能会有多个瓶颈（当然所有的瓶颈权重都相同）。在维基百科的最小生成树中，存在两个权重为8的瓶颈。

现在，取给定图的最小生成树（可能有多个最小生成树，它们的总边权重当然相同），并将最大边权重称为B。在我们的示例中，B = 8。

任何也带有权重为B = 8的瓶颈的生成树都是MBST。但它可能不是MST（因为总边权重比最佳情况更大）。

因此，取维基百科的最小生成树并修改它（添加/删除某些边），使得：

1. 它仍然是一棵生成树，并且
2. 它仍然不使用任何权重> 8，但
3. 你增加了总边权重

例如，只更改维基百科MST的“左侧”子树（包含权重{2, 2, 3}），将其更改为{2, 3, 6}，从而在不改变8的瓶颈的情况下增加总边权重4。太好了，你已经创建了一个MBST，它不是MST。

- dan3

---

你的意思是编辑左边而不是右边的{2,2,3}的边长吗？ - Nikunj Banka

哦...我把左右搞混了，我原本是在看另一个子树。已修复。 - dan3

如果边权是不同的，那么MST就是MBST。反之亦然。 - celeritas

这是必然的吗？MBST仍然不是唯一的对吧？ - jobin

@user2268997 不是这样的。取四个顶点，用权重为1、2、3的边将其中三个形成一个循环，然后用一条权重为4的边将第四个顶点连接到循环中的一个顶点。你必须选择权重为4的边，这将给你三个MBST，只有一个是MST。在所有边的权值均不相同时，仅MST始终唯一。一组反例是带有所有不同边权重的团加上一个额外的顶点，该顶点通过一条超级重边连接到团中；每个MBST由该边和团的任意生成树组成。 - G. Bach

Answer 2

在回答您的问题之前，让我定义一些在此处使用的术语...

1）生成树：给定图的生成树是覆盖该图中所有顶点的树。

2）最小生成树（MST）：给定图的MST是其所有可能的生成树中长度最小的生成树。 更清楚地说，对于给定的图，列出所有可能的生成树（可能非常大），然后选择其边权重总和最小的那个。

3）最小瓶颈生成树（MBST）：给定图的MBST是其所有可能的生成树中最大边权重最小的生成树。更明确地说，对于给定的图，列出所有可能的生成树和每个生成树的最大边权重。在其中选择最大边权重最小的生成树。

现在让我们看一下下面的四节点图像...

Graph-A是给定的原始图。如果我列出此图的所有可能生成树，并选择其边权重总和最小的那一个，则会得到Graph-B。因此Graph-B是最小生成树（MST）。请注意，它的总权重为1 + 2 + 3 = 6。

现在，如果我选择一棵最大边权重最小的生成树（即MBST），则可能会选择Graph-B或Graph-C。请注意，这两个生成树的最大边权重均为3，这是所有可能的生成树中最小的。

从Graph-B和Graph-C可以看出，即使Graph-C是MBST，它也不是MST。因为其总重量为1 + 3 + 3 = 7，大于在Graph-B中绘制的MST的总重量（即6）。

因此，MBST不一定是给定图的MST。但是，MST必须是MBST。

- Nagakishore Sidde

---

很棒的答案。我在另一个SO答案中提供了算法的详细信息：https://dev59.com/52Yq5IYBdhLWcg3wrSWs - Shital Shah