删除边后包含给定边的最小生成树

Question

这是备考的一部分。我知道这与max-flow算法有关，但我很乐意给你一个提示：

设G=(V,E)是无向连通图，w:E->R是权函数，e是边，k > 0是边。描述一个算法，该算法确定我们是否可以从图中删除最多的k边，以便e属于新图的最小生成树。

我认为生成树是一种完美的匹配。但如何使其最小化，使其包含e和适当数量的其他边？

Answer 1

提示:对于每个边e，存在一个包含e的最小权重生成林当且仅当e的端点之间不存在由比e(严格地)轻的边组成的路径。