تويت
تم تغطية عدد قليل من النظريات الرياضية و نشرها على الجمهور السائد. في بعض الأحيان، لأن الرياضيات مملة للأشخاص العاقلين، و لكن يرجع ذلك أساسًا إلى أن العديد من هذه النظريات معقدة بشكل وحشي و يصعب فهمها بلا داعٍ. نادرًا ما توجد النقطة اللطيفة بين البساطة والأهمية في الكتاب المدرسي العام لمسائل الرياضيات التي لم يتم حلها؛ و مع ذلك، فإن موضوع هذه القطعة أي نظرية الألوان الأربعة، هو أحد الاستثناءات القليلة النادرة التي تحقق هذا التوازن إلى حد كبير.
تنص نظرية الألوان الأربعة، أو نظرية خريطة الألوان الأربعة، في أبسط أشكالها، على أنه لا يلزم وجود أكثر من أربعة ألوان لتلوين مناطق أي خريطة بحيث لا توجد منطقتان متجاورتان لهما نفس اللون. كما وعدت، هذه نظرية يمكن لأي طالب في المرحلة الابتدائية فهمها. ينص الشكل الثاني، و هو شكل رياضي أكثر من النظرية، على ما يلي:
بالنظر إلى أي فصل من المستوى إلى مناطق متجاورة ينتج عنه شكل يسمى خريطة، لا يلزم وجود أكثر من أربعة ألوان لتلوين مناطق الخريطة بحيث لا يكون هناك منطقتان متجاورتان لهما نفس اللون. أكثر تعقيدًا بعض الشيء، لكن يمكن فهمه بثقة في المستوى الجامعي. الطريقة الثالثة والأخيرة لتوضيح النظرية، و هي عملية أكثر بكثير و لكنها أكثر تعقيدًا بشكل كبير، تتطلب لغة نظرية الرسم البياني. في لغة الرسم البياني النظرية، تدعي نظرية الألوان الأربعة أن رؤوس كل رسم بياني مستو يمكن تلوينها بأربعة ألوان على الأكثر دون تلقي رأسين متجاورين نفس اللون، أو بعبارة أخرى: كل رسم بياني مستوٍ أربعة ألوان قابلة للتلوين.
لا تقلق إذا كان هذا الوصف الأخير قد طار على رأسك، فالمقصود هو تقديمه ببساطة و معاينة الارتباط بنظرية الرسم البياني – سنأخذ الوقت الكافي لتحديده و هضمه لاحقًا.
مثال على خريطة بأربعة ألوان
بالإضافة إلى بساطتها الجذابة، تشتهر نظرية الألوان الأربعة بنقطة انعطافها في تاريخ الرياضيات:
كانت أول نظرية رئيسية “تم إثباتها” من خلال سيناريوهات التأثير الغاشم مع الكمبيوتر. في عصرنا الحالي، يعد هذا إنجازًا مهمًا تاريخيًا إلى حد ما.
كما سنرى قريبًا، على الرغم من الإدخال الهائل للنظريات منذ عام 1852، فإن نظرية الألوان الأربعة قاومت تمامًا أي محاولات للتخمين العام لعقود. و حتى عندما ظهر تخمين محتمل في عام 1976، رفضت نظرية الألوان الأربعة الخضوع لأي خريطة عامة. و هو ما أجبر بدوره أحدث الوافدين على اللجوء إلى طريقة الإثبات المشكوك فيها (حساب جميع السيناريوهات). أثارت الآثار المترتبة على قبول هذه الطريقة كدليل عام أسئلة حول معنى إثبات النظرية. في الواقع، بفضل نظرية الألوان الأربعة، لا يزال الناس يناقشون دور أجهزة الكمبيوتر في البرهان الرياضي و مستقبل الرياضيات كمسعى بشري.
قبل المتابعة، توقف مؤقتًا الآن وخذ لحظة لتخيل خريطة معقدة تعتقد أنها تتطلب أكثر من أربعة ألوان. انطلق وارسمها بسرعة – ثم حاول تلوينها (أو املأها بالأعداد الصحيحة 1-4). أنا شخصياً، لم أجد بعد شخصًا يؤمن بهذه النظرية بشكل حدسي من النظرة الأولى؛ يبدو أنها مجرد خطأ. و مع ذلك، طوال تاريخها، لم يتم اكتشاف مثال مضاد واحد. سنستعرض في النهاية منطق التخمين الأخير المقبول، و مع ذلك، لإرضاء فضولنا لفهم أعمق، سنبدأ أولاً من أصل المشكلة.
التلوين الرباعي لخريطة الولايات الأمريكية (تجاهل البحيرات)
تاريخ نظرية الألوان الأربعة
محاولات إثبات مبكرة
الصورة: رسالة دي مورغان إلى هاميلتون ، ٢٣ أكتوبر ١٨٥٢
بقدر ما هو معروف، تم اقتراح التخمين لأول مرة في 23 أكتوبر 1852، عندما لاحظ فرانسيس جوثري، أثناء محاولته تلوين خريطة مقاطعات إنجلترا، أن هناك حاجة إلى أربعة ألوان مختلفة فقط. في ذلك الوقت، كان شقيق جوثري، فريدريك، طالبًا في جامعة أوغسطس دي مورغان (المستشار السابق لفرانسيس) في كلية لندن الجامعية. استفسر فرانسيس من فريدريك عن ذلك، فأخذه بعد ذلك إلى دي مورغان (تخرج فرانسيس جوثري لاحقًا في عام 1852، و أصبح فيما بعد أستاذًا للرياضيات في جنوب إفريقيا). بالنسبة الى دي مورغان:
” طلب مني أحد طلابي [غوثري] اليوم أن أقدم له سببًا لحقيقة لم أكن أعرف أنها حقيقة – و لا أعرفها بعد. يقول إنه إذا كان الشكل مقسمًا و كانت المقصورات ملونة بشكل مختلف بحيث تكون الأشكال التي بها أي جزء من خط الحدود المشتركة ملونة بشكل مختلف – أربعة ألوان قد تكون مطلوبة و لكن ليس أكثر – فإن التالي هو حالته التي يلزم فيها أربعة ألوان. لا يمكن اختراع الاستعلام ضروريًا لخمسة أشخاص أو أكثر … “ (ويلسون 2014 ، ص 18)
ربما نشر أحدهما السؤال في The Athenaeum (The Athenæum كانت مجلة أدبية بريطانية نُشرت في لندن، إنجلترا)في عام 1854، و طرح دي مورغان السؤال مرة أخرى في نفس المجلة في عام 1860. مرجع آخر نشر مبكرًا بواسطة آرثر كايلي (1879) ينسب بدوره التخمين إلى دي مورغان.
كانت هناك عدة محاولات فاشلة مبكرة لإثبات النظرية. اعتقد دي مورغان أن هذا ناتج عن حقيقة بسيطة تتعلق بأربع مناطق، على الرغم من أنه لا يعتقد أن هذه الحقيقة يمكن اشتقاقها من المزيد من الحقائق الأولية.
تنص نظرية الألوان الأربعة، أو نظرية خريطة الألوان الأربعة، في أبسط أشكالها، على أنه لا يلزم وجود أكثر من أربعة ألوان لتلوين مناطق أي خريطة بحيث لا توجد منطقتان متجاورتان لهما نفس اللون. كما وعدت، هذه نظرية يمكن لأي طالب في المرحلة الابتدائية فهمها. ينص الشكل الثاني، و هو شكل رياضي أكثر من النظرية، على ما يلي:
بالنظر إلى أي فصل من المستوى إلى مناطق متجاورة ينتج عنه شكل يسمى خريطة، لا يلزم وجود أكثر من أربعة ألوان لتلوين مناطق الخريطة بحيث لا يكون هناك منطقتان متجاورتان لهما نفس اللون. أكثر تعقيدًا بعض الشيء، لكن يمكن فهمه بثقة في المستوى الجامعي. الطريقة الثالثة والأخيرة لتوضيح النظرية، و هي عملية أكثر بكثير و لكنها أكثر تعقيدًا بشكل كبير، تتطلب لغة نظرية الرسم البياني. في لغة الرسم البياني النظرية، تدعي نظرية الألوان الأربعة أن رؤوس كل رسم بياني مستو يمكن تلوينها بأربعة ألوان على الأكثر دون تلقي رأسين متجاورين نفس اللون، أو بعبارة أخرى: كل رسم بياني مستوٍ أربعة ألوان قابلة للتلوين.
لا تقلق إذا كان هذا الوصف الأخير قد طار على رأسك، فالمقصود هو تقديمه ببساطة و معاينة الارتباط بنظرية الرسم البياني – سنأخذ الوقت الكافي لتحديده و هضمه لاحقًا.
مثال على خريطة بأربعة ألوان
بالإضافة إلى بساطتها الجذابة، تشتهر نظرية الألوان الأربعة بنقطة انعطافها في تاريخ الرياضيات:
كانت أول نظرية رئيسية “تم إثباتها” من خلال سيناريوهات التأثير الغاشم مع الكمبيوتر. في عصرنا الحالي، يعد هذا إنجازًا مهمًا تاريخيًا إلى حد ما.
كما سنرى قريبًا، على الرغم من الإدخال الهائل للنظريات منذ عام 1852، فإن نظرية الألوان الأربعة قاومت تمامًا أي محاولات للتخمين العام لعقود. و حتى عندما ظهر تخمين محتمل في عام 1976، رفضت نظرية الألوان الأربعة الخضوع لأي خريطة عامة. و هو ما أجبر بدوره أحدث الوافدين على اللجوء إلى طريقة الإثبات المشكوك فيها (حساب جميع السيناريوهات). أثارت الآثار المترتبة على قبول هذه الطريقة كدليل عام أسئلة حول معنى إثبات النظرية. في الواقع، بفضل نظرية الألوان الأربعة، لا يزال الناس يناقشون دور أجهزة الكمبيوتر في البرهان الرياضي و مستقبل الرياضيات كمسعى بشري.
قبل المتابعة، توقف مؤقتًا الآن وخذ لحظة لتخيل خريطة معقدة تعتقد أنها تتطلب أكثر من أربعة ألوان. انطلق وارسمها بسرعة – ثم حاول تلوينها (أو املأها بالأعداد الصحيحة 1-4). أنا شخصياً، لم أجد بعد شخصًا يؤمن بهذه النظرية بشكل حدسي من النظرة الأولى؛ يبدو أنها مجرد خطأ. و مع ذلك، طوال تاريخها، لم يتم اكتشاف مثال مضاد واحد. سنستعرض في النهاية منطق التخمين الأخير المقبول، و مع ذلك، لإرضاء فضولنا لفهم أعمق، سنبدأ أولاً من أصل المشكلة.
التلوين الرباعي لخريطة الولايات الأمريكية (تجاهل البحيرات)
تاريخ نظرية الألوان الأربعة
محاولات إثبات مبكرة
الصورة: رسالة دي مورغان إلى هاميلتون ، ٢٣ أكتوبر ١٨٥٢
بقدر ما هو معروف، تم اقتراح التخمين لأول مرة في 23 أكتوبر 1852، عندما لاحظ فرانسيس جوثري، أثناء محاولته تلوين خريطة مقاطعات إنجلترا، أن هناك حاجة إلى أربعة ألوان مختلفة فقط. في ذلك الوقت، كان شقيق جوثري، فريدريك، طالبًا في جامعة أوغسطس دي مورغان (المستشار السابق لفرانسيس) في كلية لندن الجامعية. استفسر فرانسيس من فريدريك عن ذلك، فأخذه بعد ذلك إلى دي مورغان (تخرج فرانسيس جوثري لاحقًا في عام 1852، و أصبح فيما بعد أستاذًا للرياضيات في جنوب إفريقيا). بالنسبة الى دي مورغان:
” طلب مني أحد طلابي [غوثري] اليوم أن أقدم له سببًا لحقيقة لم أكن أعرف أنها حقيقة – و لا أعرفها بعد. يقول إنه إذا كان الشكل مقسمًا و كانت المقصورات ملونة بشكل مختلف بحيث تكون الأشكال التي بها أي جزء من خط الحدود المشتركة ملونة بشكل مختلف – أربعة ألوان قد تكون مطلوبة و لكن ليس أكثر – فإن التالي هو حالته التي يلزم فيها أربعة ألوان. لا يمكن اختراع الاستعلام ضروريًا لخمسة أشخاص أو أكثر … “ (ويلسون 2014 ، ص 18)
ربما نشر أحدهما السؤال في The Athenaeum (The Athenæum كانت مجلة أدبية بريطانية نُشرت في لندن، إنجلترا)في عام 1854، و طرح دي مورغان السؤال مرة أخرى في نفس المجلة في عام 1860. مرجع آخر نشر مبكرًا بواسطة آرثر كايلي (1879) ينسب بدوره التخمين إلى دي مورغان.
كانت هناك عدة محاولات فاشلة مبكرة لإثبات النظرية. اعتقد دي مورغان أن هذا ناتج عن حقيقة بسيطة تتعلق بأربع مناطق، على الرغم من أنه لا يعتقد أن هذه الحقيقة يمكن اشتقاقها من المزيد من الحقائق الأولية.
- هذا ينشأ على هذا النحو، أن لا نحتاج أبدًا إلى أربعة ألوان في الحي ما لم يكن هناك أربع مقاطعات، لكل منها خطوط حدية مشتركة مع كل من الثلاثة الأخرى. لا يمكن أن يحدث مثل هذا الشيء في أربع مناطق ما لم يكن واحدًا أو أكثر منها محاطًا بالباقي؛ و بالتالي فإن اللون المستخدم للمقاطعة المغلقة يتم تعيينه مجانًا للاستمرار معه. الآن هذا المبدأ، القائل بأن أربع مناطق لا يمكن أن يكون لكل منها حدود مشتركة مع جميع المجالات الثلاثة الأخرى دون التضمين، ليس كما نعتقد تمامًا، قادرًا على إثبات أي شيء أكثر وضوحًا و أكثر بدائية؛ يجب أن يقف كمسلمة.
تم تقديم دليل واحد مزعوم من قبل ألفريد كيمبي في عام 1879، و الذي لاقى استحسانًا كبيرًا؛ آخر أعطاه بيتر جوثري تايت في عام 1880. لم يكن حتى عام 1890 أن أثبت بيرسي هيوود أن دليل كيمبي غير صحيح، و في عام 1891، أظهر جوليوس بيترسن إثبات غير صحيح، كل دليل كاذب ظل دون منازع لمدة 11 عامًا.
في عام 1890، بالإضافة إلى كشف الخلل في برهان كيمبي، أثبت پيرسى چوهن هياود نظرية الألوان الخمسة و عمم تخمين الألوان الأربعة على أسطح الجنس التعسفي.
أظهر تايت، في عام 1880، أن نظرية الألوان الأربعة تعادل العبارة القائلة بأن نوعًا معينًا من الرسم البياني (يسمى الشخير في المصطلحات الحديثة) يجب أن يكون غير مستوي.
في عام 1943، صاغ هوغو هادويجر تخمين هادويجر، و هو تعميم بعيد المدى لمشكلة الألوان الأربعة التي لا تزال دون حل.
إثبات نظرية الألوان الأربعة بواسطة الكمبيوتر
خلال الستينيات والسبعينيات من القرن الماضي، طور عالم الرياضيات الألماني هاينريش هيش طرقًا لاستخدام أجهزة الكمبيوتر للبحث عن دليل. من الجدير بالذكر أنه كان أول من استخدم التفريغ لإثبات النظرية، و التي تبين أنها مهمة في جزء الحتمية من دليل Appel-Haken اللاحق. كما قام بتوسيع مفهوم الاختزال و قام، جنبًا إلى جنب مع كين دورري، بتطوير اختبار كمبيوتر له. لسوء الحظ، في هذا المنعطف الحرج، لم يكن قادرًا على توفير الوقت اللازم للحاسوب العملاق لمواصلة عمله.
تبنى آخرون أساليبه، بما في ذلك نهجه بمساعدة الكمبيوتر. بينما كانت فرق أخرى من علماء الرياضيات تتسابق لاستكمال البراهين، أعلن كينيث أبيل و ولفجانج هاكين في جامعة إلينوي، في 21 يونيو 1976، أنهم أثبتوا النظرية. ساعدهم في بعض أعمال الخوارزميات جون أ. كوخ.
إذا كان التخمين ذو الألوان الأربعة خاطئًا، فستكون هناك خريطة واحدة على الأقل بها أصغر عدد ممكن من المناطق التي تتطلب خمسة ألوان. أظهر الدليل أن مثل هذا الحد الأدنى من المثال المقابل لا يمكن أن يوجد، من خلال استخدام مفهومين تقنيين:
- المجموعة التي لا يمكن تجنبها هي مجموعة من التكوينات بحيث يجب أن تحتوي كل خريطة تفي ببعض الشروط الضرورية لكونها حد أدنى من التثليث غير 4 اللون (مثل الحصول على درجة 5 كحد أدنى) على تكوين واحد على الأقل من هذه المجموعة.
- التكوين القابل للاختزال هو ترتيب البلدان التي لا يمكن أن تحدث في الحد الأدنى من المثال المقابل.
إذا كانت الخريطة تحتوي على تكوين قابل للاختزال، فيمكن تصغير الخريطة إلى خريطة أصغر. هذه الخريطة الأصغر لها شرط أنه إذا كان من الممكن تلوينها بأربعة ألوان، فإن هذا ينطبق أيضًا على الخريطة الأصلية. هذا يعني أنه إذا كان لا يمكن تلوين الخريطة الأصلية بأربعة ألوان، فلا يمكن للخريطة الأصغر أن تكون كذلك، و بالتالي فإن الخريطة الأصلية ليست بالحد الأدنى. باستخدام القواعد والإجراءات الرياضية المستندة إلى خصائص التكوينات القابلة للاختزال، وجد Appel و Haken مجموعة لا يمكن تجنبها من التكوينات القابلة للاختزال، مما يثبت أنه لا يمكن وجود حد أدنى من الأمثلة المضادة للتخمين ذي الألوان الأربعة.
قلل دليلهم من عدد الخرائط الممكنة اللانهائية إلى 1834 تكوينًا قابلًا للاختزال (تم تخفيضها لاحقًا إلى 1482) والتي كان لا بد من فحصها واحدة تلو الأخرى بواسطة الكمبيوتر و استغرق الأمر أكثر من ألف ساعة. تم فحص جزء الاختزال من العمل بشكل مستقل مرتين مع برامج وأجهزة كمبيوتر مختلفة. و مع ذلك، تم التحقق من الجزء الذي لا مفر منه من الإثبات في أكثر من 400 صفحة من الميكروفيش، و التي كان لا بد من فحصها يدويًا بمساعدة دوروثيا بلوستين ابنة هاكن (Appel & Haken 1989).
تم تغطية إعلان أبيل و هاكن على نطاق واسع من قبل وسائل الإعلام حول العالم، و استخدم قسم الرياضيات في جامعة إلينوي علامة بريدية تنص على “أربعة ألوان كافية”. في الوقت نفسه، أثارت الطبيعة غير العادية للإثبات – كانت أول نظرية رئيسية يتم إثباتها بمساعدة الكمبيوتر المكثفة – وتعقيد الجزء الذي يمكن التحقق منه بشريًا جدلًا كبيرًا (Wilson 2014).
في أوائل الثمانينيات، انتشرت شائعات عن وجود خلل في دليل Appel-Haken. قام Ulrich Schmidt من RWTH Aachen بفحص دليل Appel و Haken على أطروحة الماجستير التي تم نشرها عام 1981 (Wilson 2014، 225). لقد قام بفحص حوالي 40 ٪ من جزء عدم القدرة على تجنبها و وجد خطأً كبيرًا في إجراء التفريغ (Appel & Haken 1989).
في عام 1986، طلب محرر Mathematical Intelligencer من Appel و Haken كتابة مقال يتناول شائعات وجود عيوب في إثباتهم. أجابوا بأن الشائعات كانت بسبب “سوء تفسير لنتائج [شميدت]” و ملزمة بمقال مفصل (ويلسون 2014، 225-226). تأليفهم الرائع، كل خريطة مستوية بأربعة ألوان، كتاب يدعي إثباتًا كاملاً ومفصلاً (مع ملحق ميكروفيش يزيد عن 400 صفحة)، ظهر في عام 1989؛ لقد قامت بشرح و تصحيح الخطأ الذي اكتشفه شميدت بالإضافة إلى العديد من الأخطاء الأخرى التي وجدها آخرون (Appel & Haken 1989).
التبسيط والتحقق
منذ إثبات النظرية، تم العثور على خوارزميات فعالة لخرائط التلوين الأربعة التي تتطلب فقط O(n2) الوقت، حيث n هو عدد الرؤوس. في عام 1996، ابتكر نيل روبرتسون، و دانييل بي ساندرز، و بول سيمور، و روبن توماس خوارزمية تربيعية الوقت، محسّنةً خوارزمية الوقت الرباعي بناءً على برهان أبيل وهاكن. هذا الدليل الجديد مشابه لـ Appel و Haken و لكنه أكثر كفاءة لأنه يقلل من تعقيد المشكلة و يتطلب فحص 633 تكوينات قابلة للاختزال فقط. يجب أن يتم تنفيذ كل من الأجزاء التي لا يمكن تجنبها و قابلية الاختزال في هذا الإثبات الجديد بواسطة الكمبيوتر و من غير العملي التحقق منها يدويًا.
في عام 2001، أعلن نفس المؤلفين عن دليل بديل، من خلال إثبات تخمين الشرير. و مع ذلك، لا يزال هذا الدليل غير منشور.
في عام 2005، قام بنيامين ويرنر و جورج غونثير بإضفاء الطابع الرسمي على إثبات النظرية داخل مساعد إثبات Coq. أدى هذا إلى إزالة الحاجة إلى الوثوق ببرامج الكمبيوتر المختلفة المستخدمة للتحقق من حالات معينة؛ من الضروري فقط الوثوق بنواة Coq.
صياغة دقيقة لنظرية الألوان الأربعة
في المصطلحات النظرية للرسم البياني، تنص النظرية على أنه بالنسبة للرسم البياني المستوي بدون حلقة G، فإن رقمه اللوني هو X(G) <= 4.
العبارة الحدسية لنظرية الألوان الأربعة – “بالنظر إلى أي فصل للطائرة إلى مناطق متجاورة، يمكن تلوين المناطق باستخدام أربعة ألوان على الأكثر بحيث لا توجد منطقتان متجاورتان لهما نفس اللون” –يجب تفسيرها بشكل مناسب لتكون صحيحة .
أولاً، تكون المناطق متجاورة إذا كانت تشترك في مقطع حدودي؛ منطقتان تشتركان فقط في نقاط حدودية معزولة لا تعتبر متجاورة. ثانيًا، لا يُسمح بالمناطق الغريبة، مثل تلك التي لها مساحة محدودة و لكن محيطها طويل بلا حدود؛ يمكن أن تتطلب الخرائط بمثل هذه المناطق أكثر من أربعة ألوان. (لكي نكون آمنين، يمكننا أن نقتصر على المناطق التي تتكون حدودها من عدد محدود من مقاطع الخطوط المستقيمة. و يُسمح بأن تحيط منطقة بالكامل بمنطقة أخرى أو أكثر.)
لاحظ أن مفهوم “المنطقة المتجاورة” (تقنيًا: مجموعة فرعية متصلة مفتوحة من الطائرة) ليس هو نفسه “البلد” على الخرائط العادية، حيث لا يلزم أن تكون البلدان متجاورة (على سبيل المثال، مقاطعة كابيندا كجزء من أنغولا، و ناختشيفان كجزء من أذربيجان، و كالينينغراد كجزء من روسيا، و ألاسكا كجزء من الولايات المتحدة ليست متجاورة). إذا طلبنا من إقليم بلد ما الحصول على نفس اللون، فلن تكون الألوان الأربعة كافية دائمًا. على سبيل المثال، ضع في اعتبارك خريطة مبسطة:
في هذه الخريطة، تنتمي المنطقتان المسمى “A” إلى نفس البلد. إذا أردنا أن تتلقى تلك المناطق نفس اللون، فسنحتاج إلى خمسة ألوان، نظرًا لأن منطقتي A معًا متجاورتان لأربع مناطق أخرى، كل منها متاخمة لجميع المناطق الأخرى. يمكن نمذجة إجبار منطقتين منفصلتين على الحصول على نفس اللون عن طريق إضافة “مقبض” يربطهما خارج المستوى.
مثل هذا البناء يجعل المشكلة مكافئة لتلوين خريطة على طارة (سطح من الجنس 1)، و التي تتطلب ما يصل إلى 7 ألوان لخريطة عشوائية. ينطبق إنشاء مماثل أيضًا إذا تم استخدام لون واحد لمناطق منفصلة متعددة، كما هو الحال بالنسبة للمسطحات المائية على الخرائط الحقيقية، أو إذا كان هناك المزيد من البلدان ذات المناطق المنفصلة. في مثل هذه الحالات، قد تكون هناك حاجة إلى مزيد من الألوان مع جنس متزايد من سطح ناتج. (انظر قسم التعميمات أدناه.)
الصورة: خريطة بأربع مناطق، و الرسم البياني المستوي المقابل بأربعة رؤوس.
بيان أبسط للنظرية يستخدم نظرية الرسم البياني. يمكن تمثيل مجموعة مناطق الخريطة بشكل أكثر تجريدًا كرسم بياني غير موجه يحتوي على رأس لكل منطقة وحافة لكل زوج من المناطق التي تشترك في مقطع حدودي. هذا الرسم البياني مستوٍ: يمكن رسمه في المستوى بدون تقاطعات عن طريق وضع كل رأس في موقع تم اختياره عشوائيًا داخل المنطقة التي يتوافق معها، و عن طريق رسم الحواف كمنحنيات بدون تقاطعات تؤدي من قمة منطقة واحدة، عبر نقطة مشتركة قطعة حدية، إلى رأس منطقة مجاورة. على العكس من ذلك، يمكن تشكيل أي رسم بياني مستو من الخريطة بهذه الطريقة. في المصطلحات النظرية للرسم البياني، تنص نظرية الألوان الأربعة على أنه يمكن تلوين رؤوس كل رسم بياني مستوٍ بأربعة ألوان على الأكثر بحيث لا يتلقى رأسان متجاوران نفس اللون، أو باختصار: كل رسم بياني مستوٍ ذو أربعة ألوان.
اقرأ أیضًا أهم قوانين الرياضيات
تعميمات نظرية الألوان الأربعة
الرسوم البيانية لانهائية
الصورة: من خلال ضم الأسهم المفردة معًا والسهام المزدوجة معًا، يحصل المرء على طارة بها سبع مناطق متلامسة؛ لذلك سبعة ألوان ضرورية
الصورة: يوضح هذا البناء الطارة مقسمة إلى سبع مناطق كحد أقصى، كل واحدة منها تلامس بعضها البعض.
لا تنطبق نظرية الألوان الأربعة على الرسوم البيانية المستوية المحدودة فحسب، بل تنطبق أيضًا على الرسوم البيانية اللانهائية التي يمكن رسمها بدون تقاطعات في المستوى، وبشكل أكثر عمومية على الرسوم البيانية اللانهائية (ربما مع عدد لا يحصى من الرؤوس) التي يكون كل رسم بياني فرعي محدد لها مستو. لإثبات ذلك، يمكن للمرء أن يجمع دليلًا على نظرية الرسوم البيانية المستوية المحدودة مع نظرية De Bruijn–Erdős التي تنص على أنه إذا كان كل رسم بياني فرعي محدود من الرسم البياني اللانهائي قابلًا للتلوين على شكل k، فإن الرسم البياني بأكمله يكون أيضًا قابلاً للتلوين على شكل k Nash- وليامز (1967). يمكن أيضًا اعتبار هذا نتيجة فورية لنظرية ضغط كورت جودل لمنطق الدرجة الأولى، ببساطة عن طريق التعبير عن قابلية تلوين الرسم البياني اللانهائي بمجموعة من الصيغ المنطقية.
سطح أعلى
يمكن للمرء أيضًا أن يفكر في مشكلة التلوين على الأسطح غير المستوية. المشكلة على الكرة أو الأسطوانة تعادل تلك الموجودة على المستوى. بالنسبة للأسطح المغلقة (القابلة للتوجيه أو غير القابلة للتوجيه) ذات الجنس الإيجابي، يعتمد الحد الأقصى لعدد الألوان المطلوبة على خاصية أويلر للسطح χ وفقًا للصيغة
حيث تشير الأقواس الخارجية إلى دالة الأرضية.
بدلاً من ذلك، بالنسبة للسطح القابل للتوجيه، يمكن إعطاء الصيغة من حيث جنس السطح، g:
الصورة: نموذج متعدد السطوح Szilassi التفاعلي مع كل وجه بلون مختلف.
هذه الصيغة، تخمين هيوود، اقترحها P.J.Heawood في عام 1890، و بعد مساهمات عدة أشخاص، أثبتها غيرهارد رينجل وجيه دبليو ت يونغز (جون ويليام ثيودور يونغز) في عام 1968. الاستثناء الوحيد للصيغة هو زجاجة كلاين، التي لها خاصية أويلر 0 (و من ثم تعطي الصيغة p = 7) ولكنها تتطلب 6 ألوان فقط، كما أوضح فيليب فرانكلين في عام 1934.
على سبيل المثال، تتميز الحلقة بخاصية أويلر)χ = 0 والجنس g = 1) و بالتالي p = 7، لذلك لا يلزم وجود أكثر من 7 ألوان لتلوين أي خريطة. هذا الحد الأعلى لـ 7 حاد:تتطلب بعض الأشكال المتعددة السطوح الحلقيّة مثل Szilassi polyhedron سبعة ألوان.
الصورة: تقسيم تيتز لشريط موبيوس إلى ست مناطق متجاورة، مما يتطلب ستة ألوان. تشكل رؤوس وحواف التقسيم الفرعي دمجًا لمخطط تيتز على الشريط.
يتطلب شريط Möbius ستة ألوان (Tietze 1910) كما هو الحال مع الرسوم البيانية ذات المستوى الواحد (الرسوم البيانية المرسومة مع تقاطع بسيط واحد على الأكثر لكل حافة) (Borodin 1984). إذا تم تلوين كل من الرؤوس والوجوه في الرسم البياني المستوي، بحيث لا يكون هناك رأسان متجاوران، أو وجوه، أو زوج ذو وجه رأس متجاور لهما نفس اللون، فسنحتاج مرة أخرى إلى ستة ألوان على الأكثر (Borodin 1984).
المناطق الصلبة
لا يوجد امتداد واضح لنتيجة التلوين إلى مناطق صلبة ثلاثية الأبعاد. باستخدام مجموعة من القضبان المرنة n، يمكن للمرء أن يرتب أن كل قضيب يلامس كل قضيب آخر. ستتطلب المجموعة بعد ذلك n لونًا، أو n + 1 إذا كنت تفكر في المساحة الفارغة التي تلامس أيضًا كل قضيب. يمكن اعتبار الرقم n أي عدد صحيح، بالحجم المرغوب. كانت هذه الأمثلة معروفة لفريدريك جوثري في عام 1880 (ويلسون 2014). حتى بالنسبة للمكعبات متوازية المحور (تعتبر متجاورة عندما يشترك شكلان متوازيان في منطقة حد ثنائية الأبعاد)، قد يكون من الضروري وجود عدد غير محدود من الألوان (Reed & Allwright 2008؛ Magnant & Martin (2011)).
كتاب للقراءة عن نظرية أربعة ألوان
نظرية الألوان الأربعة: التاريخ والأسس الطوبولوجية وفكرة الإثبات
بقلم: لرودولف فريتش، جيردا فريتش
يناقش هذا الكتاب الصغير الأنيق مشكلة شهيرة ساعدت في تحديد المجال المعروف الآن باسم نظرية الرسم البياني: ما هو الحد الأدنى لعدد الألوان المطلوبة لطباعة خريطة بحيث لا يوجد دولتان متجاورتان لهما نفس اللون، بغض النظر عن مدى تعقيد حدودهما. لقد عمل العديد من علماء الرياضيات المشهورين على حل هذه المشكلة، لكن الدليل استعصى على الصياغة حتى السبعينيات، عندما تم تصدعها أخيرًا بنهج القوة الغاشمة باستخدام الكمبيوتر.
تبدأ نظرية الألوان الأربعة بمناقشة تاريخ المشكلة حتى النهج الجديد المعطى في التسعينيات (بواسطة نيل روبرتسون ودانييل ساندرز وبول سيمور وروبن توماس). ينتقل الكتاب بعد ذلك إلى الرياضيات، مع مناقشة تفصيلية حول كيفية تحويل المشكلة الطوبولوجية الأصلية إلى مشكلة اندماجية أولية بما يكفي بحيث يمكن لأي شخص لديه معرفة أساسية بالهندسة أن يتبعها و أيضًا صارم بما يكفي ليتمكن عالم الرياضيات من قراءتها. بارتياح. يناقش المؤلفون الرياضيات ويشيرون إلى الجدل الفلسفي الذي أعقب ذلك عندما تم الإعلان عن الدليل: فقط ما هو الدليل الرياضي، إذا كان الأمر يتطلب جهاز كمبيوتر لتقديمه – وهل هذا دليل على الإطلاق؟
الملفات المرفقة
