7.1.4 Ejemplo: el problema de Max Cut

El problema del Max Cut es el siguiente: Dado un grafo $G=(V,E)$ con pesos positivos en los arcos, el problema consiste en enconrar una partición de $V$ en conjuntos disjuntos $V_0$ $V_1$, al que la suma de los pesos de los arcos que tienen un extremo en $V_0$ y el otro en $V_1$ sea máxima.

Los pesos son simétricos ( $w_{i,j} = w_{j,i}$) y podemos definir una variable $x_i$ binaria como sigue:

$$x_i = \left \{ \begin{array}{ll} 1 & \mbox{si } i \in V_1 \\ 0 & \mbox{si } i \in V_0 \end{array}\right .$$

Entonces el problema Max Cut lo podemos formular como sigue:

$$max f(x) = \sum_{i=i}^n \sum_{j=i+1}^n w_{i,j} \{(1-x_i)x_j + x_i(1-x_j)\}$$

Sea $b_i$ la suma de los pesos de todos los nodos que inciden en el nodo $i$, i.e., $b_i=\sum_{j=1}^n w_{i,j}$. Si $C_b$ son las conecciones de sesgo (auto-conecciones) y $C_w$ son las conecciones de peso (entre nodos), una función de consenso que preserva el orden es:

$$\forall {u_i,u_i} \in C_b: w_{u_i,u_i}=b_i$$

$$\forall {u_i,u_j} \in C_w: w_{u_i,u_j}=-2w_{i,j}$$

En la figure 7.5 se ve un grafo de ejemplo y su máquina de Boltzmann correspondiente.

Figura 7.5: Ejemplo de una grafo para resolver el problema de Max Cut y su máquina de Boltzmann correspondiente.