오일러 투어 기술

Euler tour technique
트리의 오일러 투어(가장자리에 라벨이 부착되어 투어에 의해 횡단되는 순서를 표시함)

레온하르트 오일러의 이름을 딴 오일러 투어 기법(ETT)은 나무를 표현하는 그래프 이론의 방법이다.트리는 트리의 각 모서리에 대해 두 개의 방향 모서리를 포함하는 방향 그래프로 표시됩니다.트리는 트리의 오일러 순회 표현(ETR)으로 알려진 방향 그래프의 오일러 회로로 표현될 수 있습니다.ETT는 알고리즘 그래프 이론의 일반적인 문제에 대한 해결책을 효율적이고 병렬적으로 계산할 수 있도록 합니다.그것은 [1]1984년 타잔과 비슈킨에 의해 소개되었다.

건설

무방향 트리가 에지 세트로 제시될 경우, 오일러 순회 표현(ETR)은 다음과 같이 병렬로 구성할 수 있습니다.

  • 방향 모서리의 대칭 목록을 구성합니다.
    • 트리의 각 무방향 에지 {u,v}에 대해 에지 목록에 (u,v) 및 (v,u)를 삽입합니다.
  • 가장자리 목록을 사전 편집순으로 정렬합니다(여기에서는 트리의 노드가 정렬되어 있고 루트가 이 순서의 첫 번째 요소라고 가정합니다).
  • 각 노드의 인접 리스트(다음으로 호출) 및 노드에서 인접 리스트의 첫 번째 엔트리(처음으로 호출)로의 맵을 작성합니다.
    • 목록의 각 에지(u,v)에 대해 병렬로 수행합니다.
      • 이전 에지(x,y)가 x µu인 경우, 즉 다른 노드에서 시작하는 경우 먼저(u) = (u,v)로 설정합니다.
      • 그렇지 않으면 x = u, 즉 동일한 노드에서 시작하는 경우 next(x,y) = (u,v)로 설정합니다.

다음 규칙에 따라 모든 에지(u,v)에 대한 포인터 succ(u,v)를 병렬로 설정하여 오일러 투어 순서로 에지 목록(숙이라고 함)을 구성합니다.

결과 목록 succ는 원형입니다.

트리에 n개의 노드가 있는 경우 전체 구성에는 W(n) = O(sort(n))(트리에서와 같이 n개의 항목을 병렬로 정렬하는 데 걸리는 시간)가 소요됩니다.

루트, 전진 및 후퇴 가장자리

트리에 루트가 있는 경우 해당 루트에서 순환 목록을 분할할 수 있습니다.이 경우 전진 및 후퇴 에지에 대해 말할 수 있습니다.한 쌍의 노드 u,v가 주어지면 ETR에서 (u,v) 또는 (v,u)의 첫 번째 발생을 전진 에지라고 하고 두 번째 발생을 후퇴 에지라고 합니다.이는 이러한 가장자리를 처음 횡단할 때는 루트까지의 거리가 증가하는 반면 두 번째부터는 거리가 감소한다는 직감에 호소합니다.

트리의 재루팅은 새 루트에서 순환 목록 succ를 분할하여 일정 시간 O(1) 내에 수행할 수 있습니다.

적용들

다음 문제는 모두 O(Prefix sum(n))(n개 항목의 목록에 대해 prefix sum 문제를 병렬로 해결하는 데 걸리는 시간)로 해결할 수 있습니다.

  1. 전진 및 후퇴 에지 분류:ETR에서 순위를 나열하고 결과를 2차원 배열 A에 저장합니다.그러면 (u,v)는 A(u,v) < A(v,u)가 되고, 그렇지 않으면 후퇴 에지가 됩니다.
  2. 각 노드의 레벨을 확인합니다.ETR에서 접두사 합계를 수행합니다. 여기서 모든 선행 에지는 1로 계산되고 후퇴 에지는 -1로 계산됩니다.다음으로 어드밴스 에지(u,v)의 값은 v의 레벨입니다.
  3. v에 루트된 하위 트리의 노드 수: v의 상위가 u라고 가정하고, 확장 에지(u,v) 및 후퇴 에지(v,u)를 병렬로 확인한 다음 접두사 합계를 사용하여 (u,v)와 (v,u) 사이의 확장 에지 수를 계산합니다.
  4. 노드 v:의 깊이 우선 검색 인덱스는 (u,v)까지의 어드밴스 에지 수를 카운트합니다.
  5. 두 노드의 가장 낮은 공통 상위 노드를 결정합니다.

오일러 투어 트리

헨징거와[2] 킹은 오일러 투어를 투어의 인덱스에 의해 키된 균형 잡힌 이진 검색 트리로 유지함으로써 주어진 트리를 나타낼 것을 제안한다.예를 들어 위의 예에서 7개의 노드를 가진 불균형 트리는 각 노드가 둘러볼 때마다 14개의 노드를 가진 균형 잡힌 이진 트리로 표시됩니다.

ET 트리(포레스트 트리 1개당 ET 트리 1개) 컬렉션을 사용하여 포레스트(비순환 그래프)를 나타낼 수 있습니다.이 표현을 통해 ET 트리의 첫 번째 노드로 이동함으로써 "노드 v의 루트는 무엇인가?"라는 질문에 빠르게 대답할 수 있습니다(ET 트리의 노드는 오일러 투어의 위치에 따라 키가 지정되며 루트는 투어의 첫 번째이자 마지막 노드이기 때문입니다).표시된 포레스트가 업데이트되면(예를 들어 두 개의 트리를 하나의 트리에 연결하거나 두 개의 트리로 분할함으로써), 해당 오일러 투어 구조가 시간 O(log(n)에 업데이트될 수 있다.

링크 트리/컷 트리는 유사한 성능 보증을 제공합니다.LC 트리는 트리 경로상의 Aggregate 유지보수에 적합하지만(네트워크 플로우알고리즘에서는 최적의 데이터 구조입니다), ET 트리는 [3]서브트리의 집약정보를 유지하는 것이 좋습니다.

레퍼런스

  1. ^ Tarjan, R.E.; Vishkin, U. (1984). Finding biconnected components and computing tree functions in logarithmic parallel time. Proceedings of FOCS. pp. 12–20. CiteSeerX 10.1.1.419.3088. doi:10.1109/SFCS.1984q5896.
  2. ^ Henzinger, M. R.; King, V. (1995). "Randomized dynamic graph algorithms with polylogarithmic time per operation". Proceedings of the twenty-seventh annual ACM symposium on Theory of computing - STOC '95. p. 519. doi:10.1145/225058.225269. ISBN 0897917189.
  3. ^ 고급 데이터 구조 강의 메모에서 오일러 트리를 둘러봅니다.에릭 데메인 교수; 스크라이브: 캐서린 라이.