Árbol PQ

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 17 de septiembre de 2015; las comprobaciones requieren 4 ediciones .

Un árbol PQ  es una estructura de datos para representar un grupo de permutaciones . Este es un árbol plano enraizado . Los vértices colgantes en él representan elementos permutables. El resto de los vértices están etiquetados como , o . Los vértices marcados tienen al menos 3 hijos y los vértices marcados tienen al menos 2 hijos. En un árbol PQ, se permite reorganizar los descendientes de un vértice marcado arbitrariamente e invertir el orden de los descendientes de un vértice marcado como .

Los árboles PQ se utilizan para encontrar permutaciones, cuyas restricciones se conocen gradualmente, una por una. Tales problemas surgen cuando se recrea el ADN y se verifica la planitud de un gráfico.

Artículos