تاريخ

لعل اول النتائج المتعلقة بهذه المسألة كانت تتعلق بالمخططات المستوية وقتها كانت المسألة على هيئة تلوين خرائط , وخلال محاولة تلوين مقاطعات انجلترا فرانسيس غوثيري اطلق فرضية الاربع الوان , وهذا لانه لاحظ ان اربعة الوان تكفي لتلوين كل المقاطعات بحيث لا تكون هناك مقاطعتان مجاورتان تشتركان بنفس اللون . بعث أخو فرانسيس غوثيري هذه الفرضية لاستاذه في جامعة لندن اغوسطوس دي مورغن , وذكرها لاحقا لهاملتون في رسالة عام 1852 . لاحقا ارثور كايلي استعرض المسألة امام مجتمع لندن الرياضي عام 1879 . في نفس العام الفرد كيمبي زعم انه قدم حلا للمسألة ولعقد كامل اعتقد الجميع ان المسألة قد انتهت , ومن اجل ذلك انتخب ليكون عضوا في مجتمع لندن الرياضي ولاحقا ليكون رئيسا للمجتمع . في عام 1890 هي-وود فند برهنة كيمبي للحدسية , ولكنه قدم نظرية الخمس الوان , اي انه برهن ان كل مخطط مستو يمكن تلوينه بواسطة خمس الوان فقط وهذا بمساعدة افكار كيمبي , وفي القرن التالي كمية كبيرة من النظريات والتقدم حصل لتخفيض عدد الالوان إلى اربعة إلى ان حلت المسألة عام 1976 بواسطة كينيث ابل وولفغانغ هيكن . حل المسألة تجاهل كل التطور والتغيرات التي طرات على المسألة وعاد إلى افكار هي-وود وكيمبي , كما ان حل هذه المسألة هو اول حل يعتمد على الحاسوب . عام 1912 عرض جورج دافيد بريكهوف متعدد الحدود اللوني لدراسة مسألة التلوين , ولاحقا طوره بيل توت ل متعدد حدود توت , وهذين هما بنيتان مهمتان في جبر المخططات . وقد كان كيمبي قد اشار إلى الحالة العامة عندما يكون المخطط ليس مستويا , والعديد من التوسيعات لهذه النظريات لمسطحات في ابعاد اعلى قد ظهرت خلال القرن العشرين . مسألة تلوين المخطط درست على انها مسألة خوارزمية منذ سبيعنيات القرن العشرين , بحيث ان مسألة رقم التلوين موجودة في قائمة كارب منذ عام 1972 , لعل أحد أهم التطبيقات المتعلقة بمسألة التلوين هي مسألة تخصيص السجلات في المصرف المترجم عرضت عام 1981 .

تعريف

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

خصائص

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

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

تلوين مخطط ما باستعمال ثلاثة ألوان فقط، هو أيضا مشكل كامل حيث يمكن اختصار أي مشكل من صنف المشاكل غير المحددة لمشكل التلوين بثلاثة ألوان. شريط بوابات رياضيات تصنيف كومنز Graph coloring تصنيف تلوين المخططات تصنيف معضلات حاسوبية في نظرية المخططات تصنيف نظرية المخططات تصنيف مسائل NP كاملة مسألة NP كاملة مسألة تلوين المخطط أحد اكثر المسائل شهرة وبحثا في نظرية المخططات , ولها الكثير من التطبيقات العملية وكثير من الحدسيات تتعلق بهذه المسألة وما زال كثير من علماء علوم الحاسوب والرياضيات يحاولون فك هذه الحدسيات . وهذه المسألة هي تخصيص لون لاحد عناصر المخطط بحيث تتحقق مجموعة شروط محددة , لعل ابسط الصيغ هذه المسألة هي تلوين رؤوس المخطط بحيث لا يوجد رأسان متجاوران لهما نفس اللون . وهذا النوع من التلوين يسمى تلوين الرؤوس , وبشكل مشابه نعرف تلوين الاضلاع وهو تلوين الاضلاع بحيث لا يوجد ضلعان يشتركان في رأس لهما نفس اللون , و تلوين الوجوه في مخطط مستو هو تخصيص لون لكل وجه او منطقة بحيث لا يوجد منطقتين تشتركان بنفس الحدود لهما نفس اللون . تلوين الرؤوس عادة هي نقطة الانطلاق ومسائل التلوين الاخرى يمكن تحويلها إلى مسألة تلوين الرؤوس , مثلا تلوين الاضلاع هي تلوين الرؤوس في مخطط خط الملائم لهذا المخطط , و تلوين الوجوه هو تلوين الرؤوس للمخطط الثنائي الملائم . ولكن هذه المسائل تدرس كل واحدة على حدا ولا يُنظر إلى هذه العلاقة لعدة اسباب منها انَّ بعض هذه المسائل يُفضل ان تدرس كما هي لبساطة التعاطي معها كما هي . في الاصل استخدام مصطلح الالوان كان لاجل تلوين الخارطة , ولكن في علم الحاسوب والرياضيات بشكل عام يستخدم الاعداد الصحيحة للدلالة على الالوان . مسألة التلوين هي حالة خاصة من مسألة وسم المخطط . مسألة تلوين المخطط مسألة لها كثير من التطبيقات العملية وتمتد على كل علم الحاسوب , يمكن اضافة شروط على المخطط وايضا على الالوان , ولعل اكثر نسخة من هذه المسألة شيوعا بين الناس هي لعبة السودوكو .