Árbol SPQR

Un gráfico y su árbol SPQR. Las líneas negras discontinuas conectan pares de bordes virtuales, que se muestran en negro; los bordes restantes se colorean de acuerdo con el componente triconectado al que pertenecen.

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

Las estructuras básicas que subyacen al árbol SPQR, los componentes triconectados de un gráfico y la conexión entre esta descomposición y las incrustaciones planas de un gráfico 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 árbol SPQR por Di Battista y Tamassia ( 1989 , 1990 , 1996 ).

Estructura

Un árbol SPQR toma la forma de un árbol sin raíces en el que para cada nodo x hay asociado un gráfico no dirigido o multigrafico G _x . El nodo, y el gráfico asociado con él, pueden tener uno de cuatro tipos, dadas las iniciales SPQR:

• En un nodo S, el gráfico asociado es un gráfico de ciclo con tres o más vértices y aristas. Este caso es análogo a la composición de series en series-gráficas paralelas ; la S significa "serie". ^[3]
• En un nodo P, el gráfico asociado es un gráfico dipolo , un gráfico múltiple con dos vértices y tres o más aristas, el gráfico plano dual a un ciclo. Este caso es análogo a la composición paralela en series-gráficas paralelas ; la P significa "paralelo". ^[3]
• En un nodo Q, el gráfico asociado tiene un solo borde real. Este caso trivial es necesario para manejar el gráfico que solo tiene un borde. En algunos trabajos sobre árboles SPQR, este tipo de nodo no aparece en los árboles SPQR de gráficos con más de un borde; en otros trabajos, se requiere que todos los bordes no virtuales estén representados por nodos Q con un borde real y uno virtual, y los bordes en los otros tipos de nodos deben ser todos virtuales.
• En un nodo R, el gráfico asociado es un gráfico de 3 conexiones 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 planos, el gráfico asociado de un nodo R tiene una incrustación plana única. ^[3]

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

Un árbol T de SPQR representa un gráfico G _{T de} 2 conexiones , formado de la siguiente manera. Siempre que los bordes árbol SPQR xy asociados el borde virtual ab de G _x con el borde virtual cd de G _y , formar un único gráfico más grande mediante la fusión de una y c en una sola supervertex, la fusión de b y d en otro solo supervertex, y eliminación de los dos bordes virtuales. Es decir, la gráfica más grande es la suma de 2 clicas de G _x y G _y. Al realizar este paso de pegado en cada borde del árbol SPQR se produce el gráfico G _T ; el orden de realización de los pasos de pegado no afecta el resultado. Cada vértice en uno de los gráficos G _x puede asociarse de esta manera con un vértice único en G _T , el supervertex en el que se fusionó.

Por lo general, no se permite dentro de un árbol SPQR que dos nodos S sean adyacentes, ni que dos nodos P sean adyacentes, porque si ocurriera tal adyacencia, los dos nodos podrían fusionarse en un solo nodo más grande. Con esta suposición, el árbol SPQR se determina de forma única a partir de su gráfico. Cuando una gráfica G está representado por un árbol SPQR con ningún nodo P adyacentes y no hay nodos S adyacentes, a continuación, los gráficos G _{x Se} asociados con los nodos del árbol SPQR son conocidos como los componentes triconnected de G .

Construcción

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

El problema de construir los componentes triconectados de un gráfico fue resuelto por primera vez en tiempo lineal por Hopcroft y Tarjan (1973) . Con base en este algoritmo, Di Battista y Tamassia (1996) sugirieron que la estructura de árbol SPQR completa, y no solo la lista de componentes, debería ser construible en tiempo lineal. Después de que se proporcionó una implementación de un algoritmo más lento para árboles SPQR como parte de la biblioteca GDToolkit , Gutwenger & Mutzel (2001) proporcionaron la primera implementación de 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.

1. Ordene los bordes del gráfico por los pares de índices numéricos de sus puntos finales, utilizando una variante de ordenación por base que hace dos pasadas de ordenación por cubeta , una para cada punto final. Después de este paso de clasificación, los bordes paralelos entre los mismos dos vértices serán adyacentes entre sí en la lista ordenada y se pueden dividir en un nodo P del eventual árbol SPQR, dejando el gráfico restante simple.
2. Divida el gráfico en componentes divididos; Estos son gráficos que se pueden formar encontrando un par de vértices de separación, dividiendo el gráfico en estos dos vértices en dos gráficos más pequeños (con un par enlazado de aristas virtuales que tienen los vértices de separación como puntos finales) y repitiendo este proceso de división hasta que no haya más existen pares de separación. 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.
3. 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 bien existen dos componentes divididos que comparten un par vinculado de bordes virtuales, y ambos componentes tienen el tipo S o ambos tienen el tipo P, combínelos en un solo componente más grande del mismo tipo.

Para encontrar los componentes divididos, Gutwenger y Mutzel (2001) utilizan la búsqueda en profundidad para encontrar una estructura a la que llaman palmera; este es un árbol de búsqueda de profundidad con sus bordes orientados lejos de la raíz del árbol, para los bordes que pertenecen al árbol, y hacia la raíz para todos los demás bordes. Luego, encuentran una numeración de preorden especial de los nodos en el árbol y usan 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 un componente se encuentra de esta manera, se usa una estructura de datos de pila para identificar los bordes que deberían ser parte del nuevo componente.

Uso

Encontrar cortes de 2 vértices

Con el árbol SPQR de un gráfico G (sin Q nodos) es sencillo encontrar cada par de vértices u y v en G de manera que quitar u y v de G deja un gráfico desconectado, y los componentes conectados de los gráficos restantes:

• Los dos vértices u y v pueden ser los dos puntos extremos 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 árbol SPQR correspondiente.
• Los dos vértices u y v pueden ser los dos vértices en el gráfico asociado con un nodo de P que tiene dos o más virtuales bordes. En este caso los componentes formados por la eliminación de u y v son representados por subárboles del árbol SPQR, uno para cada borde virtual en el nodo.
• Los dos vértices u y v pueden ser dos vértices en el gráfico asociado con un nodo de S de tal manera que sea u y v no son adyacentes, o el borde uv es virtual. Si el borde 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, los dos componentes están representados por dos caminos del gráfico de ciclo asociados con el nodo S y con los nodos del árbol SPQR adjuntos a esos dos caminos.

Representar todas las incrustaciones de gráficos planos

Si un gráfico plano está conectado en 3, 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 de no separación del gráfico. Sin embargo, para un gráfico plano (con vértices y bordes etiquetados) que está conectado en 2 pero no en 3, puede haber mayor libertad para encontrar una incrustación plana. Específicamente, siempre que dos nodos en el árbol SPQR del gráfico están conectados por un par de bordes virtuales, es posible cambiar 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 gráfico conectadas a los bordes virtuales del nodo P pueden permutarse arbitrariamente. Todas las representaciones planas pueden describirse de esta manera. ^[4]

Ver también

• Árbol de corte en bloque , 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 borde de un gráfico
• Descomposición de árboles , una generalización (ya no única) a cortes más grandes

Notas

1. Hopcroft y Tarjan (1973) ; Gutwenger y Mutzel (2001) .
2. Por ejemplo, Hopcroft & Tarjan (1973) y Bienstock & Monma (1988) , ambos citados como precedentes por Di Battista y Tamassia.
3. Di Battista y Tamassia (1989) .
4. Mac Lane (1937) .

Referencias

• Bienstock, Daniel; Monma, Clyde L. (1988), "Sobre la complejidad de cubrir vértices por caras en un gráfico 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), "Prueba de planaridad incremental", Proc. 30º Simposio anual sobre los fundamentos de la informática , págs. 436–441, doi : 10.1109 / SFCS.1989.63515.
• Di Battista, Giuseppe; Tamassia, Roberto (1990), "Algoritmos de gráficos en línea con árboles SPQR", Proc. XVII Coloquio Internacional sobre Autómatas, Lenguajes y Programación , Lecture Notes in Computer Science , 443 , Springer-Verlag, págs. 598–611, doi : 10.1007 / BFb0032061.
• 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 de tiempo lineal de árboles SPQR", Proc. Octavo Simposio Internacional sobre Dibujo de Gráficos (GD 2000) , Lecture Notes in Computer Science, 1984 , Springer-Verlag, págs. 77–90, doi : 10.1007 / 3-540-44541-2_8.
• Hopcroft, John ; Tarjan, Robert (1973), "Dividing a graph into triconnected components", SIAM Journal on Computing , 2 (3): 135–158, doi : 10.1137 / 0202012 , hdl : 1813/6037.
• Mac Lane, Saunders (1937), "Una caracterización estructural de gráficos combinatorios planos", Duke Mathematical Journal , 3 (3): 460–472, doi : 10.1215 / S0012-7094-37-00336-3.

enlaces externos

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