Técnica del recorrido de Euler

La técnica del recorrido de Euler ( ETT ), llamada así por Leonhard Euler , es un método de la teoría de grafos para representar árboles . El árbol se considera como un grafo dirigido que contiene dos aristas dirigidas por cada arista del árbol. El árbol puede entonces representarse como un circuito euleriano del grafo dirigido, conocido como la representación del recorrido de Euler ( ETR ) del árbol. La ETT permite un cálculo paralelo y eficiente de soluciones a problemas comunes en la teoría de grafos algorítmicos . Fue introducida por Tarjan y Vishkin en 1984. ^[1]

Dado un árbol no dirigido presentado como un conjunto de aristas, 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 arista no dirigida { u , v } en el árbol, inserte ( u , v ) y ( v , u ) en la lista de aristas.
• Ordenar la lista de aristas lexicográficamente . (Aquí suponemos 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 next ) y un mapa desde los nodos hasta las primeras entradas de las listas de adyacencia (llamado first ):
  • Para cada arista ( u , v ) de 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 )

Construya una lista de aristas (llamada succ ) en el orden del recorrido de Euler estableciendo punteros succ( u , v ) para todas las aristas ( u , v ) en paralelo de acuerdo con la siguiente regla:

${\displaystyle \mathrm {succ} (u,v)={\begin{cases}\mathrm {siguiente} (v,u)&\mathrm {siguiente} (v,u)\neq \mathrm {nil} \\\mathrm {primero} (v)&{\text{de lo contrario}}.\end{cases}}}$

La lista resultante succ será circular.

La construcción general requiere trabajo W ( n ) = O(sort( n )) (el tiempo que lleva ordenar n elementos en paralelo) si el árbol tiene n nodos, ya que en los árboles el número de aristas es uno menos que el número de nodos.

Si el árbol tiene una raíz, podemos dividir la lista circular succ en esa raíz. En ese caso, podemos hablar de aristas de avance y de retroceso : dado un par de nodos u , v , la primera aparición de ( u , v ) o de ( v , u ) en el ETR se denomina arista de avance , y la segunda aparición se denomina arista de retroceso . Esto apela a la intuición de que la primera vez que se recorre una arista de este tipo, la distancia a la raíz aumenta, mientras que la segunda vez la distancia disminuye.

El rerooteo del árbol se puede realizar en tiempo constante O(1) dividiendo la lista circular succ en la nueva raíz.

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):

1. Clasificación de los bordes de avance y retroceso: Realice una clasificación de lista en el ETR y guarde el resultado en una matriz bidimensional A . Entonces ( u , v ) es un borde de avance si y solo si A ( u , v ) <  A ( v , u ), y un borde de retroceso en caso contrario.
2. Determinar el nivel de cada nodo: Realizar una suma de prefijos en el ETR, donde cada borde de avance cuenta como 1 y cada borde de retroceso cuenta como −1. Entonces el valor en el borde de avance ( u , v ) es el nivel de v .
3. 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 el prefijo suma.
4. El índice de búsqueda en profundidad de un nodo v : cuenta el número de aristas de avance hasta ( u , v ) inclusive.
5. Determinar el ancestro común más bajo de dos nodos.

Henzinger y King ^[2] sugieren representar un árbol dado manteniendo su recorrido de Euler en un árbol binario de búsqueda balanceado , codificado por el índice del recorrido. Por ejemplo, el árbol no balanceado del 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 grafo acíclico) utilizando una colección de árboles ET - un árbol ET para un árbol de bosque. Esta representación nos permite responder rápidamente a la pregunta "¿cuál es la raíz del nodo v?" con solo movernos al primer nodo del árbol ET (ya que los nodos en el árbol ET están identificados por su ubicación en el recorrido de Euler, y la raíz es el primer y el último nodo en el recorrido). Cuando el bosque representado se actualiza (por ejemplo, al conectar dos árboles a un solo árbol o al dividir un árbol en dos árboles), la estructura del recorrido de Euler correspondiente se puede actualizar en tiempo O(log(n)).

Los árboles de enlace/corte tienen garantías de rendimiento similares. Mientras que los árboles LC son buenos para mantener agregados en rutas de un árbol (lo que los 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]