algorithm - 使用 =(,) 的其他生成树查找生成树

Question

我无法提出多项式时间算法来解决以下问题：

设=(,)是一个有顶点的无向无权图。让_1,_2,...,_是=−1的不同生成树。找到一种多项式时间算法，该算法在其中找到
=(,_)包含每个生成树的至少一条边的生成树_。

我真的很感激这方面的任何帮助！

Answer 1

生成树具有拟阵结构。因此，以下贪心算法起作用：从一个空森林开始，对于每个输入生成树，将森林扩展为任何不产生循环的树边缘。正确性或多或少直接来自增广属性和独立性的定义。

Answer 2

这是一个基本的解决方案。

//if the graph is given in input:
//    If any bridge exists in the graph:
//        return any spanning tree from the list of input spanning trees
    
while the size of result set is less than |V|-1:
    for every tree in the list of spanning trees:
        for every edge in the tree:
            if edge is not a part of result set:
                if adding this edge to the result set doesn't form a cycle:
                    add the edge to result set
                    break
        if size of result set is V-1:
            break

• 生成树列表的大小 < |V|-1: 需要 while 循环
• 生成树列表的大小 > |V|-1：需要证明“上述算法返回的结果集至少包含生成树列表中所有剩余树的一条边”。我会在闲暇时尝试这个证明。

如果对于给定的图 |E| < 2*(|V|-1) 或生成树的大小列表 < |V|，那么上面的算法肯定有效。

一个有趣的例子是当 |E| >= 2*(|V|-1)。如下图所示，对于一些生成树 L 的输入列表，假设绿色边缘的集合是上述算法返回的结果集。可以在不使用任何绿色边缘的情况下形成蓝色边缘的生成树。

刚刚发布了这个答案，以便它为试图回答这个问题的人们提供一些基本的基础工作。否则，可以被视为蛮力解决方案。