好吧，我觉得这有点棘手。
基本上，有一个有向图（我们称之为基图），它有一些叶子和一个0索引的节点，称为根。它可能包含循环。
从这个基础图中，我们得到了一棵树，它包含了根和所有的叶子，以及它们之间的一些联系不需要将根与叶连接的节点和边被省略。
现在想象一下树上的一个或多个边“折断”，并且不能再使用了现在的问题是
a）如果可能，找到到断开连接的节点的替代路由，从基图中引入尽可能少的以前未使用的边。
b）如果不可能，请选择要“修复”的边，修复尽可能少的边，以使所有叶重新连接。
这应该代表一个电网，中断是断电。
如果只有一条边断了，就足够容易了。但是假设你有一个100个叶子，500个边，50个边断开的图现在要找到从基图中添加以前未使用的边的组合，并在必要时修复某些边，连接所有叶，似乎是一个非常困难的问题。
我想象一个人可以做一些蛮力，所有未使用的边的组合，从使用1到所有边，都要经过测试或者如果需要修理，用新边的所有组合测试所有修理组合。当边缘的数量变得很高时，在我看来这是非常低效的。
我的问题是，有没有人有什么聪明的想法，如何能以更有效的方式做到这一点？我希望我解释得足够好。
最佳答案
这是一个np难问题，我来解释原因。假设您有三层节点：根节点、中间连接节点层，然后是叶节点层。边缘从根节点到中间节点，从中间节点到叶节点的某些子集。假设您有一些中间节点和边到叶节点的选择，它们为您提供了一个连接树图，其中每个中间节点只有一个叶节点的边现在假设缩减图中的所有边都被移除。然后，为了找到修复图所需添加的最小边数，这相当于找到其边覆盖所有叶节点的剩余中间节点的最小数目。这相当于叶节点http://en.wikipedia.org/wiki/Set_cover_problem的集覆盖问题，是np困难的。因此，在最坏的情况下（除非P=NP），几乎肯定没有快速算法来解决您的问题也许如果你限制了被移除的边的数量，你可以提出一个多项式时间算法，其中多项式中的指数依赖于（希望是弱的）被移除的边的数量。