حد أدنى خوارزمية غطاء الرأس مع البرمجة الخطية

Question

النظر في الخوارزمية التالية: إعطاء الرسم البياني $ g $ مع $ n $ القمم، إعداد مشكلة برمجة خطية LP حيث يوجد متغير $ x_i $ لكل قمة الرأس $ v_i $ من $ g $ ، يمكن لكل متغير أن يأخذ القيمة $ \ GEQ 0 $ ، لكل منها حافة $ v_av_b $ من $ g $ تعيين القيد $ X_A + X_B \ GEQ 1 $ . الوظيفة الهدف هي $ \ min \ sum \ limits_ {1} ^ {n} {x_i} $ . ابحث عن المتغير (أو أحد المتغيرات) $ x_i $ ، من بين المتغيرات غير مضبوطة على $ 0 $ ، التي اضبطت على $ 0 $ يعطي الحد الأدنى لقيمة الوظيفة الموضوعية. إضافة القيد $ x_i= 0 $ إلى LP . كرر حتى الحلا الأمثل ل LP هو عدد صحيح (هذا متغير يأخذ القيمة في $ \ {left \ {0؛ 1 \ right \} $ ).

أنا أبحث عن رسم بياني حيث تكون القمم المرتبطة بالمتغيرات التي تأخذ القيمة $ 1 $ في الحل الأمثل الأخير من LP ليس الحد الأدنى من غطاء الرأس $ g $ (إذا كان موجودا).

Answer 1

النظر في الرسم البياني

giveacodicetagpre.

إعداد $ x_1، x_2، x_3، x_6 $ أو $ x_7 $ to 0 يعطي LP الخاص بكقيمة 4، أثناء إعداد $ X_4 $ أو $ x_5 $ إلى 0 يعطي LP الخاص بك قيمة LP5. ومع ذلك، إذا قمت بتعيين $ x_1= 0 $ ، ستحصل أخيرا على غطاء رأس من الحجم 5، في حين أن غطاء الرأس الأمثل ذو الحجم 4.