En informática , la búsqueda lexicográfica en amplitud primero o Lex-BFS es un algoritmo de tiempo lineal para ordenar los vértices de un gráfico . El algoritmo es diferente de una búsqueda en amplitud , pero produce un orden que es consistente con la búsqueda en amplitud.
El algoritmo lexicográfico de búsqueda primero en amplitud se basa en la idea del refinamiento de la partición y fue desarrollado por primera vez por Donald J. Rose, Robert E. Tarjan y George S. Lueker ( 1976 ). Corneil (2004) presenta un estudio más detallado del tema . Se ha utilizado como una subrutina en otros algoritmos de grafos, incluido el reconocimiento de grafos cordales y la coloración óptima de grafos hereditarios de distancia .
Fondo
El algoritmo de búsqueda primero en amplitud se define comúnmente mediante el siguiente proceso:
- Inicialice una cola de vértices de gráfico, con el vértice inicial del gráfico como único elemento de la cola.
- Si bien la cola no está vacía, elimine (retire de la cola) un vértice v de la cola y agregue a la cola (poner en cola) todos los demás vértices a los que puede llegar un borde de v que aún no se hayan agregado en pasos anteriores.
Sin embargo, en lugar de definir el vértice a elegir en cada paso de forma imperativa como el producido por la operación de queue de una cola, se puede definir la misma secuencia de vértices declarativamente por las propiedades de estos vértices. Es decir, una búsqueda estándar en amplitud es solo el resultado de aplicar repetidamente esta regla:
- Genere repetidamente un vértice v , eligiendo en cada paso un vértice v que aún no se haya elegido y que tenga un predecesor (un vértice que tenga una arista av ) lo antes posible en la salida.
En algunos casos, este orden de vértices por las posiciones de salida de sus predecesores puede tener vínculos: dos vértices diferentes tienen el mismo predecesor más antiguo. En este caso, el orden en el que se eligen esos dos vértices puede ser arbitrario. El resultado de la búsqueda lexicográfica primero en amplitud difiere de una búsqueda estándar en amplitud en que tiene una regla coherente para romper tales vínculos. En la búsqueda lexicográfica de amplitud primero, el orden de salida es el orden que produciría la regla:
- Genere repetidamente un vértice v , eligiendo en cada paso un vértice v que aún no se haya elegido y cuyo conjunto completo de predecesores ya generados sea lo más pequeño posible en orden lexicográfico .
Por lo tanto, cuando dos vértices v y w tienen el mismo precursor temprano, antes que cualquier otro vértices no elegidas, el algoritmo de búsqueda en anchura estándar ordenarán arbitrariamente. En cambio, en este caso, el algoritmo LexBFS elegiría entre v y w según el orden de salida de sus segundos predecesores más antiguos. Si solo uno de ellos tiene un segundo predecesor más antiguo que ya se ha emitido, se elige ese. Si tanto v como w tienen el mismo segundo predecesor más antiguo, entonces el empate se rompe al considerar sus terceros predecesores más antiguos, y así sucesivamente.
Aplicar esta regla directamente comparando vértices de acuerdo con esta regla conduciría a un algoritmo ineficiente. En cambio, la búsqueda lexicográfica primero en amplitud usa una estructura de datos de partición establecida para producir el mismo orden de manera más eficiente, al igual que una búsqueda estándar en amplitud primero usa una estructura de datos de cola para producir su pedido de manera eficiente.
Algoritmo
El algoritmo lexicográfico de búsqueda primero en amplitud reemplaza la cola de vértices de una búsqueda estándar en amplitud con una secuencia ordenada de conjuntos de vértices. Los conjuntos de la secuencia forman una partición de los vértices restantes. En cada paso, un vértice v del primer conjunto de la secuencia se elimina de ese conjunto, y si esa eliminación hace que el conjunto quede vacío, entonces el conjunto se elimina de la secuencia. Luego, cada conjunto de la secuencia se reemplaza por dos subconjuntos: los vecinos de v y los no vecinos de v . El subconjunto de vecinos se coloca antes en la secuencia que el subconjunto de no vecinos. En pseudocódigo , el algoritmo se puede expresar de la siguiente manera:
- Inicialice una secuencia Σ de conjuntos, para contener un único conjunto que contenga todos los vértices.
- Inicialice la secuencia de salida de vértices para que esté vacía.
- Mientras Σ no está vacío:
- Encuentra y elimina un vértice v del primer conjunto en Σ
- Si el primer conjunto en Σ ahora está vacío, elimínelo de Σ
- Agregue v al final de la secuencia de salida.
- Para cada arista vw tal que w todavía pertenece a un conjunto S en Σ:
- Si el conjunto S que contiene w aún no se ha reemplazado durante el procesamiento de v , cree un nuevo conjunto de reemplazo vacío T y colóquelo antes de S en la secuencia; de lo contrario, deja T el conjunto antes de la S .
- Mueva w de S a T , y si esto hace que S se vacíe, quite S de Σ.
Cada vértice se procesa una vez, cada borde se examina solo cuando se procesan sus dos puntos finales y (con una representación adecuada para los conjuntos en Σ que permite que los elementos se muevan de un conjunto a otro en tiempo constante) cada iteración del bucle interno toma solo un tiempo constante. Por lo tanto, al igual que los algoritmos de búsqueda de gráficos más simples, como la búsqueda en amplitud y la búsqueda en profundidad , este algoritmo toma un tiempo lineal.
El algoritmo se denomina búsqueda lexicográfica primero en amplitud porque el orden que produce es un orden que también podría haber sido producido por una búsqueda en amplitud primero, y porque si el orden se usa para indexar las filas y columnas de una matriz de adyacencia de un gráfico luego, el algoritmo clasifica las filas y columnas en orden lexicográfico .
Aplicaciones
Gráficos de cuerdas
Un grafo G se define como cordal si sus vértices tienen un orden de eliminación perfecto , un orden tal que para cualquier vértice v los vecinos que aparecen más tarde en el orden forman una camarilla. En un gráfico de cuerdas, el reverso de una ordenación lexicográfica es siempre una ordenación de eliminación perfecta. Por lo tanto, se puede probar si una gráfica es cordal en tiempo lineal mediante el siguiente algoritmo:
- Utilice la búsqueda lexicográfica de amplitud primero para encontrar un orden lexicográfico de G
- Para cada vértice v :
- Sea w el vecino de v antes de v , lo más cerca posible de v en la secuencia
- (Continúe con el siguiente vértice v si no existe tal w )
- Si el conjunto de vecinos anteriores de v (excluyendo w en sí mismo) no es un subconjunto del conjunto de vecinos anteriores de w , la gráfica no es cordal
- Sea w el vecino de v antes de v , lo más cerca posible de v en la secuencia
- Si el bucle termina sin mostrar que el gráfico no es cordal, entonces es cordal.
Esta aplicación fue la motivación original que llevó a Rose, Tarjan & Lueker (1976) a desarrollar el algoritmo de primera búsqueda de amplitud lexicográfica. [1]
Coloración gráfica
Se dice que un gráfico G es perfectamente ordenable si hay una secuencia de sus vértices con la propiedad de que, para cualquier subgrafo inducido de G , un algoritmo de coloración codicioso que colorea los vértices en el orden de la secuencia inducida está garantizado para producir una coloración óptima.
Para un grafo cordal, una ordenación de eliminación perfecta es una ordenación perfecta: el número del color usado para cualquier vértice es el tamaño de la camarilla formada por él y sus vecinos anteriores, por lo que el número máximo de colores usados es igual al tamaño de la camarilla más grande en el gráfico, y ninguna coloración puede usar menos colores. Un subgrafo inducido de un grafo de cordales es cordal y la subsecuencia inducida de su ordenamiento de eliminacion perfecto es un ordenamiento de eliminacion perfecto en el subgrafo, por lo que los grafos de cordales se pueden ordenar perfectamente, y la busqueda lexicografica primero en amplitud se puede utilizar para colorearlos de manera optima.
La misma propiedad es cierta para una clase más grande de gráficos, los gráficos de distancia-hereditarios : los gráficos de distancia-hereditarios se pueden ordenar perfectamente, con un orden perfecto dado por el reverso de un orden lexicográfico, por lo que la búsqueda lexicográfica primero en amplitud se puede usar en conjunto con codiciosos algoritmos de coloración para colorearlos de manera óptima en tiempo lineal. [2]
Otras aplicaciones
Bretscher y col. (2008) describen una extensión de la búsqueda lexicográfica de amplitud primero que rompe cualquier vínculo adicional utilizando el gráfico de complemento del gráfico de entrada. Como muestran, esto se puede utilizar para reconocer cografías en tiempo lineal. Habib y col. (2000) describen aplicaciones adicionales de la búsqueda lexicográfica de amplitud primero, incluido el reconocimiento de gráficos de comparabilidad y gráficos de intervalo .
Pedido de LexBFS
Se dice que una enumeración de los vértices de un gráfico es un orden de LexBFS si es el resultado posible de la aplicación de LexBFS a este gráfico.
Dejar ser un gráfico con vértices. Recordar que es el conjunto de vecinos de . Dejar ser una enumeración de los vértices de . La enumeración es un pedido de LexBFS (con fuente ) si, para todos con , existe tal que .
Notas
- ^ Corneil (2004) .
- ^ Brandstädt, Le y Spinrad (1999) , Teorema 5.2.4, p. 71.
Referencias
- Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey , SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
- Bretscher, Anna; Corneil, Derek ; Habib, Michel; Paul, Christophe (2008), "Un algoritmo de reconocimiento cográfico LexBFS de tiempo lineal simple" , SIAM Journal on Discrete Mathematics , 22 (4): 1277–1296, CiteSeerX 10.1.1.188.5016 , doi : 10.1137 / 060664690.
- Corneil, Derek G. (2004), "Primera búsqueda de amplitud lexicográfica: una encuesta", Métodos teóricos de gráficos en ciencias de la computación: 30º taller internacional, GT 2004, Bad Honnef, Alemania, 21 al 23 de junio de 2004, artículos revisados , conferencia Notes in Computer Science, 3353 , Springer-Verlag, págs. 1-19, doi : 10.1007 / 978-3-540-30559-0_1 CS1 maint: parámetro desalentado ( enlace ).
- Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent (2000), "Lex-BFS y refinamiento de particiones, con aplicaciones a la orientación transitiva, reconocimiento de gráficos de intervalo y pruebas consecutivas" (PDF) , Theoretical Computer Science , 234 (1–2): 59–84, doi : 10.1016 / S0304-3975 (97) 00241-7 , archivado desde el original (PDF) en 2011-07-26 CS1 maint: parámetro desalentado ( enlace ).
- Rose, DJ; Tarjan, RE ; Lueker, GS (1976), "Aspectos algorítmicos de la eliminación de vértices en gráficos", SIAM Journal on Computing , 5 (2): 266-283, doi : 10.1137 / 0205021.