قائمة المصطلحات

حدد واحدة من الكلمات الرئيسية على اليسار ...

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

وقت القراءة: ~15 min

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

عند تلوين خريطة الولايات الأمريكية ، من الواضح أن 50 لونًا كافية ، ولكن أقل بكثير ضرورية. حاول تلوين الخرائط أدناه بأقل عدد ممكن من الألوان:

الولايات المتحدة الأمريكية

عدد الألوان: 0

امريكا الجنوبية

عدد الألوان: 0

ألمانيا

عدد الألوان: 0

إنكلترا

عدد الألوان: 0

يمكن تلوين كل هذه الخرائط بأربعة ألوان مختلفة فقط ، ولكن ليس من الصعب تخيل تلك الخرائط الأخرى المعقدة جدًا قد تحتاج إلى المزيد من الألوان. في الواقع ، تحتاج بعض الخرائط إلى على الأقل من أربعة ألوان ، كلما كانت تحتوي على أربعة بلدان متصلة ببعضها البعض.

كما كان من قبل ، يمكننا تحويل خريطة مع البلدان والحدود إلى رسم بياني مستوي: يصبح كل بلد ، والبلدان التي تواصل بحافة:

الآن نريد تلوين رؤوس الرسم البياني ، ويجب أن يكون لقمتين لون مختلف إذا كانا متصلين بحافة.

في عام 1852 ، كان على طالب علم النبات فرانسيس جوثري تلوين خريطة للمقاطعات في إنجلترا. ولاحظ أن أربعة ألوان تبدو كافية لأي خريطة حاولها ، لكنه لم يتمكن من العثور على دليل يعمل على جميع الخرائط. اتضح أن هذه مشكلة صعبة للغاية ، وأصبحت تعرف باسم نظرية الألوان الأربعة. خلال المائة عام التالية ، نشر العديد من علماء الرياضيات "برهان" على نظرية الألوان الأربعة ، فقط للكشف عن الأخطاء لاحقًا. كانت بعض هذه البراهين غير الصالحة مقنعة للغاية بحيث استغرق اكتشاف الأخطاء أكثر من 10 سنوات. لفترة طويلة ، لم يتمكن علماء الرياضيات من إثبات أن أربعة ألوان كافية ، أو العثور على خريطة تحتاج إلى أكثر من أربعة ألوان.

تم إحراز تقدم بسيط في مشكلة الألوان الأربعة حتى عام 1976 ، عندما استخدم فولفجانج هاكين و كينيث أبيل جهاز كمبيوتر لحلها أخيرًا. قاموا بتخفيض عدد لا حصر له من الخرائط الممكنة إلى 1936 حالة خاصة ، تم فحص كل منها بواسطة كمبيوتر استغرق أكثر من 1000 ساعة في المجموع.

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

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

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

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

تتطالب هذه الخريطة على الحيد سبعة الوان.