أربعة ألوان لأي خريطة، تُوجد في زمن خطي

يمكن تلوين أي خريطة مرسومة على ورقة مستوية بأربعة ألوان بحيث لا يشترك بلدان متجاوران في لون واحد أبدًا. طرح Francis Guthrie هذه الحدسية عام 1852؛ وأثبتها Appel وHaken عام 1976. لكن المبرهنة لا تقول سوى إن الألوان الأربعة موجودة. فكيف نجدها لخريطة بعينها؟ «لا توجد إجابة سهلة»، يكتب Yuta Inoue، من جامعة طوكيو، وخمسة من زملائه من اليابان وكندا وسلوفينيا والدنمارك. وقد كانت المسألة متشابكة إلى حدّ أنها أدّت إلى كثير من الأمثلة المضادة المقترحة.

نقاط وخطوط ومثلثات

يصبح كل بلد نقطة، أو رأسًا، وكل حدّ مشترك خطًا، أو ضلعًا: فتتحوّل الخريطة إلى مخطّط مستوٍ (planar graph)، يُرسم من دون خطوط متقاطعة. وتلوينه يعني إعطاء كل رأس واحدًا من أربعة ألوان، مختلفًا عند طرفي كل ضلع. لنسمِّ عدد الرؤوس n. ويكفي التعامل مع التثليثات، حيث كل وجه مثلث: فمزيد من الأضلاع لا يزيد التلوين إلا صعوبة.

مبادلة كمبه

تعود الحركة الأساسية إلى بحث نشره A. B. Kempe عام 1879. زاوِج بين الألوان الأربعة، ولنقل الأحمر مع الأزرق والأخضر مع الأصفر. سلسلة كمبه (Kempe chain) مجموعة متصلة من الرؤوس تحمل لوني زوج واحد. ومبادلة هذين اللونين على طول سلسلة كاملة تُبقي التلوين صحيحًا.

خذ رأسًا v له أربعة جيران، من v0 إلى v3 بالترتيب حوله، ولوّن الباقي أولًا. إذا استخدم الجيران ثلاثة ألوان أو أقل، أخذ v اللون الشاغر. وإذا استخدموا الألوان الأربعة كلها، فاتبع السلسلة التي تبدأ من v0 بلوني v0 وv2. فإن لم تصل إلى v2، فبادِل فيها: يأخذ v0 لون v2، فيتحرّر لون من أجل v. وإن وصلت إلى v2، فبادِل بدلًا من ذلك في سلسلة v1 بلوني v1 وv3، بحيث يأخذ v1 لون v3.

قطع يمكن إصلاحها دائمًا

تقوم براهين المبرهنة على التشكيلات القابلة للاختزال (reducible configurations): أنماط صغيرة يمكن اقتطاعها، ثم إعادتها بعد تلوين الباقي. فإن لم تتلاءم ألوان حلقتها — الرؤوس المحيطة بها مباشرة — فإن عددًا محدودًا من تغييرات كمبه المحسِّنة التي تُجرى خارجها يصلحها دائمًا: 25 على الأكثر للأنماط المستخدمة هنا، التي لا تضمّ حلقاتها أكثر من 18 رأسًا.

تشكيل قابل للاختزال (يسارًا؛ يدلّ كل رقم على عدد الجيران الذي يجب أن يكون لذلك الرأس في الخريطة الكاملة)، والنمط نفسه مكمَّلًا بحلقته R (يمينًا). — الشكل 1، Inoue وآخرون (2026)، arXiv:2610.39753.

بيّن Robertson وSanders وSeymour وThomas عام 1997 كيف يُلوَّن بهذه الطريقة، نمطًا واحدًا في كل مرة. وكل جولة تقلّص المخطّط ببضعة رؤوس وتكلّف مرورًا عليه كله، فيكون الزمن تربيعيًا: أطول بأربع مرات لخريطة أكبر بمرتين.

وفي بحث سابق (FOCS’26)، أثبت المؤلفون الستة أنفسهم أن كل تثليث يحوي عددًا من التشكيلات القابلة للاختزال غير المتلامسة يتناسب مع n، مأخوذة من قائمة تضمّ 8,202 نمطًا، أو عددًا مماثلًا من الحلقات القصيرة التي لها رؤوس على جانبيها، وهي مفيدة أيضًا. فيزيلون الأنماط كلها دفعة واحدة، ويلوّنون الباقي، ثم يصلحون الحلقات جميعها معًا. ويساعد تغيير كمبه عشوائي حلقةً ما إذا اختار المزاوجة الصحيحة بين الألوان (فرصة واحدة من ثلاث) ورمية العملة الصحيحة على كل سلسلة تلامس الحلقة (فرصة واحدة من اثنتين لكل منها). ومع ما يصل إلى 18 سلسلة كهذه، تكون الفرصة واحدة على الأقل من 3 × 2¹⁸، أي 786,432: صغيرة، لكنها ثابتة. ولذا لا يزداد عدد الجولات إلا بقدر log n، أي تقريبًا عدد المرات التي يمكن فيها قسمة n على اثنين. لكن تغييرًا واحدًا قد يشمل جزءًا ثابتًا من المخطّط: فكل تغيير يكلّف مرورًا كاملًا، أي n log n في المجموع.

جدول بدلًا من مرور كامل

يحتفظ البحث الجديد بتغييرات log n لكنه يجعل كل واحد منها أرخص. فبعد تحضير يستغرق زمنًا يتناسب مع n، يُعثر على كل تغيير ويُنفَّذ في نحو n / log n خطوة في المتوسط. فتستغرق تغييرات log n معًا زمنًا يتناسب مع n — أي زمنًا خطيًا — وهو حدّ يصفه المؤلفون بأنه أمثل.

والحيلة هي «طريقة الروس الأربعة» (Method of Four Russians). فمسألة فرعية تتّسع في رمز من ½ log n بت — أي نصف عدد الأرقام الثنائية اللازمة لكتابة n — لها √n نسخة ممكنة على الأكثر، لذا يمكن حساب جميع إجاباتها مسبقًا وتخزينها في جدول. والحاسوب المفترض، بكلمات ذاكرة طولها نحو log n بت، يقرأ أي إجابة مخزّنة في خطوة واحدة.

يُقطَّع المخطّط، مرة بعد مرة، إلى مناطق متداخلة ذات حدود قصيرة. وأصغرها تضمّ نحو log n رأسًا وتتّسع، بألوانها، في رمز واحد. ولكل منطقة، يسجّل مخطّط موجز صغير أيّ رؤوس الحدود تتشارك سلسلة كمبه. وعندئذ ينزل التغيير على هيئة سلاسل من بتات «بادِل» أو «أبقِ»، وفي كل منطقة صغيرة، تُحدِّث عملية بحث واحدة في الجدول جميع الألوان.

جزء من مخطّط ملوَّن بأربعة ألوان. المساحة الرمادية منطقة R؛ والأضلاع السوداء العريضة تنتمي إلى سلاسل كمبه للزوجين أحمر-أزرق وأخضر-أصفر. — الشكل 2، Inoue وآخرون (2026)، arXiv:2610.39753.

موجز المنطقة نفسها: تمثّل كل بقعة زرقاء قطعة من سلسلة كمبه، وتبيّن خطوطها أيّ رؤوس الحدود تصل بينها. — الشكل 3، Inoue وآخرون (2026)، arXiv:2610.39753.

الاختيار من دون نرد

مع الاختيارات العشوائية، تلوّن هذه الطريقة الخريطة أصلًا في زمن خطي في المتوسط. أما إزالة النرد من دون خسارة السرعة فكانت «الجزء الأصعب بفارق كبير». لنقل إن الحلقة حيّة ما دام كل قرار حتى الآن قد جاء في صالحها. فلو تُركت السلاسل u غير المحسومة التي تلامسها لرمي العملة، لنجت باحتمال 1/2^u؛ وبجمع هذه الأعداد على كل الحلقات الحيّة نحصل على العدد المتوقَّع للناجيات. وحسم سلسلة ما يضاعف حدّ كل حلقة أرادت ذلك الاختيار ويُصفِّر حدود الأخرى. وتأخذ الخوارزمية الخيار الذي يمنع المجموع من الانخفاض، بحيث تُساعَد في النهاية حلقات بعدد لا يقلّ عمّا كانت المصادفة ستساعده في المتوسط.

حدّ نظري، لا ساعة توقيت

لا يقدّم البحث أي تنفيذ برمجي ولا أي زمن تشغيل، ولا يذكر الثوابت المخفية في عبارة «يتناسب مع n». وهي كبيرة: فلكل نمط من الأنماط الـ8,202، تخزّن الخوارزمية عدد التغييرات المحسِّنة التي يحتاجها كل تلوين لحلقته، أي «كمية ثابتة هائلة من المعلومات». وفي ملحق، يصحّحون أيضًا «خطأً طفيفًا» في بناءٍ للمناطق المتداخلة يعود إلى عام 2013 ويستندون إليه. وهكذا باتت حدسية من عام 1852 مصحوبة بإجراء تلوين لا تنمو كلفته أسرع من الخريطة التي يلوّنها.