Árbol SPQR

Un árbol SPQR es una estructura de datos de árbol utilizada en informática , es decir, en algoritmos gráficos, para representar los componentes triconectados de un gráfico. Los componentes triconectados de un gráfico doblemente conectado son un sistema de gráficos más pequeños que describen todas las secciones de 2 vértices del gráfico. El árbol SPQR de un gráfico se puede construir en tiempo lineal [1] [2] y tiene algunas aplicaciones en algoritmos de gráficos dinámicos y visualización de gráficos .

La estructura básica subyacente al árbol SPQR son los componentes triconectados de un gráfico, y McLane [3] estudió por primera vez la relación entre dicha descomposición y las incrustaciones planas . Estas estructuras fueron utilizadas por otros investigadores en algoritmos eficientes [4] antes de que Di Batista y Tamassia las formalizaran como un árbol SPQR [5] [6] [7] .

Estructura

Un árbol SPQR tiene la forma de un árbol sin raíz , en el que para cada nodo x hay asociado un grafo no dirigido o multigrafo Gx . Un nodo y el gráfico asociado a él pueden ser de cuatro tipos, abreviados como SPQR:

Cada borde xy entre dos nodos del árbol SPQR está asociado con dos bordes virtuales dirigidos, uno de los cuales está en Gx y el otro en Gy . Cada arista en el gráfico G x puede ser una arista virtual como máximo para una arista del árbol SPQR.

El árbol SPQR T es un grafo G T biconexo formado de la siguiente manera. Si la arista xy del árbol SPQR vincula la arista virtual ab del gráfico G x con la arista virtual cd del gráfico G y , se forma una gráfica más grande fusionando a y c en un supervértice, fusionando b y d en otro supervértice y eliminando dos bordes virtuales. Es decir, el gráfico más grande es la suma de 2 clics G x y G y . La continuación de dicho pegado de cada borde del árbol SPQR da el gráfico G T , el orden de pegado no afecta el resultado. Cada vértice en uno de los gráficos G x puede asociarse de esta manera con un solo vértice en G T , es decir, el supervértice en el que se fusionó.

Por lo general, no se permite que dos nodos de tipo S o dos nodos de tipo P sean adyacentes dentro de un árbol SPQR, porque con tal adyacencia, dos nodos pueden fusionarse en un nodo más grande. Con este requisito, el árbol SPQR se define únicamente por un grafo, y los gráficos Gx asociados con los nodos del árbol SPQR se conocen como los componentes triconectados del grafo G.

Edificio

Un árbol SPQR de un gráfico conectado de 2 vértices dado se puede construir en tiempo lineal [1] [2] .

Hopcroft y Tarjan [1] resolvieron por primera vez el problema de construir componentes triconectados de un gráfico en tiempo lineal . Con base en este algoritmo, Di Battista y Tamassia [7] sugirieron que toda la estructura de un árbol SPQR, y solo sus componentes, pueden construirse en tiempo lineal. Después de que se incluyera la implementación del algoritmo más lento para los árboles SPQR en la biblioteca GDToolkit, Gutwenger y Mutzel [2] dieron la primera implementación del tiempo lineal. Como parte del proceso de implementación, corrigieron algunos de los trabajos anteriores de Hopcroft y Tarjan [1] .

El algoritmo de Gutwenger y Mutzel [2] incluye los siguientes pasos.

  1. Clasificamos los bordes del gráfico por pares de índices de sus vértices finales usando una variante de ordenación radix , que hace dos pasadas de ordenación por bloques (una pasada para cada extremo). Después de eso, los bordes paralelos estarán uno al lado del otro en la lista ordenada y se pueden dividir en un nodo P del árbol SPQR final, lo que simplifica el gráfico restante.
  2. Dividimos el gráfico en componentes. Estos componentes se pueden formar encontrando pares de vértices de separación y dividiendo el gráfico sobre estos dos vértices en gráficos más pequeños (con pares de bordes virtuales asociados que tienen los vértices de separación como vértices de hojas). El proceso de partición se repite hasta que haya pares sobre los que se pueda realizar la partición. La partición así obtenida no es necesariamente única, ya que las partes del grafo que deberían convertirse en S-nodos del árbol SPQR se dividen en varios triángulos.
  3. Etiquetamos cada componente de la partición con la letra P (componente de dos vértices con múltiples aristas), con la letra S (componente en forma de triángulo) o R (cualquier otro componente). Siempre que haya dos componentes que compartan un par conectado de bordes virtuales, y ambos componentes sean de tipo S o ambos componentes sean de tipo P, fusione estos componentes en un componente más grande del mismo tipo.

Gutwenger y Mutzel [2] utilizan la búsqueda en profundidad para encontrar una estructura a la que llaman "palmera". La palmera está construida sobre la base de un árbol de búsqueda en profundidad y tiene arcos del árbol de búsqueda con una orientación desde la raíz del árbol hasta las hojas, los arcos restantes (hojas de palma) están orientados hacia la raíz. Luego, Gutwenger y Mutzel buscan un orden previo de numeración especial para los nodos de la palma y usan ciertos patrones en esa numeración para identificar pares de vértices que pueden dividir el gráfico en componentes más pequeños. Si se encuentra un componente de esta manera, la pila se utiliza para identificar los bordes que deben formar parte del nuevo componente .

Uso

Encontrar secciones de 2 vértices

Con un árbol SPQR de G (sin nodos Q), uno puede encontrar directamente cada par de u y v en G cuya eliminación hace que G se desconecte pero deja componentes conectados:

Representación de todas las incrustaciones de grafos planos

Si un gráfico plano está conectado en 3, tiene una incrustación plana única hasta la elección de la cara exterior y la orientación de la incrustación; las caras de la incrustación son exactamente los ciclos del gráfico. Sin embargo, para gráficos planos conectados en 2 (con vértices y bordes etiquetados) que no están conectados en 3, puede haber más libertad para encontrar una incrustación plana. Más específicamente, si dos nodos de un árbol SPQR de un gráfico están conectados por un par de bordes virtuales, es posible cambiar la orientación de uno de los bordes con respecto al otro. Además, en un nodo de tipo P de un árbol SPQR, varias partes del gráfico asociadas con los bordes virtuales del nodo P pueden permutarse arbitrariamente. Todas las representaciones planas de un gráfico se pueden describir de esta manera [8] .

Véase también

Notas

  1. ↑ 1 2 3 4 Hopcroft, Tarjan, 1973 .
  2. ↑ 1 2 3 4 5 Gutwenger, Mutzel, 2001 .
  3. ↑ Mac Lane, 1937 .
  4. ↑ Por ejemplo, Horcroft y Tarjan ( Hopcroft, Tarjan 1973 ), Binstock y Monma ( Bienstock, Monma 1988 ). Ambos trabajos han sido citados como precursores por Di Batista y Tamassia.
  5. ↑ 1 2 3 4 Di Battista, Tamassia, 1989 .
  6. ↑ Di Battista, Tamassia, 1990 .
  7. ↑ 1 2 Di Battista, Tamassia, 1996 .
  8. ↑ Mac Lane (1937) .

Literatura

Enlaces