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

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

تلوين الرسوم أو تلوين المخطط هو أحد أكثر المسائل شهرة وبحثا في نظرية المخططات، ولها الكثير من التطبيقات العملية وكثير من الحدسيات تتعلق بهذه المسألة وما زال كثير من علماء علوم الحاسوب والرياضيات يحاولون فك هذه الحدسيات.

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

تلوين الرؤوس عادة هي نقطة الانطلاق ومسائل التلوين الأخرى يمكن تحويلها إلى مسألة تلوين الرؤوس، مثلا «تلوين الأضلاع» هي «تلوين الرؤوس» في مخطط خط الملائم لهذا المخطط، و«تلوين الوجوه» هو «تلوين الرؤوس» للمخطط الثنائي الملائم. ولكن هذه المسائل تدرس كل واحدة على حدا ولا يُنظر إلى هذه العلاقة لعدة أسباب منها أنَّ بعض هذه المسائل يُفضل أن تدرس كما هي لبساطة التعاطي معها كما هي.

في الأصل استخدام مصطلح الألوان كان لأجل تلوين الخارطة، ولكن في علم الحاسوب والرياضيات بشكل عام يستخدم الأعداد الصحيحة للدلالة على الألوان. مسألة التلوين هي حالة خاصة من مسألة وسم المخطط.

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

تاريخ

لعل أول النتائج المتعلقة بهذه المسألة كانت تتعلق بالمخططات المستوية وقتها كانت المسألة على هيئة تلوين خرائط، وخلال محاولة تلوين مقاطعات إنجلترا فرانسيس غوثيري أطلق فرضية الاربع الوان، وهذا لانه لاحظ أن أربعة الوان تكفي لتلوين كل المقاطعات بحيث لا تكون هناك مقاطعتان مجاورتان تشتركان بنفس اللون. بعث أخو فرانسيس غوثيري هذه الفرضية لاستاذه في جامعة لندن اغوسطوس دي مورغن، وذكرها لاحقا لهاملتون في رسالة عام 1852. لاحقا ارثور كايلي استعرض المسألة امام مجتمع لندن الرياضي عام 1879. في نفس العام الفرد كيمبي زعم انه قدم حلا للمسألة ولعقد كامل اعتقد الجميع ان المسألة قد انتهت، ومن اجل ذلك انتخب ليكون عضوا في مجتمع لندن الرياضي ولاحقا ليكون رئيسا للمجتمع.

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

عام 1912 عرض جورج دافيد بريكهوف «متعدد الحدود اللوني» لدراسة مسألة التلوين، ولاحقا طوره بيل توت ل«متعدد حدود توت»، وهذين هما بنيتان مهمتان في جبر المخططات. وقد كان كيمبي قد اشار إلى الحالة العامة عندما يكون المخطط ليس مستويا، والعديد من التوسيعات لهذه النظريات لمسطحات في ابعاد اعلى قد ظهرت خلال القرن العشرين.

مسألة تلوين المخطط درست على انها مسألة خوارزمية منذ سبيعنيات القرن العشرين، بحيث ان مسألة رقم التلوين موجودة في قائمة كارب منذ عام 1972، لعل أحد أهم التطبيقات المتعلقة بمسألة التلوين هي مسألة تخصيص السجلات في المترجم عرضت عام 1981.

خصائص

تحديد أقل عدد ممكن من الألوان يسمى عدد التلوين. وتحديد هذا العدد من المشاكل الكاملة، وهذا المشكل له علاقة قريبة جدا من مشكلة المخطط الكامل ضمن مخطط ومشكلة المخطط المستقر ضمن مخطط.

التلوين بثلاثة ألوان

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

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

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

الاختصار

gadjet 3COL

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

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

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