Árbol SPQR

En la teoría de grafos , una rama de las matemáticas, los componentes triconectados de un grafo biconectado son un sistema de grafos más pequeños que describen todos los cortes de 2 vértices en el grafo. Un árbol SPQR es una estructura de datos de árbol utilizada en informática , y más específicamente en algoritmos de grafos , para representar los componentes triconectados de un grafo. El árbol SPQR de un grafo se puede construir en tiempo lineal ^{[ 1 ]} y tiene varias aplicaciones en algoritmos de grafos dinámicos y dibujo de grafos .

Las estructuras básicas subyacentes al árbol SPQR, los componentes triconectados de un grafo y la conexión entre esta descomposición y las incrustaciones planares de un grafo planar , fueron investigadas por primera vez por Saunders Mac Lane ( 1937 ) ; estas estructuras fueron utilizadas en algoritmos eficientes por varios otros investigadores ^{[ 2 ]} antes de su formalización como el árbol SPQR por Di Battista y Tamassia ( 1989 , 1990 , 1996 ) .  

Un árbol SPQR tiene la forma de un árbol sin raíz en el que a cada nodo x se le asocia un grafo no dirigido o multigrafo G _x . El nodo, y el grafo asociado a él, pueden tener uno de cuatro tipos, según las iniciales SPQR:

• En un nodo S, el grafo asociado es un grafo cíclico con tres o más vértices y aristas. Este caso es análogo a la composición en serie en grafos serie-paralelo ; la S significa "serie". ^{[ 3 ]}
• En un nodo P, el grafo asociado es un grafo dipolar , un multigrafo con dos vértices y tres o más aristas, el dual planar de un grafo cíclico. Este caso es análogo a la composición paralela en grafos serie-paralelo ; la P significa "paralelo". ^{[ 3 ]}
• En un nodo Q, el grafo asociado tiene una única arista real. Este caso trivial es necesario para manejar el grafo que tiene una sola arista. En algunos trabajos sobre árboles SPQR, este tipo de nodo no aparece en los árboles SPQR de grafos con más de una arista; en otros trabajos, se requiere que todas las aristas no virtuales estén representadas por nodos Q con una arista real y una virtual, y que las aristas en los demás tipos de nodos sean todas virtuales.
• En un nodo R, el grafo asociado es un grafo 3-conectado que no es un ciclo ni un dipolo. La R significa "rígido": en la aplicación de árboles SPQR en la incrustación de grafos planares, el grafo asociado de un nodo R tiene una incrustación planar única. ^{[ 3 ]}

Cada arista xy entre dos nodos del árbol SPQR está asociada con dos aristas virtuales dirigidas , una de las cuales es una arista en G _x y la otra es una arista en G _y . Cada arista en un grafo G _x puede ser una arista virtual para como máximo una arista del árbol SPQR.

Un árbol SPQR T representa un grafo 2-conexo G _T , formado de la siguiente manera. Siempre que la arista xy del árbol SPQR asocie la arista virtual ab de G _x con la arista virtual cd de G _y , se forma un único grafo mayor fusionando a y c en un único supervértice, fusionando b y d en otro único supervértice y eliminando las dos aristas virtuales. Es decir, el grafo mayor es la suma de 2-cliques de G _x y G _y . Al realizar este paso de pegado en cada arista del árbol SPQR se obtiene el grafo G _T ; el orden en que se realizan los pasos de pegado no afecta al resultado. Cada vértice en uno de los grafos G _x puede asociarse de esta manera con un único vértice en G _T , el supervértice en el que se fusionó.

Normalmente, en un árbol SPQR no se permite que dos nodos S sean adyacentes, ni que dos nodos P lo sean, ya que si se produjera tal adyacencia, los dos nodos podrían fusionarse en un único nodo mayor. Bajo esta premisa, el árbol SPQR se determina de forma única a partir de su grafo. Cuando un grafo G se representa mediante un árbol SPQR sin nodos P adyacentes ni nodos S adyacentes, entonces los grafos G _x asociados a los nodos del árbol SPQR se conocen como los componentes triconectados de G.

El árbol SPQR de un grafo conexo de 2 vértices dado se puede construir en tiempo lineal . ^{[ 1 ]}

El problema de construir los componentes triconectados de un grafo fue resuelto por primera vez en tiempo lineal por Hopcroft y Tarjan (1973) . Basándose en este algoritmo, Di Battista y Tamassia (1996) sugirieron que la estructura completa del árbol SPQR, y no solo la lista de componentes, debería poder construirse en tiempo lineal. Tras la inclusión de una implementación de un algoritmo más lento para árboles SPQR en la biblioteca GDToolkit, Gutwenger y Mutzel (2001) proporcionaron la primera implementación en tiempo lineal. Durante este proceso de implementación, también corrigieron algunos errores del trabajo anterior de Hopcroft y Tarjan (1973) .

El algoritmo de Gutwenger y Mutzel (2001) incluye los siguientes pasos generales.

1. Ordena las aristas del grafo según los pares de índices numéricos de sus extremos, utilizando una variante del algoritmo de ordenación por radix que realiza dos pasadas del algoritmo de ordenación por cubetas , una para cada extremo. Tras este paso de ordenación, las aristas paralelas entre los mismos dos vértices serán adyacentes en la lista ordenada y podrán separarse en un nodo P del árbol SPQR resultante, lo que simplifica el grafo restante.
2. Dividir el grafo en componentes separados; estos son grafos que se pueden formar encontrando un par de vértices separadores, dividiendo el grafo en estos dos vértices en dos grafos más pequeños (con un par de aristas virtuales enlazadas que tienen los vértices separadores como extremos) y repitiendo este proceso de división hasta que no existan más pares separadores. La partición encontrada de esta manera no está definida de forma única, ya que las partes del grafo que deberían convertirse en nodos S del árbol SPQR se subdividirán en múltiples triángulos.
3. Etiqueta cada componente dividido con una P (un componente dividido de dos vértices con múltiples aristas), una S (un componente dividido en forma de triángulo) o una R (cualquier otro componente dividido). Si existen dos componentes divididos que comparten un par de aristas virtuales vinculadas, y ambos componentes son de tipo S o ambos son de tipo P, combínalos en un único componente más grande del mismo tipo.

Para encontrar los componentes divididos, Gutwenger y Mutzel (2001) utilizan una búsqueda en profundidad para hallar una estructura que denominan árbol de palmeras. Este árbol, construido mediante búsqueda en profundidad, tiene sus aristas orientadas desde la raíz, en el caso de las aristas que pertenecen al árbol, y hacia la raíz para todas las demás. A continuación, encuentran una numeración de preorden especial para los nodos del árbol y utilizan ciertos patrones en esta numeración para identificar pares de vértices que pueden separar el grafo en componentes más pequeños. Cuando se encuentra un componente de esta manera, se utiliza una estructura de datos de pila para identificar las aristas que deben formar parte del nuevo componente.

• Árbol de corte de bloques , una estructura de árbol similar para los componentes conectados por 2 vértices.
• Árbol de Gomory-Hu , una estructura de árbol diferente que caracteriza la conectividad de las aristas de un grafo.
• Descomposición de árboles , una generalización (ya no exclusiva) a cortes más grandes

• Bienstock, Daniel; Monma, Clyde L. (1988), "Sobre la complejidad de cubrir vértices con caras en un grafo planar", SIAM Journal on Computing , 17 (1): 53–76 , CiteSeerX 10.1.1.542.2314 , doi : 10.1137/0217004 .
• Di Battista, Giuseppe; Tamassia, Roberto (1989), "Pruebas incrementales de planaridad", Actas del 30.º Simposio Anual sobre Fundamentos de la Informática , pp. 436–441 , doi : 10.1109/SFCS.1989.63515 , ISBN  0-8186-1982-1.
• Di Battista, Giuseppe; Tamassia, Roberto (1990), "Algoritmos de grafos en línea con árboles SPQR", Actas del 17.º Coloquio Internacional sobre Autómatas, Lenguajes y Programación , Lecture Notes in Computer Science , vol.  443, Springer-Verlag, pp. 598–611 , doi : 10.1007/BFb0032061 , ISBN  978-3-540-52826-5.
• Di Battista, Giuseppe; Tamassia, Roberto (1996), "Prueba de planaridad en línea" (PDF) , SIAM Journal on Computing , 25 (5): 956–997 , doi : 10.1137/S0097539794280736.
• Gutwenger, Carsten; Mutzel, Petra (2001), "Una implementación en tiempo lineal de árboles SPQR", Actas del 8.º Simposio Internacional sobre Dibujo de Grafos (GD 2000) , Lecture Notes in Computer Science, vol.  1984, Springer-Verlag, pp. 77–90 , doi : 10.1007/3-540-44541-2_8 , ISBN  978-3-540-41554-1.
• Hopcroft, John ; Tarjan, Robert (1973), "Dividiendo un grafo en componentes triconectadas", SIAM Journal on Computing , 2 (3): 135–158 , doi : 10.1137/0202012 , hdl : 1813/6037.
• Mac Lane, Saunders (1937), "Una caracterización estructural de grafos combinatorios planares", Duke Mathematical Journal , 3 (3): 460– 472, doi : 10.1215/S0012-7094-37-00336-3.

• Implementación del árbol SPQR en el marco de dibujo de Open Graph.
• El árbol de componentes triconectados Implementación en Java en la biblioteca jBPT (ver clase TCTree).