طرق خوارزمية للهياكل المنفصلة المنتهية. نظرية الألوان الأربعة. نظرية، طرق، خوارزميات

تُعتبر مشكلة الألوان الأربعة مرتبطة ارتباطًا وثيقًا بفروع أخرى من الرياضيات وتطبيقاتها العملية. من المعروف أكثر من 20 من إعادة صياغتها، والتي تربط هذه المشكلة بمشاكل الجبر والميكانيكا الإحصائية والتخطيط. وهذا أيضًا نموذجي للرياضيات: الحل لمشكلة تمت دراستها بدافع الفضول البحت يتضح أنه مفيد في تمثيل الكائنات والعمليات الحقيقية التي تختلف تمامًا في طبيعتها. على الرغم من الأساليب الآلية المنشورة لإثبات التوافقي لمقترح الألوان الأربعة، لا يزال هناك عدم وجود وصف واضح لآلية تلوين رسم بياني مخطط بأربعة ألوان، وجوهره الطبيعي وارتباطه بظاهرة مسطحية الرسم البياني. من الضروري ليس فقط إثبات (من المفضل استخدام الطرق الاستنتاجية) أن أي رسم بياني مخطط يمكن تلوينه بأربعة ألوان، ولكن أيضًا توضيح كيفية تلوينه. تبحث الورقة في نهج يعتمد على إمكانية تقليل رسم بياني مسطح أقصى إلى رسم بياني مكعب مستوي منتظم مع تلوينه لاحقًا. بناءً على نظرية تايت-فولينسكي، يمكن تلوين رؤوس الرسم البياني المسطح الأقصى بأربعة ألوان، إذا كان يمكن تلوين حواف الرسم البياني المكعب المزدوج له بثلاثة ألوان. من خلال النظر في خصائص الرسم البياني المكعب الملون، يمكن إظهار أن إضافة الألوان تتبع قوانين التحويل لمجموعة كلاين من الدرجة الرابعة. باستخدام هذه الخاصية، من الممكن إنشاء خوارزميات لتلوين الرسوم البيانية الممسوحة.