استخدم 2SAT لإظهار أن الرسوم البيانية التضمين يجب أن يكون لها دورة إذا لم تكن راضية

Question

باستخدام الرسوم البيانية 2SAT وتضمين، كيف يمكنني إثبات الخصائص التالية لرسوم الرسوم البيانية التضمين:

لنفترض أن هناك مسار موجه بين حرفية L1 و L2 في G_φ. ثم هناك أيضا مسار موجه بين تكملهن. بعد ذلك، هناك τ، مهمة الحقيقة مرضية حيث τ (l1) صحيح، ثم يجب أن يكون τ (L2) صحيحا أيضا.

باستخدام هذا، أظهر أن غير مرضية <=> هناك بعض الدورة الموجهة في G_φ تحتوي على متغير X واستكماله.

حيث g_φ هو الرسم البياني التضمين الموجه من 2SAT تحتوي على صيغة مع متغيرات N. وبالتالي، فإن القمم 2N مع واحد لكل حرفي ممكن في، والحواف (وليس L1، L2) و (وليس L2، L1) لكل جملة (L1 ∨ L2) في.

كان الحدس الأول دليلا على التناقض ولكن فشلت في بناء افتراض عام كاف. ثم حاولت أن أظهر أنه إذا كانت مهمة الحقيقة تعني أن L1 و L2 صحيح، ثم من خلال بناء دورة توصيل جميع المتغيرات، فإن المهمة صالحة فقط عند وجود هذه الحواف. ومع ذلك، لا يبدو هذا صارما بما فيه الكفاية لأنني لا أفهمه بشكل صحيح سبب وجود الدورة مكملا من X إلى موجودة.

حاليا أقوم بإنشاء G عن طريق إضافة قمة إلى كل متغير x واستكمل أيضا. ثم لكل جملة (A V B) أضيف حافة بين ليس A و B وليس B و A.

ومع ذلك فشلت في معرفة كيفية تشكيل هذا على وجه التحديد دورة.

العمل في كتاب Sipser.

Answer 1

هنا هو رسم دليل. سنبين أن الصيغة المعينة غير مرضية IFF هناك توجد دورة تحتوي على كل من $ X $ و $ \ lnot x $ < / span>، بالنسبة لبعض المتغير $ x $ .

لنفترض أولا على وجود دورة تحتوي على كل من $ x $ $ \ lnot x $ . وجود مسار $ x \ إلى ^ * y $ في الرسم البياني التضمين يعني أنه في مهمة مرضية، إذا $ إكس $ يحمل ثم يفعل $ y $ (يمكنك إثبات ذلك عن طريق التعريفي على طول المسار). نظرا لوجود دورة تحتوي على كل من $ × $ و $ \ lnot x $ ، هناك مسارات $ x \ to ^ * \ lnot x $ و $ \ lnot x \ to ^ * x $ . في أي مهمة مرضية، إما $ x $ أو $ \ lnot x $ holds، وكلتا الحالتين تؤدي إلى تناقض.

افترض بجانب عدم وجود دورات تحتوي على كل من $ x $ و $ \ lnot x $ . سنقوم ببناء مهمة مرضية على النحو التالي. اختر بعض المتغيرات $ x $ . إذا كان هناك مسار $ x \ to ^ * \ lnot x $ ، قم بتعيين $ x= f $ ، ولكل كل حرفي $ \ ell $ مثل $ \ lnot x \ to ^ * \ ell $ ، تعيين القيمة إلى المتغير الأساسي مما يجعل $ \ ell $ true. لا يمكنك تعيين نفس المتغير لقيم الحقيقة المختلفة، حيث أنه $ \ lnot x \ to ^ * y $ و $ \ Lnot x \ to ^ * \ lnot y $ ثم أيضا $ y \ إلى ^ * x $ وكذلك أيضا $ \ lnot x \ to ^ * x $ ، إكمال دورة تنطوي على $ x $ و $ \ lnot x $ .

إذا كان هناك مسار $ \ lnot x \ to ^ * x $ ، وتعيين $ x= t $ < / span>، وتابع حقا.

إذا كانت أي من هذه المسارات موجودة، قم بتعيين $ x $ بشكل تعسفي، وتستمر كما كان من قبل. هذا لا يمكن أن يؤدي إلى تناقض، والسبب التالي. افترض أننا نخصص $ x= f $ ، وأن هناك مسارات $ x \ to ^ * y $ و $ x \ to ^ * \ lnot y $ . ثم هناك أيضا مسار $ y \ to ^ * \ lnot x $ وهكذا المسار $ x \ to ^ * \ Lnot X $ ، تناقض مع افتراض أن أيا من المسارين موجودين.

إذا كان هناك بعض هذه العملية هناك بعض المتغير غير المعين، فاختر أحدها، وكرر حتى تغطي المهمة جميع المتغيرات.