如何find最大的生成树？

Kruskal最小生成树algorithm的反面是否适用？ 我的意思是，每一步select最大重量（边缘）？

任何其他想法find最大的生成树？

是的，它确实，

来源:(不幸搬家或删除） – http://www.stats.ox.ac.uk/~konis/Rcourse/exercise1.pdf-

计算networkingG的最大权重生成树的一种方法 – 归因于克鲁斯卡尔 – 可以概括如下。

  1. 将G的边缘按重量降序排列。 设T是包含最大权重生成树的边的集合。 设定T =∅。
  2. 将第一个边添加到T.
  3. 将下一个边添加到T当且仅当它不在T中形成循环。如果没有剩余的边退出并报告G被断开连接。
  4. 如果T有n-1个边（其中n是G中的顶点数）停止并输出T。 否则，请转到步骤3。

从这个网站：

“最大生成树是具有最大权重的加权图的生成树，可以通过否定每个边的权重并应用Kruskalalgorithm（Pemmaraju和Skiena，2003，第336页）来计算。

如果你在每一个边上反转权重并且最小化，你得到最大的生成树吗？ 如果这样的话可以使用相同的algorithm。 当然，零重量将成为一个问题。

虽然这个线程太老了，但我有另外一个方法来find图G =（V，E）中的最大生成树（MST）

我们可以应用一些Prim的algorithm来寻找MST。 为此我必须定义最大加权边的切割属性。

切割属性：假设任何时候我们都有一个包含MST顶点的集合S（现在假设它是以某种方式计算的）。 现在考虑设置S / V（顶点不在MST中）：

说明：从S到S / V的最大重量的边缘总是在每个MST中。

certificate：假设当我们将顶点join到集合S时，从S到S / V的最大加权边是e =（u，v），其中u在S中，v在S / V中。 现在考虑一个不包含e的MST。 将边e添加到MST。 它会在原来的MST中创build一个循环。 遍历循环，findS和V中的顶点u'，使得u'是S中的最后一个顶点，之后我们inputS / V，V'是S / V中第一个顶点从你到你

除去边e'=（u'，v'），结果图仍然连接，但e的权重大于e'[因为e是此时从S到S / V的最大加权边缘]，所以这导致MST的权重总和大于原始MST。 所以这是一个矛盾。 这意味着边e必须在每个MST中。

algorithmfindMST： 

从S = {s}开始// s是开始顶点
而S不包含所有的顶点
 做 
  {
  对于S中的每个顶点
  从S / V添加一个顶点v，使边e =（s，v）的权重最大 
   }
结束时

实现：我们可以使用Max Heap / Priority Queue来实现，其中关键是从S中的顶点到S / V中的顶点的边的最大权重，并且值是顶点本身。 在S中添加顶点等于堆中的Extract_Max，并且在每个Extract_Max中更改刚添加的顶点附近的顶点的关键点。

所以需要m个Change_Key操作和n个Extract_Max操作。

Extract_Min和Change_Key都可以在O（log n）中实现。 n是顶点的数量。

所以这需要O（m log n）时间。 m是图中边的数量。

否定原始图的权重，并且在否定图上计算最小生成树将给出正确的答案。 这是为什么：对于两个图中的同一棵生成树，一个图的加权和是另一个的否定。 因此，否定图的最小生成树应该给出原始生成树的最大生成树。

只有颠倒sorting顺序，在顶点切割中select重边，并不能保证最大生成森林（Kruskalalgorithm生成森林，而不是树）。 如果所有边都具有负权重，则从kruskal反转获得的最大生成森林仍然是一个负权重path。 然而，理想的答案是一个连接顶点的森林。 即| V |的森林 单身树，或| V | 总重量为0的组件（不是最不重要的）。

让我提供一个改进algorithm：

  • 首先构造一个任意的树（使用BFS或DFS）
  • 然后在树外select一个边，将其添加到树中，它将形成一个循环，在循环中放下最小的重量边。
  • 继续做这个util所有其余的边缘被认为是

因此，我们将得到最大的生成树。

这棵树满足树外的任何边，如果加上，就会形成一个循环，边的外部<=在循环中的任何边权

实际上，这是生成树为最大生成树的必要条件。

PF。

必要的：很明显，这是必要的，或者我们可以交换边缘来创build一个具有较大边权重的树。

足够：假设树T1满足这个条件，T2是最大生成树。

那么对于边T1∪T2，有T1个边，T2个边，T1∩T2个边，如果我们给T2加上一个仅有T1的边（x1，xk），我们知道它会形成一个循环，并且我们声称， 在这个循环中必须存在一个仅具有与（x1，xk）相同边缘权重的仅T2边 。 然后我们可以交换这些边将产生一个与T2共同的边，并且具有相同的边权重总和，重复这样做，我们将得到T2。 所以T1也是一棵最大的生成树。

certificate索赔：

假设这是不正确的，在这个循环中我们必须有一个仅有T2的边缘，因为T1是一棵树。 如果没有任何T2的边具有等于（x1，xk）的值，则每个仅T2的边与树T1形成循环，则T1具有循环导致矛盾。

在这里输入图像说明

这个algorithm取自UTD教授R. Chandrasekaran的笔记。 你可以参考这里： 单商品多terminalstream量

    Interesting Posts

    克鲁斯卡尔vs Prim