En informática , la búsqueda lexicográfica de 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 de búsqueda lexicográfica en amplitud se basa en la idea de refinamiento de 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 subrutina en otros algoritmos de gráficos, incluido el reconocimiento de gráficos cordales y la coloración óptima de gráficos hereditarios de distancia .
El algoritmo de búsqueda en amplitud se define comúnmente mediante el siguiente proceso:
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 eliminación de cola de una cola, se puede definir la misma secuencia de vértices de forma declarativa mediante las propiedades de estos vértices. Es decir, una búsqueda estándar en amplitud es solo el resultado de aplicar repetidamente esta regla:
En algunos casos, este orden de los vértices según 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 que se eligen esos dos vértices puede ser arbitrario. El resultado de la búsqueda lexicográfica en amplitud se diferencia de una búsqueda en amplitud estándar en que tiene una regla consistente para romper dichos vínculos. En la búsqueda lexicográfica de amplitud primero, el orden de salida es el orden que produciría la regla:
Entonces, cuando dos vértices v y w tienen el mismo predecesor más antiguo, antes que cualquier otro vértice no elegido, el algoritmo de búsqueda en amplitud estándar los ordenará 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 sólo uno de ellos tiene un segundo predecesor más antiguo que ya se ha generado, se elige ese. Si tanto v como w tienen el mismo segundo antecesor, entonces el empate se rompe considerando su tercer antecesor, y así sucesivamente.
Aplicar esta regla directamente comparando vértices según esta regla conduciría a un algoritmo ineficiente. En cambio, la búsqueda lexicográfica en amplitud utiliza una estructura de datos de partición establecida para producir el mismo orden de manera más eficiente, del mismo modo que una búsqueda en amplitud estándar utiliza una estructura de datos en cola para producir su orden de manera eficiente.
El algoritmo de búsqueda lexicográfica en amplitud reemplaza la cola de vértices de una búsqueda en amplitud estándar 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:
Cada vértice se procesa una vez, cada borde se examina solo cuando se procesan sus dos puntos finales y (con una representación apropiada para los conjuntos en Σ que permite mover elementos de un conjunto a otro en tiempo constante) cada iteración del bucle interno sólo requiere 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 requiere tiempo lineal.
El algoritmo se llama búsqueda lexicográfica en amplitud porque el orden que produce es un orden que también podría haber sido producido mediante una búsqueda en amplitud, 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 ordena las filas y columnas en orden lexicográfico .
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 adelante en el orden forman una camarilla. En un gráfico cordal, el orden inverso al lexicográfico es siempre un orden de eliminación perfecto. Por lo tanto, se puede probar si un gráfico es cordal en tiempo lineal mediante el siguiente algoritmo:
Esta aplicación fue la motivación original que llevó a Rose, Tarjan y Lueker (1976) a desarrollar el algoritmo de búsqueda de amplitud lexicográfica. [1]
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 , se garantiza que un algoritmo de coloración codicioso que coloree los vértices en el orden de secuencia inducida producirá una coloración óptima.
Para un gráfico cordal, un orden de eliminación perfecto es un orden perfecto: el número de color utilizado 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 utilizados es igual al tamaño de la camarilla más grande en el gráfico, y ningún colorante puede usar menos colores. Un subgrafo inducido de un gráfico cordal es cordal y la subsecuencia inducida de su orden de eliminación perfecta es un orden de eliminación perfecto en el subgrafo, por lo que los gráficos cordales son perfectamente ordenables y se puede utilizar la búsqueda lexicográfica en amplitud para colorearlos de manera óptima.
La misma propiedad es cierta para una clase más amplia de gráficos, los gráficos hereditarios a distancia : los gráficos hereditarios a distancia son perfectamente ordenables, con un orden perfecto dado por el reverso de un orden lexicográfico, por lo que la búsqueda lexicográfica en amplitud se puede utilizar en conjunto con algoritmos de coloración codiciosos para colorearlos de manera óptima en tiempo lineal. [2]
Bretscher et al. (2008) describen una extensión de la búsqueda lexicográfica en amplitud que rompe cualquier vínculo adicional utilizando el gráfico complementario del gráfico de entrada. Como muestran, esto se puede utilizar para reconocer cografos en tiempo lineal. Habib y cols. (2000) describen aplicaciones adicionales de la búsqueda lexicográfica en amplitud, incluido el reconocimiento de gráficos de comparabilidad y gráficos de intervalo .
Se dice que una enumeración de los vértices de un gráfico es un ordenamiento LexBFS si es el posible resultado de la aplicación de LexBFS a este gráfico.
Sea un gráfico con vértices. Recuerde que es el conjunto de vecinos de . Sea una enumeración de los vértices de . La enumeración es un orden LexBFS (con fuente ) si, para todos con , existe tal que .
