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

gadjet 3COL

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

1. لكل متغيرين متقابلين ${\displaystyle x\,}$ و${\displaystyle \lnot x}$ نرسم قمتين مرتبطتين، ${\displaystyle U_{x}\,}$ خاصة ب ${\displaystyle x\,}$ و${\displaystyle U_{\lnot x}}$ خاصة ب ${\displaystyle \lnot x}$.
2. لكل رمز ${\displaystyle \lor }$ (أول رمز)، نرسم مثلث قممه ${\displaystyle A_{1}}$ و${\displaystyle B_{1}}$ و${\displaystyle C_{1}}$. وتسمى A رأس المثلث.
   1. في حالة وجود ${\displaystyle x\,}$ نربط القمة ${\displaystyle U_{x}\,}$ بB. أما في حالة وجود ${\displaystyle \lnot x}$ نربط القمة ${\displaystyle U_{\lnot x}}$ بB.
   2. بالنسبة للمتغير الثاني في الصيغة clause يتم ربط القمة التي تمثله بِC بنفس طريقة الربط مع B.
3. لكل رمز ${\displaystyle \lor }$ موالي (انطلاقا من ثاني رمز)، نرسم مثلث قممه ${\displaystyle A_{2}}$ و${\displaystyle B_{2}}$ و${\displaystyle C_{2}}$. نربط ${\displaystyle A_{1}}$ ب ${\displaystyle B_{2}}$. و${\displaystyle C_{2}}$ بتمثيل المتغير الثالث.
4. المثلث الأخير والذي يرمز لآخر رمز في الصيغة clause نسمي رأسه ${\displaystyle A}$ برأس العبارة.
5. في الأخير نضيف قمتين مرتبطتين الأولى محايدة ${\displaystyle N}$ والثانية منعدمة ${\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.