تلوين المخططات
يُخصّص تلوين المخططات تسميات، أو ألوانًا، لعناصر المخطط بحيث تختلف العناصر المتجاورة، ويدرس الحد الأدنى لعدد الألوان المطلوبة.
Definition
التلوين الصحيح للمخطط هو تخصيص ألوان لرؤوسه بحيث لا يشترك رأسان متجاوران في نفس اللون؛ والعدد اللوني هو أقل عدد من الألوان التي يوجد بها مثل هذا التخصيص.
Scope
يتناول هذا الموضوع التلوين الرأسي الصحيح والعدد اللوني، وتلوين الحواف والمؤشر اللوني، ومتعدد الحدود اللوني الذي يحسب التلوينات، والنتائج البارزة بما في ذلك نظرية بروكس، ونظرية فيزينغ، ونظرية الألوان الأربعة للمخططات المستوية. ويربط التلوين بالاستقلالية، والمجموعات المتكاملة، والنظرية الأوسع لمعاملات المخططات.
Core questions
- ما هو أقل عدد من الألوان اللازمة لتلوين مخطط معين بشكل صحيح؟
- كم عدد التلوينات الصحيحة التي يقبلها المخطط باستخدام لوحة ألوان معينة؟
- ما هي المخططات التي يمكن تلوينها بعدد قليل من الألوان، وما هي العوائق التي تتطلب الكثير؟
- كيف يوسع تلوين الحواف وتلوين القوائم المفهوم الأساسي؟
Key concepts
- التلوين الرأسي الصحيح
- العدد اللوني
- متعدد الحدود اللوني
- تلوين الحواف والمؤشر اللوني
- نظرية بروكس
- نظرية الألوان الأربعة
Key theories
- نظرية الألوان الأربعة
- يمكن تلوين كل مخطط مستوٍ بشكل صحيح بأربعة ألوان على الأكثر، وهي عبارة ظلت مفتوحة لأكثر من قرن وأثبتها لأول مرة أبيل وهاكن عام 1976 باستخدام تحليل حالات مكثف بمساعدة الحاسوب.
- نظرية فيزينغ
- يمكن تلوين حواف أي مخطط بسيط بشكل صحيح إما بالدرجة القصوى أو بدرجة واحدة أكثر من الدرجة القصوى من الألوان، مما يقسم جميع المخططات إلى فئتين ضيقتين.
Clinical relevance
تُنمذج مشكلات التلوين تخصيص الموارد الخالي من التعارضات: فجدولة المواعيد دون تصادمات، وتخصيص السجلات في المترجمات البرمجية، وتخصيص الترددات في الشبكات اللاسلكية، ومشكلات القيود على غرار لعبة سودوكو، كلها تختزل إلى تلوين المخططات.
History
دفعت فرضية الألوان الأربعة، التي طُرحت عام 1852، الكثير من نظرية التلوين؛ وكان إثباتها بمساعدة الحاسوب عام 1976 بواسطة أبيل وهاكن علامة فارقة مبكرة في الرياضيات بمساعدة الحاسوب وأثارت جدلاً حول طبيعة الإثبات.
Debates
- وضع البراهين بمساعدة الحاسوب
- أثار اعتماد نظرية الألوان الأربعة على الحالات التي تم التحقق منها آليًا تساؤلاً حول ما إذا كان البرهان الطويل جدًا بحيث لا يمكن للإنسان التحقق منه يدويًا يجب أن يُعتبر برهانًا رياضيًا حقيقيًا.
Key figures
- Kenneth Appel
- Wolfgang Haken
- Vadim Vizing
Related topics
Seminal works
- diestel2017
Frequently asked questions
- ما هو العدد اللوني للمخطط؟
- هو أصغر عدد من الألوان اللازمة بحيث تتلقى الرؤوس المتجاورة دائمًا ألوانًا مختلفة؛ على سبيل المثال، الدورة الفردية لها عدد لوني ثلاثة.
- هل تنطبق نظرية الألوان الأربعة على جميع الخرائط؟
- تنطبق على الخرائط المرسومة على المستوى أو الكرة حيث تكون المناطق متصلة؛ وقد تتطلب الخرائط على أسطح مثل الطارة (torus) المزيد من الألوان.