查找具有相同权重的最大边数量的生成树 [英] Find a spanning tree with maximum number of edges with same weight

问题描述

这是问题所在。

给出了一个加权无向连通图G.权重是恒定的。我们的任务是提出一种算法，它可以找到满足这两个条件的G的生成树的总权重（按优先级排序）：

• 生成树必须具有具有相同权重的边的最大数量（实际重复的权重值无关紧要）;
  总的生成树权重应该被最小化。例如，这意味着，例如，具有权重120的生成树T1具有至多4个具有相同权重的边（以及每个那四个是15）应该优于生成树T2，其中权重140具有至多4个具有相同权重的边（并且这四个中的每一个的权重是8）。
  

现在我已经停留了很长时间了。我已经为图表实现了Boruvka的MST搜索算法，现在我不确定是否应该在找到MST之后执行任何操作，或者最好修改MST搜索算法本身。

任何建议欢迎！

解决方案

这可以在 O m ^ 2），并且在 O（mn）中没有太多努力。似乎可以更快地做到这一点，也许像 O（m log ^ 2（n））甚至 O（m log （n））有一些工作。

基本思想是这样的。对于任何权重 k ，让 MST（k）是一个生成树，其中包含最大可能的重量边数 k ，并且具有最小的整体重量。可能有多种这样的树木，但它们的总重量都是相同的，所以选择哪一棵并不重要。通过使用任何MST算法并且将权重 k 的所有边缘视为权重 MST（k） c $ c> -Infinity 。

这个问题的解决方案是 MST（k）用于一些 k 。因此，天真的解决方案是生成所有的 MST（k）并挑选最大数量的相同边权重，然后选择最小总权重。使用Kruskal算法，您可以在 O（m ^ 2）中执行此操作，因为您只需对边进行一次排序。

通过首先使用原始权重找到MST，然后对每个 k O（mn）通过减少权重 k 的每个边的权重为，将树修改为 MST（k） code> -Infinity 。因为您只需要在相应的中查找最大权重边缘，所以更新MST以减少边缘权重是 O（n）操作。 /en.wikipedia.org/wiki/Cycle_basis#Fundamental_cyclesrel =nofollow noreferrer>基本周期。

要比<$ c $做的更好c> O（mn）使用这种方法时，您将不得不对原始MST进行预处理，以便可以更快地执行这些边重量减少。看起来应该像重路径分解这样的工作，但有一些细节可以工作出去。

Here's the problem.

A weighted undirected connected graph G is given. The weights are constant. The task is to come up with an algorithm that would find the total weight of a spanning tree for G that fulfills these two conditions (ordered by priority):

• The spanning tree has to have maximum number of edges with the same weight (the actual repeated weight value is irrelevant);
• The total spanning tree weight should be minimized. That means, for example, that the spanning tree T1 with weight 120 that has at most 4 edges with the same weight (and the weight of each of those four is 15) should be preferred over the spanning tree T2 with weight 140 that has at most 4 edges with the same weight (and the weight of each of those four is 8).

I've been stuck on that for quite a while now. I've already implemented Boruvka's MST search algorithm for the graph, and now I'm not sure whether I should perform any operations after MST is found, or it's better to modify MST-search algorithm itself.

Any suggestions welcome!

解决方案

This can be done naively in O(m^2), and without much effort in O(mn). It seems like it is possible to do it even faster, maybe something like O(m log^2(n)) or even O(m log(n)) with a little work.

The basic idea is this. For any weight k, let MST(k) be a spanning tree which contains the maximum possible number of edges of weight k, and has minimum overall weight otherwise. There may be multiple such trees, but they will all have the same total weight, so it doesn't matter which one you pick. MST(k) can be found by using any MST algorithm and treating all edges of weight k as having weight -Infinity.

The solution to this problem will be MST(k) for some k. So the naive solution is to generate all the MST(k) and picking the one with the max number of identical edge weights and then minimum overall weight. Using Kruskal's algorithm, you can do this in O(m^2) since you only have to sort the edges once.

This can be improved to O(mn) by first finding the MST using the original weights, and then for each k, modifying the tree to MST(k) by reducing the weight of each edge of weight k to -Infinity. Updating an MST for a reduced edge weight is an O(n) operation, since you just need to find the maximum weight edge in the corresponding fundamental cycle.

To do better than O(mn) using this approach, you would have to preprocess the original MST in such a way that these edge weight reductions can be performed more quickly. It seems that something like a heavy path decomposition should work here, but there are some details to work out.

这篇关于查找具有相同权重的最大边数量的生成树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！