algorithm - 需要一些帮助来理解这个关于最大化图形连通性的问题

Question

我想知道是否有人可以帮助我理解这个问题。我准备了一个小图表，因为它更容易直观地解释。

alt text http://img179.imageshack.us/img179/4315/pon.jpg

我要解决的问题:

<强>1。构建依赖图 给定图的连通性和确定节点相互依赖程度的度量，对依赖关系进行排序。例如，我可以制定一些规则来说明这一点

• 节点3依赖于节点4
• 节点2依赖于节点3
• 节点 3 依赖于节点 5

但因为最终规则不是“有值(value)的”(同样基于相同的指标)，我不会将规则添加到我的系统中。

<强>2。执行请求命令 一旦我构建了一个依赖图，就以最大化最终连接的顺序执行列表。我不确定这是否真的是个问题，但我有一种感觉，可能存在多个订单，在这种情况下，需要选择最佳订单。

首先，我想知道我是否正确构建了问题，以及我是否应该知道任何极端情况。其次，有没有我可以看的密切相关的算法？目前，我正在考虑类似 Feedback Arc Set 的东西或 Secretary Problem但我现在有点困惑。有什么建议吗？

PS:我自己对这个问题有点困惑，所以请不要因此而对我发火。如果需要任何说明，我会尝试更新问题。

Answer 1

看起来您正在尝试确定发送到节点之间具有依赖关系(或谷歌的“部分排序”)的请求的顺序。

如果你用谷歌搜索“部分顺序依赖图”，你会得到一个指向 here 的链接。 ，这应该会为您提供足够的信息来找出一个好的解决方案。

一般来说，您希望以这样一种方式对节点进行排序，即节点排在它们的依赖项之后；又名拓扑排序。