تلوين مخطط بثلاثة ألوان
من ويكيبيديا، الموسوعة الحرة
| مسألة NP كاملة | 
|---|
| 
 | 
| 
 | 
| زمرة كبرى | 
| مسار هاملتونياني | 
| عدل | 
تلوين المخطط باستعمال ثلاثة ألوان هي مسألة مشتقة من المسألة العامة تلوين مخطط و تتم باستعمال ثلاثة ألوان فقط، و رغم ذلك فهي مسألة NP كاملة.
[تحرير] تلوين مخطط بثلاثة ألوان مسألة كاملة
انطلاقا من SAT نحصل على مخطط عادي غير موجه، حيث يكون للصيغة حل إذا و فقط إذا كان هناك تلوين بثلاثة ألوان فقط. بعبارة أوضح حل SAT يحل مشكلة التلوين و حل مشكلة التلوين تحل SAT.
[تحرير] الاختصار
يتم من SAT لكل صيغة نربطها بمخطط عادي غير موجه، طريقة إنشائه كما يلي:
- لكل متغيرين متقابلين  و و نرسم قمتين مرتبطتين، نرسم قمتين مرتبطتين، خاصة ب خاصة ب و و خاصة ب خاصة ب . .
- لكل رمز  (أول رمز)، نرسم مثلث قممه A1 و B1 و C1. و تسمى A رأس المثلث. (أول رمز)، نرسم مثلث قممه A1 و B1 و C1. و تسمى A رأس المثلث.- في حالة وجود  نربط القمة نربط القمة بB. أما في حالة وجود بB. أما في حالة وجود نربط القمة نربط القمة بB. بB.
- بالنسبة للمتغير الثاني في الصيغة clause يتم ربط القمة التي تمثله بِC بنفس طريقة الربط مع B.
 
- في حالة وجود 
- لكل رمز  موالي(انطلاقا من ثاني رمز)، نرسم مثلث قممه A2 و B2 و C2. نربط A1 ب B2. و C2 بتمثيل المتغير الثالث. موالي(انطلاقا من ثاني رمز)، نرسم مثلث قممه A2 و B2 و C2. نربط A1 ب B2. و C2 بتمثيل المتغير الثالث.
- المثلث الأخير و الذي يرمز لآخر رمز في الصيغة clause نسمي رأسه A برأس العبارة.
- في الأخير نضيف قمتين مرتبطتين الأولى محايدة N و الثانية منعدمة Z:
- القمة N مرتبطة برؤوس المثلثات و بالقمم التي تمثل المتغيرات.
- القمة Z مرتبطة برؤوس العبارات.
 
الآن نستعمل للتلوين الأعداد 0 و 1 و 2، القمة N تلون ب2 و القمة z تلون ب3، هذا سيؤدي لتلوين جميع رؤوس العبارات باللون 1. و بعد انتهاء عملية التلوين، بالنسبة للصيغة نعطي للمتغير  القيمة 1 في حالة كانت القمة
 القيمة 1 في حالة كانت القمة  ملونة باللون 1، بينما يأخد القيمة 0 في حالة كانت القمة
 ملونة باللون 1، بينما يأخد القيمة 0 في حالة كانت القمة  ملونة باللون 0.
 ملونة باللون 0.



