Representación de los componentes triconectados de un gráfico.
Un gráfico y su árbol SPQR. Las líneas discontinuas negras conectan pares de bordes virtuales, que se muestran en negro; los bordes restantes están coloreados según el componente triconectado al que pertenecen.
En 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 subyacentes 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 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 árbol SPQR por Di Battista y Tamassia (1989, 1990, 1996).
Estructura
Un árbol SPQR toma la forma de un árbol sin raíz en el que para cada nodo x hay asociado un grafo o multigrafo no dirigido Gx . El nodo y el gráfico asociado a él pueden tener uno de cuatro tipos, dadas las iniciales SPQR:
En un nodo S, el gráfico asociado es un gráfico cíclico con tres o más vértices y aristas. Este caso es análogo a la composición de series en gráficos en series paralelas ; la S significa "serie". [3]
En un nodo P, el gráfico asociado es un gráfico dipolo , un multigrafo con dos vértices y tres o más aristas, el dual plano a un gráfico cíclico. Este caso es análogo a la composición paralela en gráficos en serie-paralelos ; la P significa "paralelo". [3]
En un nodo Q, el gráfico asociado tiene una única arista real. Este caso trivial es necesario para manejar el gráfico 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 todos los bordes no virtuales estén representados por nodos Q con un borde real y otro virtual, y todos los bordes en los otros tipos de nodos deben ser virtuales.
En un nodo R, el gráfico asociado es un gráfico de 3 conexiones que no es un ciclo ni un dipolo. 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 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 borde en un gráfico Gx puede ser un borde virtual para como máximo un borde del árbol SPQR .
Un árbol SPQR T representa un gráfico G T de 2 conexiones , formado de la siguiente manera. Siempre que el borde del árbol SPQR xy asocie el borde virtual ab de G x con el borde virtual cd de G y , forme un único gráfico más grande fusionando a y c en un solo supervértice, fusionando b y d en otro único supervértice y eliminando los dos. bordes virtuales. Es decir, la gráfica más grande es la suma de 2 camarillas 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 supervértice en el que se fusionó.
Normalmente, dentro de un árbol SPQR no se permite que dos nodos S sean adyacentes, ni que dos nodos P sean adyacentes, porque si tal adyacencia ocurriera, los dos nodos podrían fusionarse en un solo nodo más grande. Con esta suposición, el árbol SPQR se determina únicamente 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 componentes triconectados de G.
Construcción
El árbol SPQR de un gráfico dado de 2 vértices conectados 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). 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 poder construirse 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 y 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.
Ordene los bordes del gráfico por los pares de índices numéricos de sus puntos finales, utilizando una variante de clasificación por base que realiza dos pasadas de clasificación por cubo , 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.
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 vinculado 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 separadores. La partición encontrada de esta manera no está definida de forma ú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 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 en 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 se encuentra un componente de esta manera, se utiliza una estructura de datos de pila para identificar los bordes que deberían formar 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 modo que eliminar u y v de G deje 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 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 formado eliminando el borde del árbol SPQR correspondiente.
Los dos vértices u y v pueden ser los dos vértices en el gráfico asociados con 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 están representados por subárboles del árbol SPQR, uno para cada borde virtual del nodo.
Los dos vértices u y v pueden ser dos vértices en el gráfico asociado con un nodo S de modo que u y v no sean adyacentes o que el borde uv sea 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 describe anteriormente. Si los dos vértices no son adyacentes, entonces 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.
Representando todas las incrustaciones de gráficos planos.
Si un gráfico plano tiene 3 conexos, tiene una incrustación plana única hasta la elección de qué cara es la cara exterior y la orientación de la incrustación: las caras de la incrustación son exactamente los ciclos no separados del gráfico. Sin embargo, para un gráfico plano (con vértices y aristas etiquetados) que está conectado por 2 pero no por 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 invertir la orientación de uno de los nodos (reemplazándolo por su imagen especular) 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
^ 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).
^ MacLane (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 (1996), "Pruebas de planaridad en línea" (PDF) , Revista SIAM de Computación , 25 (5): 956–997, doi :10.1137/S0097539794280736.
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 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).
