Cobertura mínima de vértices algoritmo com programação linear

Question

Considere o seguinte algoritmo:dado um gráfico $G$ com $n$ vértices, configure um problema de programação linear LP onde há uma variável $x_i$ para cada vértice $v_i$ de $G$, cada variável pode tomar o valor $\geq 0$, para cada borda $v_av_b$ de $G$ definir a restrição de $x_a+x_b\geq 1$.A função objetivo é $\min\sum\limits_{1}^{n}{x_i}$.Localize a variável (ou uma das variáveis) $x_i$, entre as variáveis não definidas para $0$, que defina a $0$ dá o mínimo valor da função objetivo.Adicionar a restrição $x_i=0$ para LP.Repita até que a solução ótima de LP é o número inteiro (que é cada variável assume valor $\left\{0;1 ight\}$).

Eu estou procurando um grafo onde os vértices associados às variáveis que tomar o valor $1$ no final, a solução ótima de LP não são uma cobertura mínima de vértices de $G$ (se ele existir).

Answer 1

Considere o gráfico

  2-4---7
 /  |\ /|
1   | × |
 \  |/ \|
  3-5---6

Definição $x_1,x_2,x_3,x_6$ ou $x_7$ a 0 dá o seu LP de um valor de 4, enquanto a definição de $x_4$ ou $x_5$ a 0 dá o seu LP de um valor de 5.No entanto, se você definir $x_1=0$, você vai finalmente chegar a uma cobertura de vértices de tamanho 5, enquanto o ideal de cobertura de vértices é do tamanho 4.