تلوين مخطط بثلاثة ألوان

مسألة NP كاملة
قابلية الإرضاء 3سات NAE OIT
تلوين مخطط تلوين مخطط بثلاثة ألوان تلوين مخطط مستو بثلاثة ألوان
زمرة كبرى
مسار هاملتونياني
عدل

تلوين المخطط باستعمال ثلاثة ألوان هي مسألة مشتقة من المسألة العامة تلوين مخطط و تتم باستعمال ثلاثة ألوان فقط، و رغم ذلك فهي مسألة NP كاملة.

تلوين مخطط بثلاثة ألوان مسألة كاملة

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

الاختصار

gadjet 3COL

يتم من SAT لكل صيغة نربطها بمخطط عادي غير موجه، طريقة إنشائه كما يلي:

لكل متغيرين متقابلين $x \,$ و $\lnot x$ نرسم قمتين مرتبطتين، $U_x \,$ خاصة ب $x \,$ و $U_{\lnot x}$ خاصة ب $\lnot x$ .
لكل رمز (أول رمز)، نرسم مثلث قممه A₁ و B₁ و C₁. و تسمى A رأس المثلث.
1. في حالة وجود $x \,$ نربط القمة $U_x \,$ بB. أما في حالة وجود $\lnot x$ نربط القمة $U_{\lnot x}$ بB.
2. بالنسبة للمتغير الثاني في الصيغة clause يتم ربط القمة التي تمثله بِC بنفس طريقة الربط مع B.
لكل رمز $\lor$ موالي(انطلاقا من ثاني رمز)، نرسم مثلث قممه $A 2$ و $B 2$ و $C 2$ . نربط $A 1$ ب $B 2$ . و $C 2$ بتمثيل المتغير الثالث.
المثلث الأخير و الذي يرمز لآخر رمز في الصيغة clause نسمي رأسه $A$ برأس العبارة.
في الأخير نضيف قمتين مرتبطتين الأولى محايدة N و الثانية منعدمة Z:
1. القمة $N$ مرتبطة برؤوس المثلثات و بالقمم التي تمثل المتغيرات.
2. القمة $Z$ مرتبطة برؤوس العبارات.

الآن نستعمل للتلوين الأعداد 0 و 1 و 2، القمة N تلون ب2 و القمة z تلون ب3، هذا سيؤدي لتلوين جميع رؤوس العبارات باللون 1. و بعد انتهاء عملية التلوين، بالنسبة للصيغة نعطي للمتغير $x \,$ القيمة 1 في حالة كانت القمة $U_x \,$ ملونة باللون 1، بينما يأخد القيمة 0 في حالة كانت القمة $U_x \,$ ملونة باللون 0.