Algoritmo recursivo del mayor primero

Algoritmo para colorear gráficos

El algoritmo recursivo Largest First ( RLF ) es una heurística para el problema de coloración de grafos NP-hard . Fue propuesto originalmente por Frank Leighton en 1979. ^[1]

El algoritmo RLF asigna colores a los vértices de un gráfico construyendo cada clase de color de a una por vez. Para ello, identifica un conjunto máximo independiente de vértices en el gráfico, les asigna el mismo color y luego elimina estos vértices del gráfico. Estas acciones se repiten en el subgráfico restante hasta que no queden vértices.

Para formar soluciones de alta calidad (soluciones que utilizan pocos colores), el algoritmo RLF utiliza reglas heurísticas especializadas para intentar identificar conjuntos independientes de "buena calidad". Estas heurísticas hacen que el algoritmo RLF sea exacto para gráficos bipartitos , cíclicos y de rueda . ^[2] En general, sin embargo, el algoritmo es aproximado y puede devolver soluciones que utilicen más colores que el número cromático del gráfico .

Descripción

El algoritmo se puede describir mediante los tres pasos siguientes. Al final de este proceso, se obtiene una partición de los vértices que representa una coloración factible del grafo . ${\displaystyle {\mathcal {S}}}$ ${\displaystyle |{\mathcal {S}}|}$ ${\displaystyle G}$

1. Sea una solución vacía. Además, sea el grafo que deseamos colorear, que comprende un conjunto de vértices y un conjunto de aristas . ${\displaystyle {\mathcal {S}}=\emptyset }$ ${\displaystyle G=(V,E)}$ ${\displaystyle V}$ ${\displaystyle E}$
2. Identificar un conjunto independiente máximo . Para ello: ${\displaystyle S\subseteq V}$
   1. El primer vértice agregado debe ser el vértice que tenga el mayor número de vecinos. ${\displaystyle S}$ ${\displaystyle G}$
   2. Los vértices subsiguientes que se agreguen a deben elegirse como aquellos que (a) no estén actualmente adyacentes a ningún vértice en , y (b) tengan un número máximo de vecinos que estén adyacentes a los vértices en . Los empates en la condición (b) se pueden romper seleccionando el vértice con el número mínimo de vecinos que no estén en . Los vértices se agregan a de esta manera hasta que sea imposible agregar más vértices. ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$
3. Ahora, configure y elimine los vértices de . Si aún contiene vértices, vuelva al paso 2; de lo contrario, finalice. ${\displaystyle {\mathcal {S}}={\mathcal {S}}\cup \{S\}}$ ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle G}$

Ejemplo

Un gráfico de rueda con siete vértices.

Considere el gráfico que se muestra a la derecha. Se trata de un gráfico de rueda y, por lo tanto, RLF lo coloreará de manera óptima. Al ejecutar el algoritmo, los vértices se seleccionan y colorean en el siguiente orden: ${\displaystyle G=(V,E)}$

1. Vértice (color 1) ${\displaystyle g}$
2. Vértice , , y luego (color 2) ${\displaystyle a}$ ${\displaystyle c}$ ${\displaystyle e}$
3. Vértice , , y luego (color 3) ${\displaystyle b}$ ${\displaystyle d}$ ${\displaystyle f}$

Esto da la solución final de tres colores . ${\displaystyle {\mathcal {S}}=\{\{g\},\{a,c,e\},\{b,d,f\}\}}$

Actuación

Sea el número de vértices en el grafo y sea el número de aristas. Utilizando la notación O mayúscula , en su publicación original Leighton afirma que la complejidad de RLF es ; sin embargo, esto se puede mejorar. Gran parte del gasto de este algoritmo se debe al Paso 2, donde la selección de vértices se realiza de acuerdo con las reglas heurísticas establecidas anteriormente. De hecho, cada vez que se selecciona un vértice para agregarlo al conjunto independiente , se debe recalcular la información sobre los vecinos para cada vértice no coloreado. Estos cálculos se pueden realizar a tiempo, lo que significa que la complejidad general de RLF es . ^[2] ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle {\mathcal {O}}(n^{3})}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {O}}(m)}$ ${\displaystyle {\mathcal {O}}(mn)}$

Si las heurísticas del paso 2 se reemplazan con selección aleatoria, entonces la complejidad de este algoritmo se reduce a ; sin embargo, el algoritmo resultante generalmente devolverá soluciones de menor calidad en comparación con las de RLF. ^[2] Ahora también será inexacto para gráficos bipartitos , de ciclo y de rueda . ${\displaystyle {\mathcal {O}}(n+m)}$

En una comparación empírica realizada por Lewis en 2021, se demostró que RLF produce coloraciones de vértices significativamente mejores que las heurísticas alternativas, como el algoritmo greedy y el algoritmo DSatur en gráficos aleatorios . Sin embargo, también se observó que los tiempos de ejecución con RLF eran más altos que estas alternativas debido a su mayor complejidad general. ^[2] ${\displaystyle {\mathcal {O}}(n+m)}$ ${\displaystyle {\mathcal {O}}((n+m)\lg n)}$

Referencias

1. Leighton, F. (1979). "Un algoritmo de coloración de grafos para grandes problemas de planificación". Revista de investigación de la Oficina Nacional de Normas . 84 (6): 489–503. doi :10.6028/jres.084.024. PMC  6756213 . PMID  34880531.
2. Lewis, R. (2021). Una guía para colorear gráficos: algoritmos y aplicaciones . Textos en informática. Springer. doi :10.1007/978-3-030-81054-2. ISBN 978-3-030-81053-5.S2CID57188465  .​

Enlaces externos

• Algoritmos de coloración de gráficos de alto rendimiento Conjunto de algoritmos de coloración de gráficos (implementados en C++) utilizados en el libro A Guide to Graph Colouring: Algorithms and Applications (Springer International Publishers, 2021).