Coloreo de Grafos

Dado un grafo no dirigido $(G,E)$, con un conjunto $V$ de vértices y $E$ de aristas. Un coloreo válido de $G$ se corresponde a una partición de $V$ en $K$ conjuntos independientes, donde dos elementos adyacentes no pertenecen al mismo conjunto. El objetivo es minimizar $K$. Donde $\min K=\chi (G)$ es el número cromático del grafo.

Un Conjunto independiente en un grafo es un conjunto de vértices tal que ninguno de Los vértices son adyacentes a otro. Un conjunto independiente máximo es un conjunto tal que al agregarle un vértice más, deja de ser independiente.

Definimos $L_{ij}$ como verdadero si el nodo $i$ es adyacente al nodo $j$. Esta es una constante en nuestro problema. También definimos $Y_{ij}$ como verdadera si el nodo $i$ tiene el color $j$. Por último $Y_j$ indica que usamos el color $j$.

El objetivo será minimizar la cantidad de colores, por lo que:

$$Z_{\min }=\sum _{j=1}^V{Y}_J$$

Cada vértice debe tener un solo color, por lo que:

$$\sum _{i=1}^V{Y}_{ij}=1,\forall j$$

Si dos vértices son adyacentes, no pueden tener el mismo color

$$Y_{ij}+Y_{kj}\le Y_j,\text{si }[i,k]\in E,\forall j$$

Modelo por Conjuntos Independientes

Colorear es determinar a que conjunto independiente pertenece cada vértice, cada conjunto luego se colorea de un mismo color. Para este modelo, debemos determinar todos los conjuntos independientes del grafo. Sea $S$ el conjunto de todos los conjuntos independientes

Definimos $Y_{S_i}=1$ si todos los vértices de $S_i$ son coloreados con un mismo color, y $0$ en caso contrario.

Debemos minimizar la cantidad de conjuntos independientes seleccionados

$$Z_{\min }=\sum _i{Y}_{S_i}$$

Cada vértice debe pertenecer a exactamente uno de los conjuntos independientes usados

$$\sum _{i:v\in S_i}{Y}_{S_i}=1,\forall v\in V$$

Modelo por conjuntos independientes maximal

Para reducir la cantidad de variables, solo se modelan los conjuntos independientes maximales (conjuntos independientes a los que no se les puede agregar ningún vértice y que sigan siendo independientes). Sea $M$ el conjunto de todos los conjuntos independientes maximales, ahora permitimos que un vértice pertenezca a más de un conjunto (luego es a arbitrario el color que se le asigna)

$$\sum _{i:v\in M_i}{Y}_{M_i}\ge 1,\forall v\in V$$

Relajación Lineal

Si se quita las restricciones de las variables enteras, entonces el modelo usara únicamente dos colores, pintando cada vértice de dos colores. Esta solución es factible y, por lo tanto, la técnica de relajación lineal no es útil.

Simetría

Cuando se resuelve de manera exacta un problema de coloreo de grafos, aparecen muchas soluciones alternativas. Este es el problema de la simetría.

$$w_j\le \sum _{i\in V}{Y}_{ij},\forall j=1,\cdots ,n$$ $$w_j\ge w_{j+1},\forall j=1,\cdots ,n-1$$

Con estas dos restricciones, obligamos a los colores a realizarse de forma ordenada. Donde el grupo con mayor cantidad de nodos tomará el primer color, el segundo con mayor cantidad de nodos tomará el segundo color y así sucesivamente. Podemos agrupar estas dos restricciones de la siguiente forma:

$$\sum _{i=1}^n{x}_{ij}\ge \sum _{i=1}^n{x}_{ij+1}$$