我有一个应用程序，它使用有向无环图 (DAG) 来表示按时间排序的事件。我的目标是创建或找到一种算法，通过删除具有特定属性的某些边来简化图形。我将尝试定义我的意思:
在下面的例子中， 是第一个节点和 f 是最后一个。在第一张图片中，有四个独特的路径可以用来从 开始。 至 f .如果我们隔离之间的路径b 和 e ，我们有两条替代路径。为单边的路径，即之间的边b 和 e 是我要删除的路径类型，结果将图形留在第二张图片中。
因此，我想删除的所有边都定义为:两个节点之间的单个边，这些节点至少有一条其他路径 >1 条边。
我意识到这可能是一种非常特殊的图形操作，但希望这种算法已经存在，我对 Stack Overflow 的问题是:这是一个已知的图形操作，还是我应该把我的钱带到算法绘图板上？
最佳答案
就像 Matt Timmermans 在评论中所说的那样:该操作称为 transitive reduction .
谢谢马特!
关于algorithm - 这个图缩减操作是否已经存在？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/68803286/