Accesibilidad

El algoritmo de Floyd-Warshall ^{[ 5 ]} se puede utilizar para calcular el cierre transitivo de cualquier grafo dirigido, lo que da lugar a la relación de alcanzabilidad como en la definición anterior.

El algoritmo requiere${\displaystyle O(|V|^{3})}$tiempo y${\displaystyle O(|V|^{2})}$espacio en el peor de los casos. Este algoritmo no solo se interesa en la alcanzabilidad, sino que también calcula la distancia del camino más corto entre todos los pares de vértices. Para grafos que contienen ciclos negativos, los caminos más cortos pueden no estar definidos, pero aún se puede observar la alcanzabilidad entre pares.

Para digrafos planares , existe un método mucho más rápido, como lo describió Mikkel Thorup en 2004. ^{[ 6 ]} Este método puede responder consultas de alcanzabilidad en un grafo planar en${\displaystyle O(1)}$tiempo después de pasar${\displaystyle O(n\log {n})}$tiempo de preprocesamiento para crear una estructura de datos de${\displaystyle O(n\log {n})}$tamaño. Este algoritmo también puede proporcionar distancias aproximadas de la ruta más corta, así como información de ruta.

El enfoque general consiste en asociar a cada vértice un conjunto relativamente pequeño de los llamados caminos separadores, de modo que cualquier camino desde un vértice${\displaystyle v}$a cualquier otro vértice${\displaystyle w}$debe pasar por al menos uno de los separadores asociados con${\displaystyle v}$o${\displaystyle w}$A continuación se presenta un resumen de las secciones relacionadas con la accesibilidad.

Dado un gráfico${\displaystyle G}$El algoritmo comienza organizando los vértices en capas a partir de un vértice arbitrario.${\displaystyle v_{0}}$Las capas se construyen en pasos alternos considerando primero todos los vértices alcanzables desde el paso anterior (comenzando con solo${\displaystyle v_{0}}$) y luego todos los vértices que llegan al paso anterior hasta que todos los vértices se hayan asignado a una capa. Por la construcción de las capas, cada vértice aparece como máximo en dos capas, y cada camino dirigido , o dipath, en${\displaystyle G}$está contenido dentro de dos capas adyacentes${\displaystyle L_{i}}$y${\displaystyle L_{i+1}}$. Dejar${\displaystyle k}$ser la última capa creada, es decir, el valor más bajo para${\displaystyle k}$de tal manera que${\displaystyle \bigcup _{i=0}^{k}L_{i}=V}$.

El gráfico se reexpresa entonces como una serie de digrafos.${\displaystyle G_{0},G_{1},\ldots ,G_{k-1}}$donde cada${\displaystyle G_{i}=r_{i}\cup L_{i}\cup L_{i+1}}$y dónde${\displaystyle r_{i}}$es la contracción de todos los niveles anteriores${\displaystyle L_{0}\ldots L_{i-1}}$en un solo vértice. Porque cada dipath aparece en como máximo dos capas consecutivas, y porque cada${\displaystyle G_{i}}$está formada por dos capas consecutivas, cada dipath en${\displaystyle G}$aparece en su totalidad en al menos uno${\displaystyle G_{i}}$(y no más de 2 gráficos consecutivos de este tipo)

Para cada${\displaystyle G_{i}}$Se identifican tres separadores que, al ser eliminados, dividen el gráfico en tres componentes que contienen como máximo${\displaystyle 1/2}$los vértices del original. Como${\displaystyle G_{i}}$está construido a partir de dos capas de dipaths opuestos, cada separador puede constar de hasta 2 dipaths, para un total de hasta 6 dipaths en todos los separadores.${\displaystyle S}$Sea este conjunto de dipaths. La prueba de que tales separadores siempre se pueden encontrar está relacionada con el Teorema del Separador Planar de Lipton y Tarjan, y estos separadores se pueden localizar en tiempo lineal.

Para cada${\displaystyle Q\in S}$, la naturaleza dirigida de${\displaystyle Q}$proporciona una indexación natural de sus vértices desde el inicio hasta el final del camino. Para cada vértice${\displaystyle v}$en${\displaystyle G_{i}}$, localizamos el primer vértice en${\displaystyle Q}$accesible por${\displaystyle v}$y el último vértice en${\displaystyle Q}$que llega a${\displaystyle v}$. Es decir, estamos analizando cuán temprano en${\displaystyle Q}$podemos obtener de${\displaystyle v}$y hasta qué punto podemos permanecer en${\displaystyle Q}$y aún así volver a${\displaystyle v}$Esta información se almacena con cada${\displaystyle v}$. Entonces, para cualquier par de vértices${\displaystyle u}$y${\displaystyle w}$,${\displaystyle u}$puede alcanzar${\displaystyle w}$a través de${\displaystyle Q}$si${\displaystyle u}$se conecta a${\displaystyle Q}$antes que${\displaystyle w}$conecta desde${\displaystyle Q}$.

Cada vértice está etiquetado como arriba para cada paso de la recursión que construye ${\displaystyle G_{0}\ldots ,G_{k}}$. Como esta recursión tiene profundidad logarítmica, un total de ${\displaystyle O(\log {n})}$Se almacena información adicional por vértice. A partir de este punto, una consulta de tiempo logarítmico para la alcanzabilidad es tan simple como examinar cada par de etiquetas para encontrar una común y adecuada.${\displaystyle Q}$El artículo original luego trabaja para reducir el tiempo de consulta a${\displaystyle O(1)}$.

Al resumir el análisis de este método, primero considere que el enfoque de capas particiona los vértices de manera que cada vértice se considera únicamente${\displaystyle O(1)}$ veces. La fase separadora del algoritmo divide el grafo en componentes que son como máximo${\displaystyle 1/2}$el tamaño del grafo original, lo que resulta en una profundidad de recursión logarítmica. En cada nivel de la recursión, solo se necesita trabajo lineal para identificar los separadores, así como las posibles conexiones entre vértices. El resultado general es${\displaystyle O(n\log n)}$tiempo de preprocesamiento con solo ${\displaystyle O(\log {n})}$Información adicional almacenada para cada vértice.

Un método aún más rápido para el preprocesamiento, debido a T. Kameda en 1975, ^{[ 7 ]} se puede utilizar si el grafo es planar , acíclico y también exhibe las siguientes propiedades adicionales: todos los vértices de grado de entrada 0 y todos los vértices de grado de salida 0 aparecen en la misma cara (a menudo se supone que es la cara exterior), y es posible particionar el límite de esa cara en dos partes de manera que todos los vértices de grado de entrada 0 aparezcan en una parte, y todos los vértices de grado de salida 0 aparezcan en la otra (es decir, los dos tipos de vértices no se alternan).

Si${\displaystyle G}$exhibe estas propiedades, entonces podemos preprocesar el gráfico en solo ${\displaystyle O(n)}$tiempo y tienda solamente${\displaystyle O(\log {n})}$bits adicionales por vértice, respondiendo a consultas de alcanzabilidad para cualquier par de vértices en${\displaystyle O(1)}$tiempo con una simple comparación.

El preprocesamiento realiza los siguientes pasos. Añadimos un nuevo vértice.${\displaystyle s}$que tiene una arista a cada vértice de grado 0, y otro nuevo vértice${\displaystyle t}$con aristas desde cada vértice de grado 0. Tenga en cuenta que las propiedades de${\displaystyle G}$Esto nos permite hacerlo manteniendo la planaridad, es decir, no habrá cruces de aristas después de estas adiciones. Para cada vértice almacenamos la lista de adyacencias (aristas salientes) en orden de la planaridad del grafo (por ejemplo, en sentido horario con respecto a la incrustación del grafo). Luego inicializamos un contador.${\displaystyle i=n+1}$y comenzar un recorrido en profundidad desde${\displaystyle s}$Durante este recorrido, la lista de adyacencia de cada vértice se visita de izquierda a derecha según sea necesario. A medida que los vértices se extraen de la pila del recorrido, se les etiqueta con el valor${\displaystyle i}$, y${\displaystyle i}$Luego se decrementa. Tenga en cuenta que${\displaystyle t}$siempre está etiquetado con el valor${\displaystyle n+1}$y${\displaystyle s}$siempre está etiquetado con${\displaystyle 0}$A continuación, se repite el recorrido en profundidad, pero esta vez se visita la lista de adyacencia de cada vértice de derecha a izquierda.

Cuando se complete,${\displaystyle s}$y${\displaystyle t}$y sus aristas incidentes, se eliminan. Cada vértice restante almacena una etiqueta bidimensional con valores de${\displaystyle 1}$a${\displaystyle n}$Dados dos vértices${\displaystyle u}$y${\displaystyle v}$y sus etiquetas${\displaystyle L(u)=(a_{1},a_{2})}$y${\displaystyle L(v)=(b_{1},b_{2})}$, decimos que${\displaystyle L(u)<L(v)}$si y solo si${\displaystyle a_{1}\leq b_{1}}$,${\displaystyle a_{2}\leq b_{2}}$y existe al menos un componente${\displaystyle a_{1}}$o${\displaystyle a_{2}}$lo cual es estrictamente menor que${\displaystyle b_{1}}$o${\displaystyle b_{2}}$, respectivamente.

El resultado principal de este método establece entonces que${\displaystyle v}$es accesible desde${\displaystyle u}$si y solo si${\displaystyle L(u)<L(v)}$, que se calcula fácilmente en${\displaystyle O(1)}$tiempo.