4

我得到一个具有唯一源和汇的有向无环图（DAG）。有没有一种有效的方法来测试这个图表示的偏序是否是一个格子？

换句话说，我需要测试任何两个顶点是否具有唯一的最小上界和最大下界。

4

1 回答 1

2

我不确定这是不是最佳方法，但在我看来，值得一试。

目的是检查至少尽可能多的顶点对是否存在相遇和连接。使用相同的方法独立检查 Meet 和 Join。首先一侧（相遇）而不是另一侧（连接），边缘方向相反。

想法是使用拓扑排序，并检查下一个访问的顶点是否与已经访问的顶点相遇。为了实现这一点，每个顶点 ( v) 必须存储：

  • 一套它的前身P(v) = {x; x < v}，
  • 是拓扑索引I(v)。

查找两个给定顶点 ( ) 是否存在相遇a, b是通过以下方式完成的：

P_ab = P(a) intersect P(b)
Find x in P_ab with max I(x).
If |P(x)| = |P_ab| - 1 than x is a meet of a and b.

访问新的顶点v，要检查的节点v是C(v) = all already visited nodes - P(v)。使用偏序属性减少检查次数。if vand a in C(v)have a meet, and if b in C(v)and b < a, than vand bhave meet (same as vand a). 这样就足以检查C(v)具有未解析出边的顶点（U(v)）。可能甚至不需要检查 U(v) 中的所有顶点，因为其中一些是可以排序的。为了更容易地按索引（ ）U(v)按降序检查顶点。I(x)

一次见面的支票数量是有序的|V| * width(G)，可能比|V|^2.

存在内存问题，因为每个顶点都必须存储一组它的前辈。那是潜在的|V|^2空间。这可以减少，因为如果访问的顶点x不再存在U(v)，则只能检查大小 P(x)。所以，对于这些顶点P(x)可以被删除和|P(x)|存储。

请注意，如果下一个访问的顶点只有一个 in 边，则不需要测试它是否与 中的顶点相遇U(v)。这种推理甚至可以扩展到如果子格子通过一条边连接到访问的顶点，则不必检查所有子格子顶点。但是，检查子晶格可能非常困难:-)

于 2017-05-15T19:42:21.603 回答