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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
مسألة NP كاملة
زمرة كبرى
مسار هاملتونياني
عدل

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

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

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

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

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

تاريخ[عدل]

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

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

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

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

تعريف[عدل]

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

خصائص[عدل]

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

التلوين بثلاثة ألوان[عدل]

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

Nuvola apps edu mathematics-ar.svg هذه بذرة مقالة عن الرياضيات بحاجة للتوسيع. شارك في تحريرها.