Accesibilidad

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

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

En un grafo no dirigido, la alcanzabilidad entre todos los pares de vértices se puede determinar identificando los componentes conectados del grafo. Cualquier par de vértices en un grafo de este tipo puede alcanzarse entre sí si y solo si pertenecen al mismo componente conectado; por lo tanto, en un grafo de este tipo, la alcanzabilidad es simétrica ( alcanza si y solo si alcanza ). Los componentes conectados de un grafo 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 grafo dirigido (que, por cierto, no necesita ser simétrico). ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle s}$

Definición

Para un grafo dirigido , con un conjunto de vértices y un 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 en para los cuales existe una secuencia de vértices tales que la arista está en para 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 un 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 desde hasta y volver a , entonces contendría un ciclo , lo que contradice que es acíclico. Si es dirigido pero no acíclico (es decir, contiene al menos un ciclo), entonces su relación de alcanzabilidad corresponderá a un preorden en lugar de a 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: aquellos que requieren preprocesamiento y aquellos que no.

Si solo tiene que realizar una (o varias) consultas, puede resultar más eficiente prescindir del 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 en profundidad iterativa . ^[4]

Si se van a realizar muchas consultas, se 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 pueda responder a consultas de accesibilidad en cualquier par de vértices en tan solo un 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 solo se interesa por la accesibilidad, ya que también calcula la distancia de ruta más corta 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 la accesibilidad entre pares aún puede observarse. ${\displaystyle O(|V|^{3})}$ ${\displaystyle O(|V|^{2})}$

Algoritmo de Thorup

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

El enfoque general consiste en asociar a cada vértice un conjunto relativamente pequeño de los denominados 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 presenta un esquema de las secciones relacionadas con la accesibilidad. ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle v}$ ${\displaystyle w}$

Dado un grafo , el algoritmo comienza organizando los vértices en capas comenzando desde un vértice arbitrario . Las capas se construyen en pasos alternos considerando primero todos los vértices alcanzables desde el paso anterior (comenzando con solo ) y luego todos los vértices que llegan al paso anterior hasta que todos los vértices hayan sido asignados a una capa. Por construcción de las capas, cada vértice aparece como máximo en dos capas, y cada camino dirigido , o dipath, en 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}$

El grafo se vuelve a expresar entonces como una serie de dígrafos donde cada uno y donde es la contracción de todos los niveles anteriores en un único vértice. Debido a que cada dipath aparece en dos capas consecutivas como máximo, y debido a que cada uno está formado por dos capas consecutivas, cada dipath en aparece en su totalidad en al menos uno (y no más de 2 de dichos grafos consecutivos) ${\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 , se identifican tres separadores que, cuando se eliminan, dividen el grafo en tres componentes que contienen, cada uno, como máximo, los vértices del original. Como se construye a partir de dos capas de dipaths opuestos, cada separador puede constar de hasta 2 dipaths, para un total de hasta 6 dipaths sobre todos los separadores. Sea este conjunto de dipaths. La prueba de que siempre se pueden encontrar dichos separadores está relacionada con el Teorema del Separador Planar de Lipton y Tarjan, y estos separadores se pueden ubicar en tiempo lineal. ${\displaystyle G_{i}}$ ${\displaystyle 1/2}$ ${\displaystyle G_{i}}$ ${\displaystyle S}$

Para cada , la naturaleza dirigida de proporciona una indexación natural de sus vértices desde el inicio hasta el final de la ruta. Para cada vértice en , ubicamos el primer vértice en alcanzable por , y el último vértice en que llega a . Es decir, estamos viendo qué tan pronto en podemos llegar desde , y qué tan lejos podemos permanecer en y aún así regresar a . Esta información se almacena con cada . Luego, para cualquier par de vértices y , puede llegar a través de si se conecta a antes de que 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 se etiqueta como se indica más arriba para cada paso de la recursión que construye . Como esta recursión tiene 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 alcanzar la accesibilidad es tan simple como buscar en cada par de etiquetas un . El artículo original luego trabaja para ajustar el tiempo de consulta a . ${\displaystyle G_{0}\ldots ,G_{k}}$ ${\displaystyle O(\log {n})}$ ${\displaystyle Q}$ ${\displaystyle O(1)}$

Para resumir el análisis de este método, primero se debe considerar que el enfoque de capas divide los vértices de modo que cada vértice se considera 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 recursión, solo se necesita trabajo lineal para identificar los separadores, así como las conexiones posibles 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 agregado. ${\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

Un método aún más rápido para el preprocesamiento, debido a T. Kameda en 1975, ^[7] se puede utilizar si el gráfico 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 dividir el límite de esa cara en dos partes de modo 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 exhibe 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 grado 0 de entrada y otro nuevo vértice con aristas en cada vértice de grado 0 de salida. Tenga en cuenta que las propiedades de nos permiten 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 de salida) 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 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 se extraen los vértices de la pila del recorrido, se etiquetan con el valor y luego se decrementa. Tenga en cuenta que siempre se etiqueta con el valor y siempre se etiqueta con . Luego se repite el recorrido en profundidad, pero esta vez se visita la lista de adyacencia de cada vértice 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 aristas incidentes, se eliminan. Cada vértice restante almacena una etiqueta bidimensional con valores de a . Dados dos vértices y , y sus etiquetas y , decimos que si y solo 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 entonces establece que es alcanzable desde si y sólo 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 una cierta cantidad de fallas de vértices. Por ejemplo: "¿Puede un vértice alcanzar otro vértice a pesar de que los vértices han fallado y ya no se pueden usar?" Un problema similar puede considerar fallas de aristas en lugar de fallas de vértices, o una combinación de las dos. La técnica de búsqueda en amplitud funciona igual de bien en tales 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 el de tener que volver a calcular rápidamente los cambios en las relaciones de accesibilidad cuando se modifica alguna parte del gráfico. Por ejemplo, esto es un problema importante 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.

Véase también

• Gamoide
• st -conectividad

Referencias

1. Skiena, Steven S. (2011), "15.5 Cierre transitivo y reducción", Manual de diseño de algoritmos (2.ª ed.), Springer, págs. 495-497, ISBN 9781848000698.
2. Cohn, Paul Moritz (2003), Álgebra básica: grupos, anillos y campos, Springer, pág. 17, ISBN 9781852335878.
3. Schmidt, Gunther (2010), Matemáticas relacionales, Enciclopedia de 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ág. 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 alcanzabilidad y distancias aproximadas en dígrafos planares", 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 grafos dirigidos planares", Information Processing Letters , 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 la planificación de emergencias, Universidad de Burdeos.