Á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 puede construirse en tiempo lineal ^[1] y tiene varias aplicaciones en algoritmos de grafos dinámicos y en el dibujo de grafos .

Las estructuras básicas subyacentes al árbol SPQR, los componentes triconectados de un gráfico y la conexión entre esta descomposición y las incrustaciones planares de un gráfico plano 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).

Estructura

Un árbol SPQR adopta la forma de un árbol sin raíz en el que a cada nodo x se le asocia un grafo o multigrafo no dirigido G _x . El nodo y el grafo asociado a él pueden tener uno de cuatro tipos, dadas 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 de grafos serie-paralelos ; 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 es un grafo cíclico. Este caso es análogo a la composición paralela en grafos serie-paralelos ; 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 las aristas en los otros tipos de nodos deben ser todas virtuales.
En un nodo R, el gráfico asociado es un gráfico triconexo 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 gráficos planares, el gráfico asociado de un nodo R tiene una incrustación plana ú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-conectado 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 , forme un único grafo más grande 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 más grande es la suma de 2 cliques de G _x y G _y . Realizar este paso de pegado en cada arista del árbol SPQR produce el grafo G _T ; el orden de realización de los pasos de pegado no afecta el resultado. Cada vértice en uno de los grafos G _x puede asociarse de esta manera con un vértice único en G _T , el supervértice en el que se fusionó.

Por lo general, no se permite que dentro de un árbol SPQR haya dos nodos S adyacentes, ni tampoco dos nodos P adyacentes, porque si se produjera dicha adyacencia, los dos nodos podrían fusionarse en un único nodo más grande. Con esta suposición, el árbol SPQR se determina de forma única a partir de su gráfico. Cuando un gráfico G está representado por un árbol SPQR sin nodos P adyacentes ni nodos S adyacentes, entonces los gráficos G _x asociados con los nodos del árbol SPQR se conocen como los componentes triconectados de G .

Construcción

El árbol SPQR de un gráfico dado con 2 vértices conectados 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 sólo la lista de componentes, debería ser construible en tiempo lineal. Después de que se proporcionara una implementación de un algoritmo más lento para árboles SPQR como parte de la biblioteca GDToolkit, Gutwenger y Mutzel (2001) proporcionaron la primera implementación en tiempo lineal. Como parte de este proceso de implementación de este algoritmo, también corrigieron algunos errores en el trabajo anterior de Hopcroft y Tarjan (1973).

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

Ordene los bordes del gráfico por los pares de índices numéricos de sus puntos finales, utilizando una variante de ordenación por radix que realiza dos pasadas de ordenación por cubo , una para cada punto final. Después de este paso de ordenación, los bordes paralelos entre los mismos dos vértices estarán adyacentes entre sí en la lista ordenada y se pueden dividir en un nodo P del árbol SPQR final, dejando el gráfico restante simple.
Dividir el gráfico en componentes divididos; estos son gráficos que se pueden formar al encontrar un par de vértices separadores, dividir el gráfico en estos dos vértices en dos gráficos más pequeños (con un par de aristas virtuales vinculadas que tengan los vértices separadores como puntos finales) y repetir este proceso de división hasta que no existan más pares separadores. La partición encontrada de esta manera no está definida de manera única, porque las partes del gráfico que deberían convertirse en nodos S del árbol SPQR se subdividirán en múltiples triángulos.
Etiquete 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 vinculado de aristas virtuales, y ambos componentes tienen tipo S o ambos tienen tipo P, combínelos en un solo componente más grande del mismo tipo.

Para encontrar los componentes divididos, Gutwenger y Mutzel (2001) utilizan una búsqueda en profundidad para encontrar una estructura que denominan palmera; se trata de un árbol de búsqueda en profundidad con sus aristas orientadas en dirección opuesta a la raíz del árbol, para las aristas que pertenecen al árbol, y hacia la raíz para todas las demás aristas. A continuación, encuentran una numeración especial de preorden de los nodos del árbol y utilizan ciertos patrones en esta numeración para identificar pares de vértices que pueden separar el gráfico 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 deberían formar parte del nuevo componente.

Uso

Encontrar cortes de 2 vértices

Con el árbol SPQR de un grafo G (sin Q nodos) es sencillo encontrar cada par de vértices u y v en G tales que al eliminar u y v de G se obtiene un grafo desconectado y los componentes conectados de los grafos restantes:

Los dos vértices u y v pueden ser los dos puntos finales de un borde virtual en el gráfico asociado con un nodo R, en cuyo caso los dos componentes están representados por los dos subárboles del árbol SPQR formados al eliminar el borde correspondiente del árbol SPQR.
Los dos vértices u y v pueden ser los dos vértices del grafo asociados a un nodo P que tiene dos o más aristas virtuales. En este caso, los componentes formados por la eliminación de u y v se representan mediante subárboles del árbol SPQR, uno por cada arista virtual del nodo.
Los dos vértices u y v pueden ser dos vértices en el grafo asociado con un nodo S de modo que u y v no sean adyacentes, o la arista uv sea virtual. Si la arista es virtual, entonces el par ( u , v ) también pertenece a un nodo de tipo P y R y los componentes son como se describió anteriormente. Si los dos vértices no son adyacentes, entonces los dos componentes están representados por dos caminos del grafo de ciclo asociado con el nodo S y con los nodos del árbol SPQR adjuntos a esos dos caminos.

Representación de todas las incrustaciones de gráficos planares

Si un grafo plano es 3-conexo, tiene una incrustación plana única hasta la elección de qué cara es la cara exterior y de la orientación de la incrustación: las caras de la incrustación son exactamente los ciclos no separadores del grafo. Sin embargo, para un grafo plano (con vértices y aristas etiquetados) que es 2-conexo pero no 3-conexo, puede haber mayor libertad para encontrar una incrustación plana. Específicamente, siempre que dos nodos en el árbol SPQR del grafo estén conectados por un par de aristas virtuales, es posible invertir la orientación de uno de los nodos (reemplazándolo por su imagen reflejada) en relación con el otro. Además, en un nodo P del árbol SPQR, las diferentes partes del grafo conectadas a las aristas virtuales del nodo P pueden permutarse arbitrariamente . Todas las representaciones planares pueden describirse de esta manera. ^[4]

Véase también

Árbol de corte en 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 los bordes de un gráfico
Descomposición de árboles , una generalización (ya no exclusiva) para cortes más grandes

Notas

^ ab Hopcroft y Tarjan (1973); Gutwenger y Mutzel (2001).
^ Por ejemplo, Hopcroft & Tarjan (1973) y Bienstock & Monma (1988), ambos citados como precedentes por Di Battista y Tamassia.
^ abc Di Battista y Tamassia (1989).
^ Madrid (1937).

Referencias

Bienstock, Daniel; Monma, Clyde L. (1988), "Sobre la complejidad de cubrir vértices con caras en un grafo plano", 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 de planaridad incremental", Proc. 30.º Simposio anual sobre fundamentos de la informática , págs. 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", Proc. 17th International Colloquium on Automata, Languages and Programming , Lecture Notes in Computer Science , vol. 443, Springer-Verlag, págs. 598–611, doi :10.1007/BFb0032061, ISBN 978-3-540-52826-5.
Di Battista, Giuseppe; Tamassia, Roberto (1996), "Pruebas 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 de tiempo lineal de árboles SPQR", Proc. 8th International Symposium on Graph Drawing (GD 2000) , Notas de clase en informática, vol. 1984, Springer-Verlag, págs. 77–90, doi : 10.1007/3-540-44541-2_8 , ISBN 978-3-540-41554-1.
Hopcroft, John ; Tarjan, Robert (1973), "División de un gráfico en componentes triconectados", 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.

Enlaces externos

Implementación del árbol SPQR en el marco de dibujo de gráficos abiertos.
El árbol de la implementación de Java de componentes triconectados en la biblioteca jBPT (ver clase TCTree).