الفرق بين المراجعتين لصفحة: «مشكلة تلوين المخطط»
اذهب إلى التنقل
اذهب إلى البحث
ط (١ مراجعة: الصفحات في تصنيف رياضيات) |
(-) |
||
| سطر 14: | سطر 14: | ||
[[تصنيف:نظرية المخططات]] | [[تصنيف:نظرية المخططات]] | ||
[[تصنيف:مسائل NP كاملة]] | [[تصنيف:مسائل NP كاملة]] | ||
المراجعة الحالية بتاريخ 14:26، 30 أغسطس 2012
تعريف
في مخطط عادي نريد تلوين كل رأس بلون، حيث لا نلون رأسين متجاورين بنفس اللون. المشكلة هي كيف نحدد أقل عدد ممكن من الألوان؟
خصائص
تحديد أقل عدد ممكن من الألوان يسمى عدد التلوين. وتحديد هذا العدد من المشاكل الكاملة, وهذا المشكل له علاقة قريبة جدا من مشكلة المخطط الكامل ضمن مخطط ومشكلة المخطط المستقر ضمن مخطط.
التلوين بثلاثة ألوان
تلوين مخطط ما باستعمال ثلاثة ألوان فقط، هو أيضا مشكل كامل حيث يمكن اختصار أي مشكل من صنف المشاكل غير المحددة لمشكل التلوين بثلاثة ألوان.
