Accesibilidad

Si se puede llegar a un vértice desde otro en un gráfico

En teoría de grafos , la accesibilidad se refiere a la capacidad de pasar de un vértice a otro dentro de un gráfico. Un vértice puede alcanzar un vértice (y es accesible desde ) si existe una secuencia de vértices adyacentes (es decir, un recorrido ) que comienza y termina con . ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle t}$

En un gráfico no dirigido, la accesibilidad entre todos los pares de vértices se puede determinar identificando los componentes conectados del gráfico. Cualquier par de vértices en dicho gráfico pueden llegar entre sí si y sólo si pertenecen al mismo componente conectado; por lo tanto, en un gráfico de este tipo, la accesibilidad es simétrica ( alcanza si alcanza ). Los componentes conectados de un gráfico no dirigido se pueden identificar en tiempo lineal. El resto de este artículo se centra en el problema más difícil de determinar la alcanzabilidad por pares en un gráfico dirigido (que, dicho sea de paso, no tiene por qué ser simétrico). ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle s}$

Definición

Para un gráfico dirigido , con conjunto de vértices y conjunto de aristas , la relación de alcanzabilidad de es el cierre transitivo de , es decir, el conjunto de todos los pares ordenados de vértices para los cuales existe una secuencia de vértices tal que la arista está en todo . ^[1] ${\displaystyle G=(V,E)}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle G}$ ${\displaystyle E}$ ${\displaystyle (s,t)}$ ${\displaystyle V}$ ${\displaystyle v_{0}=s,v_{1},v_{2},...,v_{k}=t}$ ${\displaystyle (v_{i-1},v_{i})}$ ${\displaystyle E}$ ${\displaystyle 1\leq i\leq k}$

Si es acíclico , entonces su relación de alcanzabilidad es de orden parcial ; cualquier orden parcial puede definirse de esta manera, por ejemplo, como la relación de alcanzabilidad de su reducción transitiva . ^[2] Una consecuencia notable de esto es que, dado que los órdenes parciales son antisimétricos, si puede alcanzar , entonces sabemos que no puede alcanzar . Intuitivamente, si pudiéramos viajar de ay de regreso a , entonces contendríamos un ciclo , contradiciendo que es acíclico. Si es dirigido pero no acíclico (es decir, contiene al menos un ciclo), entonces su relación de accesibilidad corresponderá a un preorden en lugar de un orden parcial. ^[3] ${\displaystyle G}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle G}$ ${\displaystyle G}$

Algoritmos

Los algoritmos para determinar la accesibilidad se dividen en dos clases: los que requieren preprocesamiento y los que no.

Si solo tiene que realizar una (o varias) consultas, puede ser más eficiente renunciar al uso de estructuras de datos más complejas y calcular directamente la accesibilidad del par deseado. Esto se puede lograr en tiempo lineal utilizando algoritmos como la búsqueda en amplitud o la búsqueda iterativa en profundidad . ^[4]

Si va a realizar muchas consultas, puede utilizar un método más sofisticado; La elección exacta del método depende de la naturaleza del gráfico que se analiza. A cambio de tiempo de preprocesamiento y algo de espacio de almacenamiento adicional, podemos crear una estructura de datos que luego pueda responder consultas de accesibilidad en cualquier par de vértices en tan solo tiempo. A continuación se describen tres algoritmos y estructuras de datos diferentes para tres situaciones diferentes y cada vez más especializadas. ${\displaystyle O(1)}$

Algoritmo Floyd-Warshall

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

El algoritmo requiere tiempo y espacio en el peor de los casos. Este algoritmo no está interesado únicamente en la accesibilidad, sino que también calcula la distancia del camino más corto entre todos los pares de vértices. Para los gráficos que contienen ciclos negativos, las rutas más cortas pueden no estar definidas, pero aún se puede observar la accesibilidad entre pares. ${\displaystyle O(|V|^{3})}$ ${\displaystyle O(|V|^{2})}$

Algoritmo de Thorup

Para dígrafos planos , hay disponible un método mucho más rápido, como lo describió Mikkel Thorup en 2004. ^[6] Este método puede responder consultas de accesibilidad en un gráfico plano a tiempo después de dedicar tiempo de preprocesamiento para crear una estructura de datos de tamaño. Este algoritmo también puede proporcionar distancias de ruta más cortas aproximadas, así como información de ruta. ${\displaystyle O(1)}$ ${\displaystyle O(n\log {n})}$ ${\displaystyle O(n\log {n})}$

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

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

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

Para cada uno , se identifican tres separadores que, cuando se eliminan, dividen el gráfico en tres componentes, cada uno de los cuales contiene como máximo los vértices del original. Como 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. Sea este conjunto de dipaths. La prueba de que tales separadores siempre se pueden encontrar está relacionada con el teorema del separador plano de Lipton y Tarjan, y estos separadores se pueden ubicar en el tiempo lineal. ${\displaystyle G_{i}}$ ${\displaystyle 1/2}$ ${\displaystyle G_{i}}$ ${\displaystyle S}$

Para cada uno , la naturaleza dirigida de proporciona una indexación natural de sus vértices desde el principio hasta el final del camino. Para cada vértice en , ubicamos el primer vértice alcanzable por y el último vértice que llega a . Es decir, estamos analizando qué tan temprano podemos llegar desde , y qué tan lejos podemos permanecer y aun así regresar a . Esta información se almacena con cada . Luego, para cualquier par de vértices y , se puede llegar a través de si se conecta antes que si se conecta desde . ${\displaystyle Q\in S}$ ${\displaystyle Q}$ ${\displaystyle v}$ ${\displaystyle G_{i}}$ ${\displaystyle Q}$ ${\displaystyle v}$ ${\displaystyle Q}$ ${\displaystyle v}$ ${\displaystyle Q}$ ${\displaystyle v}$ ${\displaystyle Q}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle w}$ ${\displaystyle u}$ ${\displaystyle w}$ ${\displaystyle Q}$ ${\displaystyle u}$ ${\displaystyle Q}$ ${\displaystyle w}$ ${\displaystyle Q}$

Cada vértice está etiquetado como se indica arriba para cada paso de la recursividad que se construye . Como esta recursividad tiene una profundidad logarítmica, se almacena un total de información adicional por vértice. A partir de este punto, una consulta de tiempo logarítmico para determinar la accesibilidad es tan simple como buscar en cada par de etiquetas un archivo común y adecuado . Luego, el artículo original trabaja para ajustar el tiempo de consulta a . ${\displaystyle G_{0}\ldots ,G_{k}}$ ${\displaystyle O(\log {n})}$ ${\displaystyle Q}$ ${\displaystyle O(1)}$

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

Algoritmo de Kameda

Un dígrafo adecuado para el método de Kameda con y añadido. ${\displaystyle s}$ ${\displaystyle t}$

El mismo gráfico que el anterior después de ejecutar el algoritmo de Kameda, que muestra las etiquetas DFS para cada vértice.

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

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

El preprocesamiento realiza los siguientes pasos. Agregamos un nuevo vértice que tiene una arista en cada vértice de 0 grados y otro nuevo vértice con aristas de cada vértice de 0 grados. Tenga en cuenta que las propiedades de nos permiten hacerlo manteniendo la planaridad, es decir, todavía no habrá cruces de bordes después de estas adiciones. Para cada vértice almacenamos la lista de adyacencias (bordes exteriores) en orden de planaridad del gráfico (por ejemplo, en el sentido de las agujas del reloj con respecto a la incrustación del gráfico). Luego inicializamos un contador y comenzamos un recorrido en profundidad primero desde . 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 etiquetan con el valor y luego se reducen. Tenga en cuenta que siempre está etiquetado con el valor y siempre está etiquetado con . Luego se repite el recorrido en profundidad, pero esta vez la lista de adyacencia de cada vértice se visita de derecha a izquierda. ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle G}$ ${\displaystyle i=n+1}$ ${\displaystyle s}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle t}$ ${\displaystyle n+1}$ ${\displaystyle s}$ ${\displaystyle 0}$

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

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

Problemas relacionados

Un problema relacionado es resolver consultas de accesibilidad con cierta cantidad de fallas en los vértices. Por ejemplo: "¿Puede el vértice alcanzar el vértice aunque los vértices hayan fallado y ya no se puedan usar?" Un problema similar puede considerar fallas de aristas en lugar de fallas de vértices, o una combinación de ambas. La técnica de búsqueda en amplitud funciona igual de bien en este tipo de consultas, pero construir un oráculo eficiente es más desafiante. ^{[8] [9]} ${\displaystyle k}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle s_{1},s_{2},...,s_{k}}$

Otro problema relacionado con las consultas de accesibilidad es volver a calcular rápidamente los cambios en las relaciones de accesibilidad cuando se cambia alguna parte del gráfico. Por ejemplo, esta es una preocupación relevante para la recolección de basura , que necesita equilibrar la recuperación de memoria (para que pueda reasignarse) con las preocupaciones de rendimiento de la aplicación en ejecución.

Ver también

• Gammoide
• st -conectividad

Referencias

1. Skiena, Steven S. (2011), "15.5 Cierre y reducción transitivos", The Algorithm Design Manual (2ª ed.), Springer, págs. 495–497, ISBN 9781848000698.
2. Cohn, Paul Moritz (2003), Álgebra básica: grupos, anillos y campos, Springer, p. 17, ISBN 9781852335878.
3. Schmidt, Gunther (2010), Matemáticas relacionales, Enciclopedia de las matemáticas y sus aplicaciones, vol. 132, Cambridge University Press, pág. 77, ISBN 9780521762687.
4. Gersting, Judith L. (2006), Estructuras matemáticas para la informática (6ª ed.), Macmillan, p. 519, ISBN 9780716768647.
5. Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001), "Cierre transitivo de un gráfico dirigido", Introducción a los algoritmos (2ª ed.), MIT Press y McGraw-Hill, págs. 632–634, ISBN 0-262-03293-7.
6. Thorup, Mikkel (2004), "Oráculos compactos para accesibilidad y distancias aproximadas en dígrafos planos", Journal of the ACM , 51 (6): 993–1024, doi :10.1145/1039488.1039493, MR  2145261, S2CID  18864647.
7. Kameda, T (1975), "Sobre la representación vectorial de la alcanzabilidad en gráficos planos dirigidos", Cartas de procesamiento de información , 3 (3): 75–77, doi :10.1016/0020-0190(75)90019-8.
8. Demetrescu, Camil; Thorup, Mikkel ; Chowdhury, Rezaul Alam; Ramachandran, Vijaya (2008), "Oráculos para distancias que evitan un nodo o enlace fallido", SIAM Journal on Computing , 37 (5): 1299–1318, CiteSeerX 10.1.1.329.5435 , doi :10.1137/S0097539705429847, MR  2386269 .
9. Halftermeyer, Pierre, Conectividad en redes y esquemas de etiquetado compactos para planificación de emergencias, Universidad de Burdeos.