Clase | Coloración de gráficos |
---|---|
Complejidad espacial en el peor de los casos | O ( n 2 ) |
DSatur es un algoritmo de coloración de grafos propuesto por Daniel Brélaz en 1979. [1] De manera similar al algoritmo de coloración voraz , DSatur colorea los vértices de un grafo uno tras otro, agregando un color no utilizado previamente cuando es necesario. Una vez que se ha coloreado un nuevo vértice , el algoritmo determina cuál de los vértices sin color restantes tiene el mayor número de colores en su vecindad y colorea este vértice a continuación. Brélaz define este número como el grado de saturación de un vértice dado. [1] La contracción del término "grado de saturación" forma el nombre del algoritmo. [2] DSatur es un algoritmo de coloración de grafos heurístico, pero produce resultados exactos para grafos bipartitos, [1] de ciclo y de rueda. [2] DSatur también se ha denominado LF de saturación en la literatura. [3]
Sea el "grado de saturación" de un vértice la cantidad de colores diferentes que utilizan sus vecinos. Dado un grafo simple no dirigido que comprende un conjunto de vértices y un conjunto de aristas , el algoritmo asigna colores a todos los vértices utilizando etiquetas de color . El algoritmo funciona de la siguiente manera: [4]
El paso 2 de este algoritmo asigna colores a los vértices utilizando el mismo esquema que el algoritmo de coloración voraz . Las principales diferencias entre los dos enfoques surgen en el paso 1 mencionado anteriormente, donde los vértices que se consideran más "restringidos" se colorean primero.
Considere el gráfico que se muestra a la derecha. Se trata de un gráfico de rueda y, por lo tanto, el algoritmo DSatur le dará un color óptimo. Al ejecutar el algoritmo, los vértices se seleccionan y se colorean de la siguiente manera. (En este ejemplo, cuando se producen empates en ambas heurísticas de DSatur, se elige el vértice con el etiquetado lexicográfico más bajo entre ellos).
Esto da la solución final de tres colores .
La complejidad del peor caso de DSatur es , donde es el número de vértices en el gráfico. Esto se debe a que el proceso de selección del siguiente vértice para colorear lleva tiempo, y este proceso se lleva a cabo veces. El algoritmo también se puede implementar utilizando un montón binario para almacenar los grados de saturación, operando en , o utilizando el montón de Fibonacci, donde es el número de aristas en el gráfico. [2] Esto produce ejecuciones mucho más rápidas con gráficos dispersos.
Se sabe que DSatur es exacto para gráficos bipartitos, [1] así como para gráficos de ciclo y de rueda. [2] En una comparación empírica de Lewis en 2021, DSatur produjo coloraciones de vértices significativamente mejores que el algoritmo codicioso en gráficos aleatorios con probabilidad de borde , mientras que a su vez produjo coloraciones significativamente peores que el algoritmo recursivo del primero más grande . [2]