شرح نظرية الألوان الأربعة
في عام 1852 لاحظ رياضي شاب كان يلوّن خريطة لمقاطعات إنجلترا أن أربعة ألوان تبدو كافية للتمييز بين المقاطعات المتجاورة. فهل يصح ذلك على كل خريطة ممكنة؟ أصبح هذا السؤال من أشهر المسائل في الرياضيات، وجذب برهانًا خاطئًا شهيرًا صمد أحد عشر عامًا، وحُسم أخيرًا عام 1976 بطريقة غيّرت ما يقبله الرياضيون برهانًا.
السؤال
سأل فرانسيس غوثري، وهو طالب سابق لدى أوغسطس دي مورغان، عمّا إذا كان يمكن تلوين أي خريطة بأربعة ألوان بحيث تحصل الدول ذات الحدود المشتركة على ألوان مختلفة. هناك قاعدتان تجعلان السؤال دقيقًا. يجب أن تكون الدول متصلة، كل منها قطعة واحدة، والدول التي لا تلتقي إلا عند نقطة واحدة لا تُعد متجاورة. من الواضح أن ثلاثة ألوان لا تكفي دائمًا، إذ إن دولة تحيط بها حلقة من ثلاث دول أخرى متلامسة جميعها تحتاج إلى لون رابع. والسؤال هو: هل يُحتاج يومًا إلى لون خامس؟
الخرائط بوصفها مخططات
ضع علامة على نقطة في كل دولة، وارسم خطًا بين نقطتين كلما تشاركت دولتاهما حدًا. والنتيجة مخطط، ولأن الخريطة تقع على ورقة مسطحة، يمكن رسم الخطوط دون أن تتقاطع: فالمخطط مستوٍ. وتلوين الخريطة هو تلوين رؤوس هذا المخطط بحيث يختلف لونا طرفي كل ضلع. وأصغر عدد من الألوان ينجح في ذلك هو العدد اللوني، وتنص نظرية الألوان الأربعة على أنه لا يوجد مخطط مستوٍ عدده اللوني أكبر من أربعة.
برهان كيمبي الذي أخفق
في عام 1879 نشر المحامي والرياضي ألفريد كيمبي برهانًا. وفكرته البارعة، التي تُسمى اليوم سلاسل كيمبي، هي مبادلة لونين على طول سلسلة متصلة من الدول لتحرير لون حيث تكون الحاجة إليه. ظل البرهان مقبولًا أحد عشر عامًا، حتى وجد بيرسي هيوود فيه ثغرة عام 1890. وقد أثبت إصلاح هيوود نتيجة أضعف: خمسة ألوان تكفي دائمًا. أما سلاسل كيمبي فبقيت، وصارت أداة في البرهان الذي جاء في النهاية.
لماذا تسهل خمسة ألوان
في كل مخطط مستوٍ رأس له خمسة جيران على الأكثر؛ وهذا ينتج عن صيغة أويلر، التي تقيّد عدد أضلاع المخطط المستوي ذي n من الرؤوس بما لا يزيد على 3n − 6. أزل رأسًا كهذا، ولوّن بقية الخريطة بالحجة نفسها، ثم أعد الرأس. إذا كان جيرانه يستخدمون أقل من خمسة ألوان، فهناك لون متاح. وإذا استخدموا الخمسة كلها، فإن مبادلة على سلسلة كيمبي تحرر لونًا دائمًا. أما مع أربعة ألوان فقد تخفق المبادلة نفسها، وهذه بالضبط الثغرة التي فاتت كيمبي.
البرهان الحاسوبي
في عام 1976 برهن كينيث أبل وفولفغانغ هاكن في جامعة إلينوي النظرية. فقد بيّنا أن كل خريطة تحتوي على واحدة على الأقل من 1936 تشكيلة تنتمي إلى مجموعة لا مفر منها، وأن كل تشكيلة قابلة للاختزال: أي إن أصغر خريطة تحتاج إلى خمسة ألوان لا يمكن أن تحتويها. واستغرق التحقق من قابلية الاختزال أكثر من ألف ساعة على الحواسيب، وهو قدر يفوق كثيرًا ما يمكن التحقق منه يدويًا. وشعر كثير من الرياضيين بعدم الارتياح تجاه برهان لا يستطيع أي إنسان قراءته كاملًا، فبدأ الجدل حول البراهين بمساعدة الحاسوب.
براهين أبسط وتحقق كامل
في عام 1996 نشر نيل روبرتسون ودانيال ساندرز وبول سيمور وروبن توماس برهانًا أكثر منهجية يضم 633 تشكيلة، لا يزال يُفحص بالحاسوب لكنه أسهل في التحقق. وفي عام 2005 صاغ جورج غونتييه وبنجامين فيرنر البرهان كله صياغة صورية في مساعد البراهين Coq، بحيث يفحص برنامج صغير موثوق كل خطوة منطقية. واليوم تُعد نظرية الألوان الأربعة من أكثر النتائج في الرياضيات خضوعًا للتحقق الدقيق.
خوارزميات التلوين
إيجاد تلوين بأربعة ألوان لخريطة معينة سريع عمليًا، لكن إيجاد أقل عدد من الألوان لمخطط عام صعب: فتحديد ما إذا كانت ثلاثة ألوان تكفي مسألة NP-كاملة. ومن الطرق العملية التلوين الجشع بترتيب تنازلي للدرجة، وDSATUR الذي يلوّن الرأس الأكثر تقييدًا في الخطوة التالية، والبحث بالتراجع الذي يستكشف الاختيارات ويلغيها عندما يعلق. ويُستخدم تلوين المخططات في جدولة الامتحانات دون تعارض، وتخصيص الترددات اللاسلكية كي لا تتداخل أجهزة الإرسال المتجاورة، وتوزيع السجلات في المترجمات البرمجية.
استكشفها بنفسك
افتح مُلوِّن خرائط الألوان الأربعة لتولّد خرائط من 4 إلى 120 دولة، ولوّنها بيدك بأربعة ألوان، وشاهد التعارضات تظهر باللون الأحمر. دع التلوين الجشع أو DSATUR أو التراجع يحل الخريطة خطوة خطوة، واعرض مخطط الدول المتجاورة، وتحقق من أقل عدد من الألوان تحتاج إليه الخريطة فعلًا.
الأسئلة المتداولة
هل تساعد النظرية صانعي الخرائط؟
بالكاد. فالخرائط الحقيقية تُلوَّن عادةً بألوان أكثر من أجل الوضوح، وتضم محيطات وبحيرات ودولًا من عدة قطع، وهي أمور لا تشملها النظرية. وأهميتها رياضية: فقد دفعت تطور نظرية المخططات وأثارت سؤال ما الذي يُعد برهانًا.
ما سلسلة كيمبي؟
خذ لونين، وليكونا الأحمر والأزرق، ودولة ملونة بالأحمر. سلسلة كيمبي الخاصة بها هي مجموعة كل الدول الحمراء والزرقاء التي يمكن الوصول إليها منها بالانتقال عبر الجيران الحمر والزرق فقط. ومبادلة الأحمر والأزرق في السلسلة كلها تُبقي التلوين صحيحًا، ويمكن أن تحرر لونًا لدولة مجاورة للسلسلة.
لماذا تُبطل الدول المؤلفة من عدة قطع النظرية؟
إذا جاز أن تتألف الدولة من مناطق منفصلة يجب أن تحمل جميعها اللون نفسه، فإن مخطط الجيران لا يعود مستويًا، ويمكن بناء خرائط تحتاج إلى أي عدد من الألوان حتى 12 عندما تتألف كل دولة من قطعتين، كما درس هيوود في «مسألة الإمبراطورية».
لماذا يصنع المُلوِّن الخرائط من نقاط؟
كل دولة هي منطقة المربع الأقرب إلى نقطة عشوائية واحدة منها إلى أي نقطة أخرى، أي مخطط فورونوي. وهذا يعطي خرائط واقعية المظهر لدول محدّبة، وتكون دولتان متجاورتين تمامًا عندما تتشارك منطقتاهما امتدادًا من الحدود، وهو ما يحسبه التطبيق بدقة.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
افتح مُلوِّن خرائط الألوان الأربعة