مشكلة تلوين المخطط
| مسألة NP كاملة |
|---|
| زمرة كبرى |
| مسار هاملتونياني |
| عدل |
تعريف
في مخطط عادي نريد تلوين كل رأس بلون، حيث لا نلون رأسين متجاورين بنفس اللون. المشكلة هي كيف نحدد أقل عدد ممكن من الألوان؟
خصائص
تحديد أقل عدد ممكن من الألوان يسمى عدد التلوين. وتحديد هذا العدد من المشاكل الكاملة, وهذا المشكل له علاقة قريبة جدا من مشكلة المخطط الكامل ضمن مخطط ومشكلة المخطط المستقر ضمن مخطط.
التلوين بثلاثة ألوان
تلوين مخطط ما باستعمال ثلاثة ألوان فقط، هو أيضا مشكل كامل حيث يمكن اختصار أي مشكل من صنف المشاكل غير المحددة لمشكل التلوين بثلاثة ألوان.
| ملف:Nuvola apps edu mathematics-ar.svg | هذه بذرة مقالة عن الرياضيات تحتاج للنمو والتحسين، فساهم في إثرائها بالمشاركة في تحريرها. |
| ملف:Nuvola apps edu mathematics-ar.svg | بوابة رياضيات تصفح مقالات ويكيبيديا المهتمة بالرياضيات. |
cs:Barvení grafu de:Färbung (Graphentheorie) el:Χρωματισμός γραφήματος Graph coloring]] es:Coloración de grafos eu:Grafo koloreztaketa fa:رنگآمیزی گراف fr:Coloration de graphe he:גרף n-צביע hu:Gráfok színezése ja:グラフ彩色 ko:그래프 색칠 문제 lt:Grafo spalvinimas pl:Kolorowanie grafu pt:Coloração de grafos ru:Хроматическое число sv:Graffärgning th:ปัญหาการระบายสีกราฟ uk:Хроматичне число vi:Tô màu đồ thị zh:图着色问题
