如何以最少的步骤删除图表？

给定一个有向图，我如何找到删除最小数量的节点以删除整个图所需的顺序？我假设如果一个节点被删除，连接到它的所有外部节点（任何程度）也被删除。如何以最少的步骤删除图表？

例如，在二叉搜索树中，删除树中所有节点的最快方法（假定是）将删除根节点。但是，给定任何图表，如何确定要删除哪个节点？

我心目中的（很慢）什么：

生成所有可能的子图，并与最外边找到子。
删除该子图。
重复，直到没有剩余的节点。

为什么它是一个很好的问题： 假设我们得到与代表世界所有问题的节点有向图，而所有这些节点与代表的原因/效果的边缘（即一些问题进行了连接造成他人）。我们如何才能找到摆脱所有问题的最少数量的问题？

2015-09-07 Mico Abrina

欢迎使用stackoverflow。从问题的复制/粘贴性质来看，这是一个分配问题。我们不介意帮助那些人，但目前格式化的方式是“为我做”，我们不在这里做。如果我们是，我们最终会获得学位;）。用你试过的一些例子更新你的问题，如果可以的话，我们会提供帮助。 – ScottMcGready

我已经添加了我对这个问题的答案，但我不得不承认这是一个非常慢的算法。另外，请记住，这不是一个分配问题。我只是想知道是否有人能想出解决这个问题的更好方法。 –

好得多。你现在会收到一个体面的回应。 – ScottMcGready

一个顶点可以有：

未连接边缘或出站连接边缘只（即路径的第一顶点）;
仅限入站连接边（即路径的最后一个顶点）;或
传入和外发连接边缘 - 在这种情况下，它可以是：
1. 一个strongly connected component（SCC）的部分 - 即一个周期a->b->c->a或在两个方向上a->b->c + c->b->a连接边缘的顶点;或
2. 部分有向非循环子图 - 即b在简单路径a->b->c中或在一组分支路径a->b->c + b->d->e + f->b中。

顶点匹配情况（1）可以被平凡搜索和删除 - 无呼入边缘的顶点不能被删除任何其他顶点所以必须包含删除所需的最小集合的顶点的内删除图表。

匹配情况（2）和（3.2）的顶点可以忽略;删除路径顶部的顶点将删除路径中间的所有顶点（情况3.2）和路径末尾（情况2），因此这些顶点将永远不会包含在要删除的最小顶点集合中图表。

删除包含在SCC中的任何顶点（案例3.1）将删除SCC中的所有顶点（以及从SCC分支出来的所有后代子树）。通过将SCC折叠成单个伪顶点（其中连接到包含在SCC中的顶点的所有边被替代地视为与伪顶点具有相同的方向性连接），可以（简单地）减小图。对所有SCC重复此操作会将该图减少为连接有向无环图（DAG）的集合。每个DAG将具有一个或多个根顶点（没有出边），它们可以是实际的顶点，情况（1）或伪顶点，代表情况（3.1）。最小删除集合是这组根顶点 - 即情况（1）的所有根顶点和每个根假顶点（表示情况3.1）任何一个包含在该SCC内的实际顶点。

Stronly连接的组件可使用Tarjan's Strongly Connected Components Algorithm被发现和一次减少到DAG根顶点可以通过入站边沿进行计数找到。

删除这些顶点的顺序并不重要 - 删除这些顶点中的任何一个都不会删除最小删除集中的任何一个，以便它们可以按任意顺序删除，并且必须全部删除以删除整个图。（最小删除集合中的顶点可能会共享它们的部分或全部后代，删除的顺序会影响这些后代的删除顺序，但在问题中没有问到这一点。）

来源

2015-09-08 14:25:16 MT0

如何以最少的步骤删除图表？

回答

相关问题