주어진 DAG가 격자인지 테스트

Question

고유 한 소스 및 싱크가있는 지시 된 비순환 그래프 (DAG)가 제공됩니다. 이 그래프가 나타내는 partial order이 lattice인지 여부를 테스트하는 효율적인 방법이 있습니까?

즉, 어떤 두 개의 꼭지점이 고유 한 최소 상한선과 최대 하한선인지 여부를 테스트해야합니다.

Answer 1

이 최적의 방법은 확실하지 않지만 시도해 볼 가치가있는 것으로 보입니다.

의도적으로 만나고 존재하는 버텍스 쌍 수를 확인해야합니다. 회의 및 조인은 동일한 접근 방식으로 독립적으로 검사됩니다. 반대편 가장자리 방향으로 다른 쪽 (조인)보다 먼저 한 쪽 (충족).

아이디어는 토폴로지 정렬을 사용하고 이미 방문한 정점과 만나기 위해 다음 방문 정점을 검사하는 것입니다. 그것의

• 세트가 이전 P(v) = {x; x < v},
• 는 위상 인덱스 I(v)의의 :이 각 정점 (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)이다. 수표를 줄이려면 부분 명령의 속성을 사용하십시오. v 및 a in C(v)에 회의가 있고 b in C(v) 및 b < a 인 경우 v 및 b이 충족되어야합니다 (v 및 a과 동일). 이를 통해 확인할 수없는 나가는 모서리 (U(v))를 가진 C(v)의 정점을 검사하면 충분합니다. 아마도 U (v)의 모든 정점을 검사 할 필요가 없을 것입니다. 그 중 일부는 순서가 매겨 질 수 있기 때문입니다. U(v)의 정점을 인덱스 (I(x))로 내림차순으로보다 쉽게 ​​검사 할 수 있습니다.

회의의 수표는 |V| * width(G)이며, 아마도 |V|^2보다 훨씬 작습니다.

각 버텍스는 이전 버젼의 집합을 저장해야하기 때문에 메모리 문제가 있습니다. 잠재적으로 |V|^2 공간입니다. 방문 된 버텍스가 x 인 경우 U(v)에 없기 때문에 더 이상 크기 P (x) 만 확인할 수 있기 때문에 그럴 수 있습니다. 따라서이 정점들에 대해서는 P(x)을 삭제하고 대신 |P(x)|을 저장할 수 있습니다.

다음에 방문한 정점이 단 하나만있는 경우, 정점이 U(v) 인 회의를 테스트 할 필요가 없으므로주의하십시오. 이러한 추론은 수퍼 - 블래 티스가 한 모서리로 방문 된 정점에 연결되고 모든 하위 격자 정점을 검사 할 필요가없는 경우에도 확장 할 수 있습니다. 하지만 하위 격자를 확인하는 것은 매우 어렵습니다.