algorithm - 寻找最小瓶颈生成树

Question

嗨，我正在做一些测试准备，我需要弄清楚 b 和 c 部分。我知道 a 部分是正确的，我可以证明这一点，但是找到 b 和 c 部分的算法目前让我望而却步。

解决以下问题以获得最小瓶颈树，其中具有最大成本的边被称为瓶颈。(a) G 的每个最小瓶颈生成树都是 G 的最小生成树吗？证明你的主张。

(b) 对于给定的成本 c，给出一个 O(n+m) 时间的算法来找出 G 的最小瓶颈生成树的瓶颈成本是否不大于 c。

(c) 找到一种算法来找到 G 的最小瓶颈生成树。

提前感谢任何可以帮助我的人

Answer 1

对于（b）：

擦除G中花费超过c的每条边，然后检查左图是否仍然连接。

对于(c)：

对c进行二分搜索，使用求解 (b) 的算法作为划分条件。

(b)的证明：

假设我们从G中删除成本超过c的边后得到的图是G'。然后：

1. 如果G'是连通的，那么G '中一定有生成树T。由于G'中没有边的成本超过c，我们可以确定T中没有边的成本超过c。因此T是G'和G的生成树，其瓶颈至多为c
2. 如果G'不连通，则G '中根本没有生成树。由于我们知道G - G'中的每条边都比c花费更多，并且我们知道G的任何生成树都将包含G - G'的至少一条边，因此我们知道G的边生成树不存在瓶颈 < = c

当然，检测一个图是否连接成本 O(n+m)

(c)的证明：

比如说，我们在(b)中使用的算法是F(G,c)。

然后我们有

如果F(G,c) = True对于某些c，则F(G,c') = True对于所有具有c '>=c 的 c'

如果F(G,c) = False对于某些c，则F(G,c') = False对于所有c'具有c'<=c

所以我们可以在c上进行二分搜索:)

Answer 2

Ans. a)False,every minimum bottleneck spanning tree of graph G is not a minimum spanning tree of G.

b)To check whether the value of minimum bottleneck spanning tree is atmost c,you can apply depth first search by selecting any vertex from the set of vertices in graph G.

***Algorithm:*** 


check_atmostvalue(Graph G,int c)
{

for each vertex v belongs to V[G] do {
visited[v]=false;
}

DFS(v,c); //v is any randomly choosen vertex in Graph G
for each vertex v belongs to V[G] do {
if(visited[v]==false) then
return false;
}
return true;
}



DFS(v,c)
{
visited[v]=true;

for each w adjacent to v do {
if(visited[w]=false and weight(v,w)<=c) then
DFS(w,c);
}
visited[w]=true;
}


This algorithm works in O(V+E) in the worst case as running timr for depth first search DFS is O(V+E).

Answer 3

这个问题可以通过简单地找到图的 MST 来解决。这基于以下声明：
MST 是连接图的 MBST。
对于一个 MST，选择 MST 中最大的边 e，边 e 将 MST 分成两个集合 S 和 T。那么从割性质来看，边 e 必须是连接 S 和 T 的那些边中的最小权重。
那么对于一个MBST，一定有一条边e'连接S和T。那么w(e')必须不小于w(e)。因此我们知道 MST 一定是一个 MBST。

但是，还有另一种方法可以确定最小瓶颈。我们不需要计算 MBST。在您的问题中，您实际上暗示了最小瓶颈的单调性。因此我们可以使用二分搜索结合连通性算法来找到最小瓶颈。我已经看到在其他情况下使用单一性。我有点惊讶，在这里可以使用类似的技术！