Week 8
Bottleneck minimum spanning tree.
题目
Given a connected edge-weighted graph, design an efficient algorithm to find a
minimum bottleneck spanning tree
. The bottleneck capacity of a spanning tree is the weights of its largest edge. A minimum bottleneck spanning tree is a spanning tree of minimum bottleneck capacity.
思路
根据这个定义……MST就是瓶颈生成树呀，因为其最大的权重边已经是所有生成结果里面最小的——这是MST的定义
设计
如上
Is an edge in a MST.
题目
Given an edge-weighted graph
G
and an edge
e
, design a linear-time algorithm to determine whether
e
appears in some MST of
G
.
Note:
Since your algorithm must take linear time in the worst case, you cannot afford to compute the MST itself.
思路（非原创）
https://stackoverflow.com/questions/15049864/check-if-edge-is-included-in-some-mst-in-linear-time-non-distinct-values
MST环性质：如果图上存在一个环，其上一边的权重大于环上的其他边，那么这条边必不属于该图的MST
设计
对于指定的边，从其中一个端点DFS到另一端点，过程中只能走比指定边权重小的边
如果可达，那么指定边一定不在MST中
如果不可达，那么指定便一定在MST中（因为这种情况下，其不是两端点所在环上的权重最大边）
由于算法只涉及DFS，因此复杂度
ο ( E + V ) \omicron(E+V)
ο
(
E
+
V
)
Minimum-weight feedback edge set.
题目
A
feedback edge set
of a graph is a subset of edges that contains at least one edge from every cycle in the graph. If the edges of a feedback edge set are removed, the resulting graph is acyclic. Given an edge-weighted graph, design an efficient algorithm to find a feedback edge set of minimum weight. Assume the edge weights are positive.