DSatur

Algoritmo de coloración de gráficos de Daniel Brélaz

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 la mayor cantidad 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]

Pseudocódigo

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] ${\displaystyle G}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle 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. ${\displaystyle v}$ ${\displaystyle G}$
2. Asignar a la etiqueta de color más baja que no esté siendo utilizada por ninguno de sus vecinos. ${\displaystyle 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.

Ejemplo

Gráfica de rueda con siete vértices y doce aristas

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á colores de manera óptima. 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) ${\displaystyle g}$
2. Vértice (color 2) ${\displaystyle a}$
3. Vértice (color 3) ${\displaystyle b}$
4. Vértice (color 2) ${\displaystyle c}$
5. Vértice (color 3) ${\displaystyle d}$
6. Vértice (color 2) ${\displaystyle e}$
7. Vértice (color 3) ${\displaystyle f}$

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

Actuación

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})}$ ${\displaystyle n}$ ${\displaystyle O(n)}$ ${\displaystyle n}$ ${\displaystyle O((n+m)\log n)}$ ${\displaystyle O(m+n\log n)}$ ${\displaystyle 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}$

Referencias

1. Brélaz, Daniel (1979-04-01). "Nuevos métodos para colorear los vértices de un grafo". Comunicaciones de la ACM . 22 (4): 251–256. doi : 10.1145/359094.359101 . ISSN  0001-0782. S2CID  14838769.
2. Lewis, RMR (2021). Una guía para la coloración de gráficos: algoritmos y aplicaciones . Textos en informática (2.ª edición). Berlín: Springer. doi :10.1007/978-3-030-81054-2. ISBN 978-3-030-81053-5. Número de identificación del sujeto  57188465.
3. Kubale, ed. (2004). Coloración de gráficos (Vol. 352) . Providence: American Mathematical Society. pág. 13. ISBN 978-0-8218-3458-9.
4. Lewis, Rhyd (19 de enero de 2019). "Algoritmos constructivos para la coloración de gráficos". youtube.com . El evento ocurre en el minuto 3:49.

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).
• 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)