والحد من 3-تلوين المشكلة الثلاثي الممثلين

Question

مجموعة من الطلاب ينقسم إلى ثلاثيات - مجموعات من 3 أعضاء.كل طالب يمكن أن تسند إلى أكثر من الثلاثي.نحن نريد أن تعيين ممثليهم عن طريق اختيار واحد بالضبط عضو كل من الثلاثي.هو هذه المهمة ممكن ؟

هدفي هو استخدام متعدد الحدود-إجراء تحويل 3-تلوين الرسم البياني في هذه المشكلة.ولكن أنا عالقة على التمثيل الصحيح.

• إذا كل قمة هي مختلفة الطالب حواف تمثل يجري في نفس الثلاثي, كيف يمكنني منفصلة ثلاثيات?

• إذا كل عقدة يمثل الثلاثي, ماذا يمكن أن يكون معقول المعنى من الحواف ؟

وأظن أنه منذ 4 زمرة لا الكافية 3-تلوين (والتي يمكن أن يعني أيضا أن 4 ثلاثيات مع نفس ثلاثة أعضاء لا يوجد لها أي ممثل الانتداب) ، فإن الخيار الأخير يمكن أن يكون أكثر عقلانية ، ولكن أنا غير متأكد بشأن كيفية المضي قدما مع هذا التخفيض دليل على ذلك.

Answer 1

السماح $G = (V,E)$ يكون مثيل $3$ التلوين.لإنشاء مثيل $\phi$ من 3-SAT على النحو التالي.

• على كل قمة $v \في الخامس$ إنشاء $3$ المتغيرات $v_a, v_b, v_c$ تمثل $3$ السبل الممكنة لون $v$.
• على كل قمة $v \في الخامس$ خلق الشروط $(v_a \مخروطى v_b \مخروطى v_c) \إسفين (\overline{v_a} \مخروطى \overline {v_b}) \إسفين (\overline{v_b} \مخروطى \overline {v_c}) \إسفين (\overline{v_c} \مخروطى \overline {v_a})$.هذا بترميز حقيقة $v$ يجب أن تكون ملونة من لون واحد بالضبط.
• لكل الحافة $(u,v) \في E$ خلق الشروط $( \overline{v_a} \مخروطى \overline{u_a} ) \إسفين ( \overline{v_b} \مخروطى \overline{u_b} ) \إسفين ( \overline{v_c} \مخروطى \overline{u_c} )$.هذا يضمن أن $u$ و $v$ لا يمكن أن تعطى نفس اللون.

بوضوح فوق الحد لا يمكن أن يؤديها في poylnomial الوقت و يضمن أن هناك مرضية المهمة $\phi$ المنتدى هناك 3-التلوين على $G$.

الآن تحويل مثيل $\phi$ 3-جلس إلى ما يعادل سبيل المثال $\phi'$ 1-in-3 السبت (انظر هنا تعريف 1-في 3 سبت والحد من 3-SAT).

لدينا ومن ثم تبين أن 3-التلوين هو متعدد الحدود-الوقت يمكن اختزالها إلى 1-in-3 السبت.اتضح أن 1-in-3 السبت هو بالضبط المشكلة:مجموعة من الطلاب هو مجموعة من المتغيرات بالنسبة لكل بند $\{x_i, x_j, x_k\}$ يمكنك إنشاء مجموعة تحتوي على الطلاب $x_i$, $x_j$, ، $x_k$.وضع متغير صحيح يتوافق مع تحديد المقابلة الطالب كزعيم.