En teoría de grafos , para un grafo conectado con k G = (V, E), un subconjunto de aristasse considera un certificado para la k-conectividad del gráfico G si y solo si el subgrafo G '= (V, E') está k-conectado . [1]
Certificados escasos
Para un grafo conectado con k con n vértices , siempre existe un certificado de conectividad k con como máximo k (n-1) aristas. Los certificados de conectividad K se consideran escasos si contienen bordes O ( kn ). [2] En esta figura, el gráfico de la derecha también es un certificado escaso para el gráfico G de la izquierda.
Búsqueda de escaneo primero
Scan-First es un algoritmo para la construcción paralela de certificados de conectividad k para gráficos. Fue introducido en el documento Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for K-Vertex Connectivity por Joseph Cheriyan, Ming-Yang Kao y Ramakrishna Thurimella. [2] El algoritmo Scan-First Search mejora el tiempo de ejecución de la construcción de un certificado escaso para k-conectividad utilizando el modelo de cálculo paralelo.
Podemos encontrar un certificado escaso para k-conectividad ejecutando iterativamente la búsqueda primero de escaneo k veces en los subgráficos de nuestro gráfico de entrada. Nuestra entrada es un gráfico G = (V, E) y un vértice raíz r. Para cada iteración de búsqueda de escaneo primero, primero calculamos un árbol de expansión T de nuestro gráfico de entrada G, y asignamos una numeración de preorden a todos los vértices, que usaremos como nuestro orden de escaneo. Desde nuestra raíz r, primero escaneamos r, lo que implica marcar todos sus vértices vecinos.
Dado un gráfico no dirigido conectado y un vértice especificado, una búsqueda de exploración primero en el gráfico a partir del vértice especificado es una forma sistemática de marcar los vértices. El paso principal de marcado se llama escanear : escanear un vértice marcado significa marcar todos los vecinos previamente no marcados de ese vértice. Al comienzo de la búsqueda, solo se marca el vértice inicial especificado. Luego, la búsqueda escanea iterativamente un vértice marcado y no escaneado hasta que se escanean todos los vértices.
Una búsqueda de exploración primero en un gráfico conectado no dirigido produce un árbol de expansión definido de la siguiente manera. Al comienzo de la búsqueda, el árbol está vacío. Luego, para cada vértice x en el gráfico, cuando se escanea x, todos los bordes entre x y sus vecinos previamente no marcados se agregan al árbol; los bordes entre xy sus vecinos previamente marcados no se agregan al árbol.
Todos los vértices previamente no marcados constituyen el punto final de una arista desde el vértice actualmente escaneado, por lo que si partimos de algún vértice v, y tiene vecinos w y x, entonces si w y x no están marcadas, creamos las aristas (v , w) y (v, x) y agréguelos a nuestro árbol de salida T '. Si w o x se marcó previamente, no agregamos el borde que incluye ese vértice a T '. Con estos nuevos bordes en T ', nos movemos al siguiente vértice con el número de preorden más bajo para escanear, lo que implica marcar continuamente vértices sin marcar previamente y agregar los bordes del vértice actual a estos vértices a nuestro árbol de salida.
Usamos la búsqueda de escaneo primero para generar certificados para k-conectividad ejecutándolo para k iteraciones. Una nota importante en el futuro es que para cada borde agregado a algún árbol de salida T 'en cada iteración, eliminamos los bordes del gráfico G original para que no se incluyan en algún bosque de expansión para la próxima iteración. Sin embargo, podemos ver las marcas en los vértices como reiniciadas, por lo que no se marcan vértices en la siguiente iteración.
Una vez que hemos agotado todos los vértices, tenemos un conjunto de aristas para la primera iteración, E 1 . Luego quitamos E 1 de G = G 0 , y hacemos que G 1 , y pasamos a la segunda iteración usando el gráfico G 1 . Al final de cada iteración tenemos:
- E i : el conjunto de bordes que encontramos durante nuestra búsqueda de escaneo primero
- F i : bosque de búsqueda de exploración primero, la agrupación de bordes en lo que pueden ser árboles separados en cada paso.
- G i : El gráfico resultante de eliminar E i del gráfico G i-1 que usamos para comenzar esta iteración.
- H i : La unión de los bordes desde cada iteración hasta ahora, E 1 ∪ E 2 ∪ ... ∪ E i .
Decimos que H k es el certificado escaso para el gráfico G.
El teorema principal del certificado
Dado un gráfico no dirigido G = ( V , E ) con n vértices, sea k un número entero positivo. Para todo i = 1, 2,. . . , k , sea E i el conjunto de aristas generadas por la i -ésima iteración de la búsqueda de exploración primero, correspondiente a un gráfico G i −1 = ( V , E - ( E 1 ∪... ∪ E i −1 )). Entonces, para cada iteración de búsqueda de exploración primero, como se indicó anteriormente, eliminaremos los bordes del gráfico G para crear un nuevo gráfico G i que resulte al final de la i- ésima iteración. Para cada iteración i , nuestro bosque de búsqueda de exploración primero se construye a partir del gráfico G i −1 , donde G = G 0 . La afirmación del Teorema del certificado principal es que la unión E 1 ∪. . . ∪ E k es un certificado para la conectividad k- vértice de G y que tiene como máximo k ( n - 1) aristas. [2]
Complejidad computacional
El tiempo de ejecución más importante es el del algoritmo que se ejecuta en paralelo, utilizando en este caso el modelo CRCW PRAM. Nuestro primer árbol de expansión T se puede encontrar en el tiempo O (log n ) usando procesadores C ( n , m ). Nuestros números de preorden y vecinos también se pueden calcular en tiempo O (log n) porque las técnicas paralelas [3] con procesadores O (( n + m ) / log n ) , nuestro valor C ( n , m ). Por esta razón, podemos generar un único T & primo correspondiente a una iteración en el tiempo O (log n ).
Utilizando un enfoque de búsqueda distribuida de amplitud primero, podemos encontrar nuestro bosque de expansión en tiempo O ( d log 3 n ) en un gráfico con diámetro d usando mensajes O ( m + n log 3 n ) . El enfoque secuencial es simplemente el tiempo de ejecución para la búsqueda en amplitud, O ( m + n ) .
Ver también
Referencias
- ↑ Incluso, S. (1 de septiembre de 1975). "Un algoritmo para determinar si la conectividad de un gráfico es al menos k" (PDF) . Revista SIAM de Computación . 4 (3): 393–396. doi : 10.1137 / 0204034 . hdl : 1813/6027 . ISSN 0097-5397 .
- ^ a b c Cheriyan, J .; Kao, M .; Thurimella, R. (1 de febrero de 1993). "Búsqueda de escaneo primero y certificados dispersos: un algoritmo paralelo mejorado para la conectividad k-Vertex" (PDF) . Revista SIAM de Computación . 22 (1): 157-174. doi : 10.1137 / 0222013 . hdl : 1813/8878 . ISSN 0097-5397 .
- ^ Karp, Richard M .; Ramachandran, Vijaya (1 de enero de 1990). van Leeuwen, Jan (ed.). Manual de Informática Teórica (Vol. A) . Cambridge, MA, EE.UU .: MIT Press. págs. 869–941. ISBN 978-0-444-88071-0.