Descomposición pesada-ligera

En matemáticas combinatorias e informática teórica , la descomposición pesada-ligera (también llamada descomposición de caminos pesados ) es una técnica para descomponer un árbol con raíz en un conjunto de caminos . En una descomposición de caminos pesados, cada nodo que no es una hoja selecciona una "arista pesada", la arista que conecta con el hijo que tiene el mayor número de descendientes (los empates se resuelven arbitrariamente). Las aristas seleccionadas forman los caminos de la descomposición.

Si las aristas de un árbol T se dividen en un conjunto de aristas pesadas y aristas ligeras, con una arista pesada desde cada nodo no hoja a uno de sus hijos, entonces el subgrafo formado por las aristas pesadas consiste en un conjunto de caminos, donde cada vértice no hoja pertenece a exactamente un camino, el que contiene su arista pesada. Los nodos hoja del árbol que no son el extremo de una arista pesada pueden considerarse como caminos de longitud cero. De esta manera, cada vértice pertenece a exactamente uno de los caminos. Cada camino tiene un vértice cabeza, su vértice superior.

Alternativamente, los caminos de aristas pesadas pueden extenderse incluyendo una arista ligera, la que va desde la cabeza del camino hasta su padre. ^{[ 1 ]} En esta variación de la descomposición, algunos vértices pertenecen a múltiples caminos, pero cada arista de T pertenece exactamente a un camino.

Las rutas de la descomposición pueden organizarse en un árbol denominado «árbol de rutas», «árbol de rutas pesadas» o «árbol comprimido». Cada nodo del árbol de rutas corresponde a una ruta de la descomposición de rutas pesadas. Si p es una ruta de la descomposición de rutas pesadas, entonces el padre de p en el árbol de rutas es la ruta que contiene al padre de la cabeza de p . La raíz del árbol de rutas es la ruta que contiene la raíz del árbol original. Alternativamente, el árbol de rutas puede formarse a partir del árbol original mediante la contracción de todas las aristas pesadas.

Una arista "ligera" de un árbol dado es una arista que no fue seleccionada como parte de la descomposición de ruta pesada. Si una arista ligera conecta dos nodos de árbol x e y , donde x es el padre de y , entonces x debe tener al menos el doble de descendientes que y . Por lo tanto, en cualquier ruta de raíz a hoja de un árbol con n nodos, puede haber como máximo log₂n _aristas ligeras . De manera equivalente, el árbol de ruta tiene una altura como máximo _log₂n .  

La descomposición de caminos pesados ​​fue introducida por Sleator y Tarjan (1983) como parte del análisis amortizado de su estructura de árbol de enlaces/cortes , ^{[ 2 ]} y por Harel y Tarjan (1984) como parte de su estructura de datos para los ancestros comunes más bajos , ^{[ 3 ]} La estructura de datos de árbol de enlaces/cortes utiliza una partición de un árbol dinámico en caminos que no es necesariamente la descomposición de caminos pesados; su análisis utiliza una función potencial que mide su distancia de la descomposición de caminos pesados, y la pequeña altura del árbol de caminos implica que cada operación de la estructura de datos realiza solo un pequeño número de pasos que no pueden imputarse a las mejoras de esta función. ^{[ 2 ]} En la estructura de datos del ancestro común más bajo, la descomposición se utiliza para incrustar el árbol de entrada en un árbol binario completo de profundidad logarítmica, lo que permite que cada consulta se resuelva mediante operaciones bit a bit de tiempo constante . ^{[ 3 ]}

Las aplicaciones posteriores de la descomposición de rutas pesadas han incluido la resolución del problema del ancestro de nivel , ^{[ 4 ]} el cálculo de la distancia de edición entre árboles, ^{[ 5 ] [ 6 ]} el dibujo de grafos y la incrustación voraz , ^{[ 7 ] [ 8 ] [ 9 ]} encontrar una ruta cerca de todos los nodos de un grafo dado, ^{[ 10 ]} el diagnóstico de fallas en redes de comunicación de fibra óptica , ^{[ 1 ]} y la decodificación de códigos basados ​​en gramática , ^{[ 11 ]} entre otros.