La técnica de recorrido de Euler (ETT) , que lleva el nombre de Leonhard Euler , es un método en teoría de grafos para representar árboles . El árbol se ve como un gráfico dirigido que contiene dos bordes dirigidos para cada borde del árbol. El árbol se puede representar entonces como un circuito euleriano del gráfico dirigido, conocido como la representación del recorrido de Euler (ETR) del árbol. El ETT permite el cálculo paralelo y eficiente de soluciones a problemas comunes en la teoría de grafos algorítmicos . Fue introducido por Tarjan y Vishkin en 1984. [1]
Construcción
Dado un árbol no dirigido presentado como un conjunto de bordes, la representación del recorrido de Euler (ETR) se puede construir en paralelo de la siguiente manera:
- Construimos una lista simétrica de aristas dirigidas:
- Para cada borde no dirigido { u , v } en el árbol, inserte ( u , v ) y ( v , u ) en la lista de bordes.
- Ordene la lista de bordes lexicográficamente . (Aquí asumimos que los nodos del árbol están ordenados y que la raíz es el primer elemento en este orden).
- Construya listas de adyacencia para cada nodo (llamado a continuación ) y un mapa de los nodos a las primeras entradas de las listas de adyacencia (llamado primero ):
- Para cada borde ( u , v ) en la lista, haga en paralelo:
- Si el borde anterior ( x , y ) tiene x ≠ u , es decir, comienza desde un nodo diferente, establezca primero ( u ) = ( u , v )
- De lo contrario, si x = u , es decir, comienza desde el mismo nodo, establezca next ( x , y ) = ( u , v )
- Para cada borde ( u , v ) en la lista, haga en paralelo:
Construya una lista de aristas (llamada succ ) en orden de recorrido de Euler estableciendo punteros succ ( u , v ) para todas las aristas ( u , v ) en paralelo de acuerdo con la siguiente regla:
El succ de la lista resultante será circular.
La construcción general requiere trabajo W ( n ) = O (sort ( n )) (el tiempo que toma ordenar n elementos en paralelo) si el árbol tiene n nodos, ya que en los árboles el número de bordes es uno menos que el número de nodos.
Aristas, avance y retroceso de bordes
Si el árbol tiene una raíz, podemos dividir la lista circular succ en esa raíz. En ese caso, podemos hablar de bordes de avance y retroceso : dado un par de nodos u , v , la primera aparición de ( u , v ) o ( v , u ) en la ETR se llama borde de avance , y el segundo la ocurrencia se llama borde de retirada . Esto apela a la intuición de que la primera vez que se atraviesa un borde de este tipo, la distancia a la raíz aumenta, mientras que la segunda vez la distancia disminuye.
Se puede volver a enraizar el árbol en tiempo constante O (1) dividiendo la lista circular succ en la nueva raíz.
Aplicaciones
Todos los siguientes problemas se pueden resolver en O (Suma de prefijo ( n )) (el tiempo que lleva resolver el problema de suma de prefijo en paralelo para una lista de n elementos):
- La clasificación de avance y retroceso de bordes: clasificación en la ETR y guardar el resultado en una matriz bidimensional lista de tareas Una . Entonces ( u , v ) es un borde de avance si A ( u , v ) < A ( v , u ), y un borde de retirada en caso contrario.
- Determine el nivel de cada nodo: haga una suma de prefijo en el ETR, donde cada borde de avance cuenta como 1 y cada borde de retirada cuenta como -1. Entonces, el valor en el borde de avance ( u , v ) es el nivel de v .
- Número de nodos en un subárbol con raíz en v : suponga que el padre de v es u, determine el borde de avance ( u , v ) y el borde de retroceso ( v , u ) en paralelo, y luego cuente el número de bordes de avance entre ( u , v ) y ( v , u ) usando la suma de prefijo.
- El índice de búsqueda en profundidad primero de un nodo v : cuente el número de bordes de avance hasta e incluyendo ( u , v ).
- Determine el ancestro común más bajo de dos nodos.
Árboles de euler tour
Henzinger y King [2] sugieren representar un árbol dado manteniendo su recorrido de Euler en un árbol de búsqueda binario equilibrado , codificado por el índice del recorrido. Entonces, por ejemplo, el árbol desequilibrado en el ejemplo anterior, que tiene 7 nodos, estará representado por un árbol binario balanceado con 14 nodos, uno por cada vez que cada nodo aparece en el recorrido.
Podemos representar un bosque (un gráfico acíclico) usando una colección de árboles ET: un árbol ET por un árbol forestal. Esta representación nos permite responder rápidamente a la pregunta "¿cuál es la raíz del nodo v?" simplemente moviéndose al primer nodo del árbol ET (ya que los nodos en el árbol ET están codificados por su ubicación en el recorrido de Euler, y la raíz es el primer y último nodo del recorrido). Cuando se actualiza el bosque representado (por ejemplo, conectando dos árboles a un solo árbol o dividiendo un árbol en dos árboles), la estructura de Euler-tour correspondiente se puede actualizar en el tiempo O (log (n)).
Los árboles de enlace / corte tienen garantías de rendimiento similares. Si bien los árboles LC son buenos para mantener agregados en las rutas de un árbol (lo que lo convierte en una buena opción de estructura de datos en algoritmos de flujo de red), los árboles ET son mejores para mantener información agregada en subárboles. [3]
Referencias
- ^ Tarjan, RE; Vishkin, U. (1984). Encontrar componentes biconectados y calcular funciones de árbol en tiempo paralelo logarítmico . Procedimientos de FOCS. págs. 12-20. CiteSeerX 10.1.1.419.3088 . doi : 10.1109 / SFCS.1984q5896 .
- ^ Henzinger, MR; King, V. (1995). "Algoritmos de grafos dinámicos aleatorizados con tiempo polilogarítmico por operación". Actas del vigésimo séptimo simposio anual de ACM sobre teoría de la computación - STOC '95 . pag. 519. doi : 10.1145 / 225058.225269 . ISBN 0897917189.
- ↑ Euler tour trees - in Lecture Notes in Advanced Data Structures. Prof. Erik Demaine; Escriba: Katherine Lai.