Algoritmo mínimo de cobertura de vértices con programación lineal

Question

Considere el siguiente algoritmo: Dado un gráfico $ g $ con $ n $ vértices, configure Un problema de programación lineal LP donde hay una variable $ x_i $ para cada vértice $ v_i $ de $ g $ , cada variable puede tomar valor $ \ geq 0 $ , para cada uno borde $ v_av_b $ de $ g $ configurar la restricción $ x_a + x_b \ geq 1 $ . La función objetivo es $ \ min \ sum \ limits_ {1} ^ {n} {x_i} $ . Encuentre la variable (o una de las variables) $ x_i $ , entre las variables que no se establecen en $ 0 $ , que se establece en $ 0 $ proporciona el valor mínimo de la función objetivo. Agregue la restricción $ x_i= 0 $ a lp . Repita hasta que la solución óptima de LP sea entero (que es cada variable toma valor en $ \ \ {0; 1 \ derecha \} $ ).

Estoy buscando un gráfico donde los vértices asociados a las variables que toman valor $ 1 $ en la solución óptima final de lp son No es una cubierta de vértice mínima de $ g $ (si existe).

Answer 1

Considerar el gráfico

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

Configuración $ x_1, x_2, x_3, x_6 $ o $ x_7 $ a 0 le da a su LPun valor de 4, al configurar $ x_4 $ o $ x_5 $ a 0 le da a su LP un valor de5. Sin embargo, si configura $ x_1= 0 $ , finalmente obtendrá una cubierta de vértice de tamaño 5, mientras que la cubierta de vértice óptima es de tamaño 4.