去边后包含给定边的最小生成树
这是考试准备的一部分。我知道这和最大流量算法有关，但我很乐意给你一个提示：
设G=(V,E)为无向连通图，W:E->R为权函数，E为边，K>0。描述一种算法，该算法确定是否可以从图中最多删除K边，以便E属于新图的最小生成树。
我认为生成树是一种完美的匹配。但是，如何使它最小化，包含e和适当数量的其他边？
共有1个答案
提示：对于每条边e，存在一个包含e的最小权生成林当且仅当e的endpoint之间不存在由（严格地）比e轻的边组成的路径。
-
在加权无向图中，我需要找到一个包含给定边“e”的最小生成树，如果可能的话。我该怎么做呢？Kruskal从“e”开始？
-
问题: 给定 N 个节点和 M 条边的图形，边的索引范围为 1 - 你需要为M条边分配权重。权重在[1...M]，并且每个数字只能出现一次。 简而言之，答案应该是[1]的置换数组...M]，其中arr[i] = x表示edge[i]的权重为x。 你得到了一个由n-1条边组成的集合。R保证是图的生成树。 找到一种分配权重的方法，使R是图的最小生成树，如果有多个答案，则打印具有最小字典顺序的答案。 约
-
我现在使用的算法有点问题。我想让它划定界限。 下面是当前行为的一个例子： 以下是一个被通缉行为的示例： C#中凸壳的当前代码：https://hastebin.com/dudejesuja.cs 我的问题是： 1） 这可能吗？ R:是的 2）这甚至被称为凸包吗？（我不这么认为） R：不，这叫边界，link：https://www.mathworks.com/help/matlab/ref/boun
-
所以我有一个练习，我应该证明或反驳： 1）如果e是连通图G中的一个最小权边，使得不一定所有边都是不同的，则G的每一个最小生成树都包含e 关于如何证明这两个问题，有什么建议吗？归纳法？不知道怎么接近。
-
我不确定如何处理这个问题。 给定一个无向图，每条边的颜色要么是红色，要么是蓝色。如何在时间复杂度（O（m+n）log n）中找到包含尽可能少的红边的最小生成树。其中m个顶点和n个边。 任何帮助都将不胜感激。
-
我想为给定数量的节点和边生成一个随机图。当我运行它时，它会返回一个包含所有零的edgelist（例如，如果我用五个节点和边运行它，它会返回五对零作为edgelist）。这部分代码是否有问题导致了这种情况？