La definición estándar de coloreado de grafos (véase aquí ) en grafos no dirigidos es:
Una coloración es un etiquetado de los vértices del grafo con colores tales que no hay dos vértices que compartan la misma arista que tengan el mismo color.
Es bien sabido que el número cromático de un gráfico $G$ , $\chi(G)$ denota el número mínimo de colores necesarios para obtener una coloración "adecuada" del grafo.
Supongamos ahora que el número de colores disponibles es $k < \chi(G)$ . En este caso, cualquier asignación de colores a los vértices puede verse como una coloreado débil de grafos ya que es seguro que hay al menos dos vértices conectados que comparten el mismo color.
En este concurso, dado un grafo no dirigido $G$ de $N$ nodos representados por una matriz de adyacencia binaria $A$ y una coloración débil del grafo $\alpha \in \{1, \ldots, k\}^N$ (es decir, una asignación genérica de colores a los vértices de $G$ ), se puede definir un función de pérdida como:
$$\mathcal{L}(G, \alpha) = \frac{1}{2}\sum_{v = 1}^N \sum_{w = 1}^N a_{v,w} \delta_{\alpha_v, \alpha_w},$$
donde $\alpha_v$ es el color del nodo $v$ , $\alpha_w$ es el color de $w$ y $\delta_{x,y}$ es el delta de Kronecker (es decir. $\delta_{x,y} = 1 \iff x=y$ y $\delta_{x,y}=0 \iff x \neq y$ ). La función $\mathcal{L}(G, \alpha)$ cuenta el número de enlaces que conectan nodos con el mismo color.
Por supuesto, cuando $\alpha$ es una coloración "adecuada", $\mathcal{L}(G, \alpha) = 0$ mientras que en el caso "débil", $\mathcal{L}(G, \alpha) > 0$ .
¿Existe bibliografía/referencias sobre este tipo de problemas, sobre esta función de pérdida y sobre su optimización? Gracias de antemano.
