Tag: 图有

如何将“级别”分配给非循环有向图的顶点？

我有一个非循环有向图。 我想以一种方式为每个顶点分配级别，以确保边缘（v1，v2）在图形中，然后是级别（v1）>级别（v2）。 如果等级（v1）=等级（v3），只要（v1，v2）和（v3，v2）在图中，我也会喜欢它。 此外，可能的级别是离散的（也可能将它们视为自然数）。 理想的情况是该级别（v1）=级别（v2）+ 1只要（v1，v2）在图表中并且没有从v1到v2的其他路径，但有时这对于其他约束是不可能的 – 例如，考虑具有边（a，b）（b，d）（d，e）（a，c）（c，e）的五个顶点上的图。 有谁知道一个不错的算法来解决这个问题？ 我的图表相当小（| V | <= 25左右），所以我不需要快速的东西 – 简单性更重要。 到目前为止，我的想法是找到一个最小元素，将它指定为0级，找到所有父级，将它们指定为级别1，并通过将+0.5添加到适当的顶点来解决矛盾，但这看起来非常糟糕。 此外，我觉得删除所有“隐含”边缘可能会有所帮助（例如，如果图形同时包含（v1，v2）和（v2，v3），则删除（v1，v3）。