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

من موسوعة العلوم العربية
اذهب إلى: تصفح، ابحث

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

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

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

الاختصار

gadjet 3COL

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

  1. لكل متغيرين متقابلين خطأ رياضيات (خطأ غير معروف): x \,
وخطأ رياضيات (خطأ غير معروف): \lnot x
نرسم قمتين مرتبطتين، خطأ رياضيات (خطأ غير معروف): U_x \,
خاصة ب خطأ رياضيات (خطأ غير معروف): x \,
وخطأ رياضيات (خطأ غير معروف): U_{\lnot x}
خاصة ب خطأ رياضيات (خطأ غير معروف): \lnot x

.

  1. لكل رمز خطأ رياضيات (خطأ غير معروف): \lor
(أول رمز)، نرسم مثلث قممه خطأ رياضيات (خطأ غير معروف): A_1
وخطأ رياضيات (خطأ غير معروف): B_1
وخطأ رياضيات (خطأ غير معروف): C_1

. وتسمى A رأس المثلث.

    1. في حالة وجود خطأ رياضيات (خطأ غير معروف): x \,
نربط القمة خطأ رياضيات (خطأ غير معروف): U_x \,
بB. أما في حالة وجود خطأ رياضيات (خطأ غير معروف): \lnot x
نربط القمة خطأ رياضيات (خطأ غير معروف): U_{\lnot x}
بB.
    1. بالنسبة للمتغير الثاني في الصيغة clause يتم ربط القمة التي تمثله بِC بنفس طريقة الربط مع B.
  1. لكل رمز خطأ رياضيات (خطأ غير معروف): \lor
موالي(انطلاقا من ثاني رمز)، نرسم مثلث قممه خطأ رياضيات (خطأ غير معروف): A_2
وخطأ رياضيات (خطأ غير معروف): B_2
وخطأ رياضيات (خطأ غير معروف): C_2

. نربط خطأ رياضيات (خطأ غير معروف): A_1

ب خطأ رياضيات (خطأ غير معروف): B_2

. وخطأ رياضيات (خطأ غير معروف): C_2

بتمثيل المتغير الثالث.
  1. المثلث الأخير والذي يرمز لآخر رمز في الصيغة clause نسمي رأسه خطأ رياضيات (خطأ غير معروف): A
برأس العبارة.
  1. في الأخير نضيف قمتين مرتبطتين الأولى محايدة خطأ رياضيات (خطأ غير معروف): N
والثانية منعدمة خطأ رياضيات (خطأ غير معروف): Z
    1. القمة خطأ رياضيات (خطأ غير معروف): N
مرتبطة برؤوس المثلثات وبالقمم التي تمثل المتغيرات.
    1. القمة خطأ رياضيات (خطأ غير معروف): Z
مرتبطة برؤوس العبارات.

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

القيمة 1 في حالة كانت القمة خطأ رياضيات (خطأ غير معروف): U_x \,
ملونة باللون 1، بينما يأخد القيمة 0 في حالة كانت القمة خطأ رياضيات (خطأ غير معروف): U_x \,
ملونة باللون 0.