مشكلة تلوين المخطط

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

تعريف[عدل]

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

خصائص[عدل]

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

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

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

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