Espero que me puedan ayudar con esto. Estoy atascado con una formulación de programación entera para el llamado Problema del Cartero Chino No Dirigido.
Consideremos un grafo no dirigido $G=(V,E)$ , donde $V$ es el conjunto de vértices y E es el conjunto de $edges$ . Sea $E(S)=\{(i,j) : i\in S, j\in V\setminus S\text{, or } i\in V\setminus S, j\in S\}$ sea un subconjunto de vértices de grado impar, $S \subseteq V$ se dice que es impar si es un conjunto formado por un número impar de vértices de grado impar"
Este último impar es la condición con la que estoy luchando.
La formulación es la siguiente: \begin{align} \min \ &\sum_{(i,j)\in E}c_{ij}x_{ij} \\ \text{Subj to }&\sum_{(i,j)\in E(S)} x_{ij}\geq 1,\quad S\subset V,S\text{ odd} \\ &x_{ij}\geq 0,\quad (i,j)\in E \\ &x_{ij}\in \mathbb{Z},\quad (i,j)\in E \end{align}
Según la primera restricción, ¿significa que si tenemos un grafo con un número par de vértices de grado impar no podemos resolver el CPP? o lo estoy entendiendo totalmente mal?
Considere este gráfico en particular . ¿Cómo sería la formulación para este caso? Sería muy útil que explicaras la formulación para la restricción 1. Gracias.
