Búsqueda lexicográfica en amplitud

En informática , la búsqueda lexicográfica en amplitud o Lex-BFS es un algoritmo de tiempo lineal para ordenar los vértices de un grafo . El algoritmo es diferente de una búsqueda en amplitud , pero produce un ordenamiento que es consistente con la búsqueda en amplitud.

El algoritmo de búsqueda lexicográfica 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 subrutina en otros algoritmos de grafos, incluido el reconocimiento de grafos cordales y la coloración óptima de grafos hereditarios de distancia .

El algoritmo de búsqueda en amplitud se define comúnmente mediante el siguiente proceso:

• Inicializar una cola de vértices de gráficos, con el vértice inicial del gráfico como el único elemento de la cola.
• Mientras la cola no esté vacía, elimine (saca de la cola) un vértice v de la cola y agregue a la cola (ponga en cola) todos los demás vértices a los que se puede llegar mediante un borde desde v que no se hayan agregado en pasos anteriores.

Sin embargo, en lugar de definir el vértice que se debe elegir en cada paso de forma imperativa , como se hace con la operación de desencolado 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 simplemente el resultado de aplicar repetidamente esta regla:

• Generar repetidamente un vértice v , eligiendo en cada paso un vértice v que no haya sido elegido ya y que tenga un predecesor (un vértice que tenga una arista en v ) lo más temprano posible en la salida.

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 el que se eligen esos dos vértices puede ser arbitrario. El resultado de una búsqueda lexicográfica en amplitud difiere de una búsqueda en amplitud estándar en que tiene una regla consistente para romper esos vínculos. En una búsqueda lexicográfica en amplitud, el orden de salida es el que se produciría según la regla:

• Generar repetidamente un vértice v , eligiendo en cada paso un vértice v que no haya sido elegido anteriormente 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 predecesor más antiguo, anterior a cualquier otro vértice no elegido, el algoritmo estándar de búsqueda en amplitud los ordenará de forma arbitraria. 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 generado, se elige ese. Si tanto v como w tienen el mismo segundo predecesor más antiguo, entonces el empate se deshace considerando sus terceros predecesores más antiguos, y así sucesivamente.

La aplicación directa de esta regla mediante la comparación de vértices según esta regla daría lugar a un algoritmo ineficiente. En cambio, la búsqueda lexicográfica en amplitud utiliza una estructura de datos de partición de conjuntos para producir el mismo ordenamiento de manera más eficiente, de la misma manera que una búsqueda en amplitud estándar utiliza una estructura de datos de cola para producir su ordenamiento de manera eficiente.

El algoritmo de búsqueda en amplitud lexicográfica 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, se elimina un vértice v del primer conjunto de la secuencia de ese conjunto y, si esa eliminación hace que el conjunto quede vacío, se elimina el conjunto 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:

• Inicializar 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 Σ
  • Añade 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 ha sido 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, sea T el conjunto anterior a S.
    • Mueva w de S a T y, si esto hace que S quede vacío, elimine S de Σ.

Cada vértice se procesa una vez, cada arista 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 toma solo tiempo constante. Por lo tanto, al igual que los algoritmos de búsqueda de grafos más simples, como la búsqueda en amplitud y la búsqueda en profundidad , este algoritmo toma tiempo lineal.

El algoritmo se llama búsqueda en amplitud lexicográfica porque el orden que produce es un orden que también podría haber sido producido por una búsqueda en amplitud, y porque si el orden se utiliza para indexar las filas y columnas de una matriz de adyacencia de un gráfico, entonces 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 grafo cordal, el reverso de un orden lexicográfico es siempre un orden de eliminación perfecto. Por lo tanto, se puede comprobar si un grafo es cordal en tiempo lineal mediante el siguiente algoritmo:

• Utilice la búsqueda en amplitud lexicográfica para encontrar un orden lexicográfico de G
• Para cada vértice v :
  • Sea w el vecino de v que ocurre antes de v , lo más cerca posible de v en la secuencia.
    • (Continuar al siguiente vértice v si no existe tal w )
  • Si el conjunto de vecinos anteriores de v (excluyendo w mismo) no es un subconjunto del conjunto de vecinos anteriores de w , el gráfico no es cordal.
• 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 y Lueker (1976) a desarrollar el algoritmo de búsqueda de amplitud lexicográfica. ^[1]

Se dice que un grafo G es perfectamente ordenable si existe 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 voraz que coloree los vértices en el orden de secuencia inducido producirá una coloración óptima.

Para un grafo cordal, un ordenamiento de eliminación perfecto es un ordenamiento perfecto: la cantidad de color utilizado para cualquier vértice es el tamaño de la camarilla formada por él y sus vecinos anteriores, por lo que la cantidad máxima de colores utilizados es igual al tamaño de la camarilla más grande en el grafo, y ninguna coloración puede utilizar menos colores. Un subgrafo inducido de un grafo cordal es cordal y la subsecuencia inducida de su ordenamiento de eliminación perfecto es un ordenamiento de eliminación perfecto en el subgrafo, por lo que los grafos cordales son perfectamente ordenables y se puede utilizar la búsqueda lexicográfica en amplitud para colorearlos de manera óptima.

La misma propiedad es válida para una clase más grande de gráficos, los gráficos hereditarios de distancia : los gráficos hereditarios de distancia son perfectamente ordenables, con un orden perfecto dado por el reverso de un orden lexicográfico, por lo que la búsqueda en amplitud lexicográfica se puede utilizar junto con algoritmos de coloración voraz 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 et al. (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 la salida posible de la aplicación de LexBFS a este gráfico.

Sea un grafo con vértices. Recordemos que es el conjunto de vecinos de . Sea una enumeración de los vértices de . La enumeración es un ordenamiento LexBFS (con origen ) si, para todos con , existe tal que .${\displaystyle G=(V,E)}$${\estilo de visualización n}$${\estilo de visualización N(v)}$${\estilo de visualización v}$${\displaystyle \sigma =(v_{1},\dots,v_{n})}$${\estilo de visualización V}$${\estilo de visualización \sigma}$$estilo de visualización v_{1}$${\displaystyle 1\leq i<j<k\leq n}$${\ Displaystyle v_ {i} \ en N (v_ {k}) \ setminus N (v_ {j})}$${\displaystyle m<i}$${\ Displaystyle v_ {m} \ en N (v_ {j}) \ setminus N (v_ {k})}$

• Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999), Clases de grafos: un estudio , Monografías SIAM sobre matemáticas discretas y aplicaciones, ISBN 0-89871-432-X.
• Bretscher, Anna; Corneil, Derek ; Habib, Michel; Paul, Christophe (2008), "Un algoritmo de reconocimiento de cografos 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), "Búsqueda en amplitud lexicográfica: una encuesta", Graph-Theoretic Methods in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Alemania, 21-23 de junio de 2004, Documentos revisados , Lecture Notes in Computer Science, vol. 3353, Springer-Verlag, págs. 1–19, doi :10.1007/978-3-540-30559-0_1, ISBN 978-3-540-24132-4.
• 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 intervalos y pruebas de consecutivos", Theoretical Computer Science , 234 (1–2): 59–84, doi : 10.1016/S0304-3975(97)00241-7.
• 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.