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

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

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

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

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

الاختصار

gadjet 3COL

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

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

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