Minimaler Scheitelpunkt-Abdeckungsalgorithmus mit linearer Programmierung

Question

Betrachten Sie den folgenden Algorithmus: Angesichts eines Diagramms $ g $ mit $ n $ Scheitelpunkte, einrichten Ein lineares Programmierproblem lp wo es eine Variable $ x_i $ für jeden Vertex $ v_i $ gibt von $ g $ , jede Variable kann Wert $ \ geq 0 $ für jeden annehmen Edge $ v_av_b $ von $ g $ Set die Einschränkung $ x_a + x_b \ geq 1 $ . Die objektive Funktion ist $ \ min \ sum \ limits_ {1} ^ {n} {x_i} $ . Finden Sie die Variable (oder eine der Variablen) $ x_i $ , zwischen den Variablen, die nicht auf $ 0 $ eingestellt sind , das auf $ 0 $ eingestellt ist, gibt den Mindestwert der objektiven Funktion an. Fügen Sie die Einschränkung $ x_i= 0 $ auf lp . Wiederholen, bis die optimale Lösung von lp integer (dh jede Variable ist der Wert in $ \ Links \ {0; 1 \ Right \} $ ).

Ich suche nach einem Diagramm, in dem die Variablen verknüpft sind, die den Variablen zugeordnet sind $ 1 $ in der endgültigen optimalen Lösung von lp Kein Minimum Scheitelpunkt von $ g $ (falls vorhanden).

Answer 1

Betrachten Sie die Grafik

generasacodicetagpre.

Einstellung $ X_1, X_2, X_3, X_6 $ oder $ x_7 $ bis 0 gibt Ihrem LP anEin Wert von 4, während der Einstellung $ X_4 $ oder $ X_5 $ bis 0 gibt Ihrem LP einen Wert von5. Wenn Sie jedoch $ X_1= 0 $ einstellen, erhalten Sie schließlich einen Scheitelpunktabdeckung von Größe 5, während die optimale Scheitelpunktabdeckung von Größe 4 ist.