المحتوى هنا ينقصه الاستشهاد بمصادر، أي معلومات غير موثقة يمكن التشكيك بها وإزالتها.

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

من ويكيبيديا، الموسوعة الحرة
(بالتحويل من مشكلة تلوين المخطط)
اذهب إلى: تصفح، ‏ ابحث
Question book-new.svg
المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (مارس 2016)
مسألة NP كاملة
زمرة كبرى
مسار هاملتونياني
عدل

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

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

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

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

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

تاريخ[عدل]

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

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

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

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

خصائص[عدل]

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

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

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

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

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

الاختصار[عدل]

gadjet 3COL

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

  1. لكل متغيرين متقابلين و نرسم قمتين مرتبطتين، خاصة ب و خاصة ب .
  2. لكل رمز (أول رمز)، نرسم مثلث قممه و و. وتسمى A رأس المثلث.
    1. في حالة وجود نربط القمة بB. أما في حالة وجود نربط القمة بB.
    2. بالنسبة للمتغير الثاني في الصيغة clause يتم ربط القمة التي تمثله بِC بنفس طريقة الربط مع B.
  3. لكل رمز موالي(انطلاقا من ثاني رمز)، نرسم مثلث قممه و و. نربط ب . و بتمثيل المتغير الثالث.
  4. المثلث الأخير والذي يرمز لآخر رمز في الصيغة clause نسمي رأسه برأس العبارة.
  5. في الأخير نضيف قمتين مرتبطتين الأولى محايدة والثانية منعدمة :
    1. القمة مرتبطة برؤوس المثلثات وبالقمم التي تمثل المتغيرات.
    2. القمة مرتبطة برؤوس العبارات.

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

المراجع[عدل]