La coloración de gráficos es la tarea de asignar colores a los vértices de un gráfico para que:
- a los pares de vértices adyacentes se les asignan colores diferentes, y
- el número de colores diferentes utilizados en el gráfico es mínimo.
El siguiente gráfico ha sido coloreado usando solo tres colores (rojo, azul y verde aquí). Este es en realidad el número mínimo de colores necesarios para este gráfico en particular; es decir, no podemos colorear este gráfico usando menos de tres colores mientras nos aseguramos de que los vértices adyacentes tengan un color diferente.
Tricoloración adecuada de un gráfico
El número mínimo de colores necesarios para colorear un gráfico G se conoce como el número cromático y generalmente se denota por χ(G) . Determinar el número cromático de un gráfico es NP-difícil . El problema de decisión correspondiente de decidir si existe una coloración k para un gráfico G también es NP-completo .
Publicaciones similares en este sitio web ya han descrito el algoritmo codicioso para colorear gráficos. Este algoritmo es simple de aplicar, pero la cantidad de colores utilizados en sus soluciones depende mucho del orden en que se consideren los vértices. En el mejor de los casos, el ordenamiento correcto producirá una solución usando colores χ(G) ; sin embargo, los pedidos incorrectos pueden resultar en soluciones que utilizan muchos colores adicionales.
El algoritmo DSatur (abreviado de “ grado de saturación ”) tiene un comportamiento similar al algoritmo Greedy . La diferencia radica en la forma en que genera el ordenamiento de los vértices. En concreto, siempre se elige el siguiente vértice a colorear como el vértice no coloreado con mayor grado de saturación . El grado de saturación de un vértice se define como el número de colores diferentes actualmente asignados a los vértices vecinos. También se utilizan otras reglas para desempatar.
Sea G un grafo con n vértices y m aristas. Además, supongamos que usaremos las etiquetas de color 0, 1, 2, …, n-1 . ( Nunca se requieren más de n colores en una solución). El algoritmo DSatur funciona de la siguiente manera
- Sea v el vértice no coloreado en G con el mayor grado de saturación. En caso de empates, elegir entre estos el vértice de mayor grado en el subgrafo inducido por los vértices no coloreados. Otros lazos se pueden romper arbitrariamente.
- Asigne v al color i , donde i es el entero más pequeño del conjunto {0, 1, 2, …, n} que actualmente no está asignado a ningún vecino de v .
- Si quedan vértices sin colorear, repita todos los pasos nuevamente, de lo contrario, finalice en este paso.
El algoritmo DSatur es similar al algoritmo Greedy en que una vez que se ha seleccionado un vértice, se asigna a la etiqueta de color más baja no asignada a ninguno de sus vecinos. Las acciones del Paso 1, por lo tanto, brindan el poder principal detrás del algoritmo en el sentido de que priorizan los vértices que se ven como los » más restringidos «, es decir, los vértices que actualmente tienen la menor cantidad de opciones de color disponibles. En consecuencia, estos vértices «más restringidos» se tratan primero, lo que permite colorear los vértices menos restringidos más adelante.
Análisis de DSatur
Debido a que el algoritmo DSatur genera una ordenación de vértices durante la ejecución, la cantidad de colores que utiliza es más predecible que el algoritmo voraz. Sus soluciones también tienden a tener menos colores que las del algoritmo voraz. Una característica del algoritmo es que, si un gráfico se compone de múltiples componentes, todos los vértices de un solo componente se colorearán antes de que se consideren los otros vértices. DSatur también es exacto para varias topologías de gráficos, incluidos gráficos bipartitos, gráficos de ciclo y gráficos de rueda. (Con estos gráficos, siempre se producirá una solución usando χ(G) colores).
La complejidad general del algoritmo DSatur es O(n 2 ) , donde n es el número de vértices en el gráfico. Esto se puede lograr realizando n aplicaciones separadas de un proceso O(n) que:
- Identifica el siguiente vértice a colorear según las reglas de selección de DSatur.
- Colorea este vértice.
A continuación presentamos una implementación en C++ de DSatur que opera en tiempo O((n + m) log n) , donde m es el número de aristas en el gráfico. Esto es mucho más rápido que O(n 2 ) para todos excepto los gráficos más densos. Esta implementación implica el uso de un árbol binario rojo-negro para almacenar todos los vértices que aún no están coloreados, junto con sus grados de saturación y sus grados en el subgrafo inducido por los vértices no coloreados. Los árboles rojo-negro son un tipo de árbol binario autoequilibrado que se utilizan con el conjuntocontainer en la biblioteca de plantillas estándar de C++. Esto permite que la selección del siguiente vértice a colorear (según las reglas de selección de DSatur) se realice en tiempo constante. También permite insertar y quitar elementos en tiempo logarítmico.
C++
// A C++ program to implement the DSatur algorithm for graph
// coloring
#include <iostream>
#include <set>
#include <tuple>
#include <vector>
using namespace std;
// Struct to store information
// on each uncoloured vertex
struct nodeInfo {
int sat; // Saturation degree of the vertex
int deg; // Degree in the uncoloured subgraph
int vertex; // Index of vertex
};
struct maxSat {
bool operator()(const nodeInfo& lhs,
const nodeInfo& rhs) const
{
// Compares two nodes by
// saturation degree, then
// degree in the subgraph,
// then vertex label
return tie(lhs.sat, lhs.deg, lhs.vertex)
> tie(rhs.sat, rhs.deg, rhs.vertex);
}
};
// Class representing
// an undirected graph
class Graph {
// Number of vertices
int n;
// Number of vertices
vector<vector<int> > adj;
public:
// Constructor and destructor
Graph(int numNodes)
{
n = numNodes;
adj.resize(n, vector<int>());
}
~Graph() { adj.clear(); }
// Function to add an edge to graph
void addEdge(int u, int v);
// Colour the graph
// using the DSatur algorithm
void DSatur();
};
void Graph::addEdge(int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
// Assigns colors (starting from 0)
// to all vertices and
// prints the assignment of colors
void Graph::DSatur()
{
int u, i;
vector<bool> used(n, false);
vector<int> c(n), d(n);
vector<set<int> > adjCols(n);
set<nodeInfo, maxSat> Q;
set<nodeInfo, maxSat>::iterator maxPtr;
// Initialise the data structures.
// These are a (binary
// tree) priority queue, a set
// of colours adjacent to
// each uncoloured vertex
// (initially empty) and the
// degree d(v) of each uncoloured
// vertex in the graph
// induced by uncoloured vertices
for (u = 0; u < n; u++) {
c[u] = -1;
d[u] = adj[u].size();
adjCols[u] = set<int>();
Q.emplace(nodeInfo{ 0, d[u], u });
}
while (!Q.empty()) {
// Choose the vertex u
// with highest saturation
// degree, breaking ties with d.
// Remove u from the priority queue
maxPtr = Q.begin();
u = (*maxPtr).vertex;
Q.erase(maxPtr);
// Identify the lowest feasible
// colour i for vertex u
for (int v : adj[u])
if (c[v] != -1)
used] = true;
for (i = 0; i < used.size(); i++)
if (used[i] == false)
break;
for (int v : adj[u])
if (c[v] != -1)
used] = false;
// Assign vertex u to colour i
c[u] = i;
// Update the saturation degrees and
// degrees of all uncoloured neighbours;
// hence modify their corresponding
// elements in the priority queue
for (int v : adj[u]) {
if (c[v] == -1) {
Q.erase(
{ int(adjCols[v].size()),
d[v], v });
adjCols[v].insert(i);
d[v]--;
Q.emplace(nodeInfo{
int(adjCols[v].size()),
d[v], v });
}
}
}
// The full graph has been coloured.
// Print the result
for (u = 0; u < n; u++)
cout << "Vertex " << u
<< " ---> Color " << c[u]
<< endl;
}
// Driver Code
int main()
{
Graph G1(5);
G1.addEdge(0, 1);
G1.addEdge(0, 2);
G1.addEdge(1, 2);
G1.addEdge(1, 3);
G1.addEdge(2, 3);
G1.addEdge(3, 4);
cout << "Coloring of graph G1 \n";
G1.DSatur();
Graph G2(5);
G2.addEdge(0, 1);
G2.addEdge(0, 2);
G2.addEdge(1, 2);
G2.addEdge(1, 4);
G2.addEdge(2, 4);
G2.addEdge(4, 3);
cout << "\nColoring of graph G2 \n";
G2.DSatur();
return 0;
}
Coloring of graph G1 Vertex 0 ---> Color 0 Vertex 1 ---> Color 2 Vertex 2 ---> Color 1 Vertex 3 ---> Color 0 Vertex 4 ---> Color 1 Coloring of graph G2 Vertex 0 ---> Color 0 Vertex 1 ---> Color 2 Vertex 2 ---> Color 1 Vertex 3 ---> Color 1 Vertex 4 ---> Color 0
La primera parte de esta implementación consiste en inicializar las estructuras de datos. Esto implica recorrer cada uno de los vértices y poblar el árbol rojo-negro. Esto toma tiempo O (n log n) . En la parte principal del algoritmo, el árbol rojo-negro permite que la selección del siguiente vértice a colorear se realice en tiempo constante. Una vez que u ha sido coloreado, los elementos correspondientes a los vecinos no coloreados de u deben actualizarse en el árbol rojo-negro. Hacer esto para cada vértice da como resultado un tiempo de ejecución total de O(m log n) . En consecuencia, el tiempo total de ejecución es O((n log n) + (m log n)) = O((n+m) log n) .
Puede encontrar más información sobre este algoritmo y otros para la coloración de gráficos en el libro: Una guía para la coloración de gráficos: algoritmos y aplicaciones (2021)
Publicación traducida automáticamente
Artículo escrito por rhydianlewis y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA