مشكلة تلوين المخطط
من ويكيبيديا، الموسوعة الحرة
| مسألة NP كاملة |
|---|
| زمرة كبرى |
| مسار هاملتونياني |
| عدل |
[تحرير] تعريف
في مخطط عادي نريد تلوين كل رأس بلون، حيث لا نلون رأسين متجاورين بنفس اللون. المشكلة هي كيف نحدد أقل عدد ممكن من الألوان؟
[تحرير] خصائص
تحديد أقل عدد ممكن من الألوان يسمى عدد التلوين. و تحديد هذا العدد من المشاكل الكاملة, و هذا المشكل له علاقة قريبة جدا من مشكلة المخطط الكامل ضمن مخطط و مشكلة المخطط المستقر ضمن مخطط.
[تحرير] التلوين بثلاثة ألوان
تلوين مخطط ما باستعمال ثلاثة ألوان فقط، هو أيضا مشكل كامل حيث يمكن اختصار أي مشكل من صنف المشاكل غير المحددة لمشكل التلوين بثلاثة ألوان.
