coloración débil
En la teoría de grafos , una coloración débil es un caso especial de etiquetado de grafos . Una coloración k débil de un gráfico G = ( V , E ) asigna un color c ( v ) ∈ {1, 2, ..., k } a cada vértice v ∈ V , tal que cada vértice no aislado es adyacente a al menos un vértice con diferente color. En notación, para cada v ∈ V no aislado , hay un vértice u ∈ V con { u ,v } ∈ mi y c ( tu ) ≠ c ( v ) .
La figura de la derecha muestra una débil coloración en 2 de un gráfico. Cada vértice oscuro (color 1) es adyacente a al menos un vértice claro (color 2) y viceversa.
Cada gráfico tiene una coloración 2 débil. La figura de la derecha ilustra un algoritmo simple para construir una coloración débil de 2 en un gráfico arbitrario. La parte (a) muestra el gráfico original. La parte (b) muestra un árbol de búsqueda primero en anchura del mismo gráfico. La parte (c) muestra cómo colorear el árbol: comenzando desde la raíz, las capas del árbol se colorean alternativamente con los colores 1 (oscuro) y 2 (claro).
Si no hay un vértice aislado en el grafo G , entonces una coloración débil en 2 determina una partición dómática : el conjunto de los nodos con c ( v ) = 1 es un conjunto dominante , y el conjunto de los nodos con c ( v ) = 2 es otro conjunto dominante.
Históricamente, la coloración débil sirvió como el primer ejemplo no trivial de un problema gráfico que se puede resolver con un algoritmo local (un algoritmo distribuido que se ejecuta en un número constante de rondas de comunicación síncrona). Más precisamente, si el grado de cada nodo es impar y está acotado por una constante, entonces hay un algoritmo distribuido en tiempo constante para 2 colores débiles. [1]
Esto es diferente de la coloración de vértices (no débil) : no hay un algoritmo distribuido en tiempo constante para la coloración de vértices; los mejores algoritmos posibles (para encontrar una coloración mínima pero no necesariamente mínima) requieren O ( log * | V |) rondas de comunicación. [1] [2] [3] Aquí log * x es el logaritmo iterado de x .
