DSatur

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] ${\estilo de visualización G}$${\estilo de visualización V}$${\estilo de visualización E}$${\estilo de visualización 1,2,3,...}$

1. Sea el vértice sin colorear con el mayor grado de saturación. En caso de empate, elija entre estos el vértice con el mayor grado en el subgrafo inducido por los vértices sin colorear.${\estilo de visualización v}$${\estilo de visualización G}$
2. Asignar a la etiqueta de color más baja que no esté siendo utilizada por ninguno de sus vecinos.${\estilo de visualización v}$
3. Si se han coloreado todos los vértices, finalice; de ​​lo contrario, regrese al Paso 1.

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).${\displaystyle G=(V,E)}$

1. Vértice (color 1)${\estilo de visualización g}$
2. Vértice (color 2)${\estilo de visualización a}$
3. Vértice (color 3)${\estilo de visualización b}$
4. Vértice (color 2)${\estilo de visualización c}$
5. Vértice (color 3)${\estilo de visualización d}$
6. Vértice (color 2)${\estilo de visualización e}$
7. Vértice (color 3)${\estilo de visualización f}$

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

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. ${\displaystyle O(n^{2})}$${\estilo de visualización n}$${\displaystyle O(n)}$${\estilo de visualización n}$${\displaystyle O((n+m)\log n)}$${\displaystyle O(m+n\log n)}$${\estilo de visualización m}$

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]${\displaystyle p=0,5}$

• 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).
• Implementación en C++ del algoritmo DSatur, presentada como parte del artículo El algoritmo DSatur para coloración de gráficos, Geeks for Geeks (2021)