نظرية الألوان الأربعة

في الرياضيات ، تنص نظرية الألوان الأربعة ، أو نظرية خريطة الألوان الأربعة ، على أنه لا يلزم أكثر من أربعة ألوان لتلوين مناطق أي خريطة بحيث لا تتشابه منطقتان متجاورتان في اللون. والمقصود بالتجاور أن منطقتين تشتركان في حدود مشتركة ذات طول غير صفري (أي ليس مجرد زاوية تلتقي عندها ثلاث مناطق أو أكثر). ^{[ 1 ]} كانت هذه أول نظرية رئيسية تُثبت باستخدام الحاسوب . في البداية، لم يتقبل جميع علماء الرياضيات هذا البرهان لأن التحقق منه يدويًا كان مستحيلاً بالنسبة للإنسان . ^{[ 2 ]} ومنذ ذلك الحين، حظي البرهان بقبول واسع، على الرغم من بقاء بعض التحفظات. ^{[ 3 ]}

تُعدّ هذه النظرية نسخةً أقوى من نظرية الألوان الخمسة ، والتي يُمكن إثباتها باستخدام حجةٍ أبسط بكثير. مع أن نظرية الألوان الخمسة الأضعف قد أُثبتت في القرن التاسع عشر، إلا أن نظرية الألوان الأربعة ظلت عصيةً على الإثبات حتى عام ١٩٧٦، حين أثبتها كينيث أبيل وولفغانغ هاكن باستخدام برهانٍ مُحوسب . جاء ذلك بعد العديد من البراهين الخاطئة والأمثلة المضادة المُضللة في العقود السابقة.

تعتمد برهان أبيل-هاكن على تحليل عدد كبير جدًا من "التكوينات القابلة للاختزال"، وهي أمثلة على دوال ذات خاصية معينة. وقد طُوّر هذا البرهان عام ١٩٩٧ على يد روبرتسون وساندرز وسيمور وتوماس، الذين تمكنوا من تقليص عدد هذه التكوينات إلى ٦٣٣، وهو عدد لا يزال كبيرًا جدًا. وفي عام ٢٠٠٥، تحقق جورج غونتييه من صحة النظرية باستخدام برنامج عام لإثبات النظريات .

التركيبة

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

لكي يكون هذا ذا معنى، يجب تفسير البيان البديهي لنظرية الألوان الأربعة - "بالنظر إلى أي تقسيم لمستوى إلى مناطق متجاورة، يمكن تلوين المناطق باستخدام أربعة ألوان على الأكثر بحيث لا يكون لأي منطقتين متجاورتين نفس اللون" - بشكل مناسب.

أولًا، تُعتبر المناطق متجاورة إذا كانت تشترك في جزء من الحدود؛ أما المنطقتان اللتان تشتركان في نقاط حدودية معزولة فقط فلا تُعتبران متجاورتين. (وإلا، فإن الخريطة على شكل مخطط دائري ستجعل عددًا كبيرًا من المناطق "متجاورة" عند زاوية مشتركة، مما يستلزم عددًا كبيرًا من الألوان). ثانيًا، لا يُسمح بالمناطق غير المألوفة، مثل تلك التي لها مساحة محدودة ومحيط لا نهائي الطول؛ ويمكن أن تتطلب الخرائط التي تحتوي على مثل هذه المناطق أكثر من أربعة ألوان. ^{[ 4 ]} (لضمان الدقة، يمكننا الاقتصار على المناطق التي تتكون حدودها من عدد محدود من القطع المستقيمة. يُسمح بوجود جيوب معزولة في المنطقة ، أي أنها تُحيط تمامًا بمنطقة أو أكثر). تجدر الإشارة إلى أن مفهوم "المنطقة المتجاورة" (تقنيًا: مجموعة فرعية مفتوحة متصلة من المستوى) يختلف عن مفهوم "الدولة" في الخرائط العادية، إذ لا يشترط أن تكون الدولة متجاورة: فقد تحتوي على جيوب معزولة ، مثل أنغولا ومقاطعة كابيندا ، وأذربيجان وجمهورية ناخيتشيفان ذاتية الحكم ، وروسيا ومقاطعة كالينينغراد ، وفرنسا وأقاليمها ما وراء البحار ، والولايات المتحدة وولاية ألاسكا . إذا اشترطنا أن تُلوّن جميع أراضي الدولة بنفس اللون، فإن أربعة ألوان لا تكفي دائمًا. على سبيل المثال، انظر إلى الخريطة المبسطة:

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

يستخدم بيان أبسط لنظرية الألوان الأربعة نظرية المخططات . يمكن تمثيل مجموعة مناطق الخريطة بشكل أكثر تجريدًا كمخطط غير موجه ، حيث يمثل كل منطقة رأسًا، ويمثل كل زوج من المناطق التي تشترك في قطعة حدودية حافة. هذا المخطط مستوٍ : يمكن رسمه في المستوى دون تقاطعات بوضع كل رأس في موقع مختار عشوائيًا داخل المنطقة التي يمثلها، ورسم الحواف كمنحنيات دون تقاطعات، تمتد من رأس منطقة ما، عبر قطعة حدودية مشتركة، إلى رأس منطقة مجاورة. وبالعكس، يمكن تكوين أي مخطط مستوٍ من خريطة بهذه الطريقة. في مصطلحات نظرية المخططات، تنص نظرية الألوان الأربعة على أنه يمكن تلوين رؤوس أي مخطط مستوٍ بأربعة ألوان على الأكثر، بحيث لا يحصل أي رأسين متجاورين على اللون نفسه، أو باختصار: كل مخطط مستوٍ قابل للتلوين بأربعة ألوان . ^{[ 5 ]}

تاريخ

محاولات إثبات مبكرة

رسالة دي مورغان إلى ويليام روان هاميلتون ، 23 أكتوبر 1852

بحسب ما هو معروف، ^{[ 6 ]} طُرحت هذه الفرضية لأول مرة في 23 أكتوبر 1852، ^{[ 7 ]} عندما لاحظ فرانسيس غوثري ، أثناء محاولته تلوين خريطة مقاطعات إنجلترا، أنه لا يلزم سوى أربعة ألوان مختلفة. في ذلك الوقت، كان فريدريك ، شقيق غوثري ، طالبًا لدى أوغسطس دي مورغان (المستشار السابق لفرانسيس) في جامعة لندن . استفسر فرانسيس من فريدريك عن الأمر، الذي بدوره عرضه على دي مورغان. (تخرج فرانسيس غوثري لاحقًا في عام 1852، وأصبح فيما بعد أستاذًا للرياضيات في جنوب إفريقيا). وفقًا لدي مورغان:

سألني أحد طلابي [غوثري] اليوم أن أقدم له تفسيراً لحقيقة لم أكن أعرف أنها حقيقة - ولا زلت أجهلها. يقول إنه إذا قُسِّم شكلٌ ما بأي شكلٍ من الأشكال، ولُوِّنت أقسامه بألوانٍ مختلفة بحيث تكون الأشكال التي تشترك في أي جزء من خط حدودي مختلفة الألوان - فقد يُراد أربعة ألوان فقط - فإن الحالة التالية هي التي يُراد فيها أربعة ألوان . ولا يمكن اختلاق ضرورة لخمسة ألوان أو أكثر... ^{[ 8 ]}

نشر "FG"، ربما أحد غوثري، السؤال في مجلة The Athenaeum عام 1854، ^{[ 9 ]} وطرح دي مورغان السؤال مرة أخرى في نفس المجلة عام 1860. ^{[ 10 ]} وينسب مرجع منشور مبكر آخر لآرثر كايلي ( 1879 ) بدوره التخمين إلى دي مورغان.

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

ينشأ هذا على النحو التالي: لا نحتاج أبدًا إلى أربعة ألوان في منطقة ما إلا إذا كانت هناك أربع مقاطعات، لكل منها حدود مشتركة مع المقاطعات الثلاث الأخرى. ولا يمكن أن يحدث هذا مع أربع مناطق إلا إذا كانت واحدة أو أكثر منها محاطة بالباقي؛ وبالتالي، يُترك اللون المستخدم للمقاطعة المحاطة حرًا. الآن، هذا المبدأ، وهو أن أربع مناطق لا يمكن أن يكون لكل منها حدود مشتركة مع المقاطعات الثلاث الأخرى دون إحاطة، لا يمكن، في اعتقادنا التام، إثباته بأي شيء أكثر وضوحًا وبديهية؛ بل يجب أن يبقى مجرد مسلمة. ^{[ 10 ]}

قدّم ألفريد كيمب أحد البراهين المقترحة عام 1879، والذي لاقى استحسانًا واسعًا؛ ^{[ 11 ]} وقدّم بيتر غوثري تيت برهانًا آخر عام 1880. ولم يُثبت خطأ برهان كيمب إلا عام 1890 على يد بيرسي هيوود ، وفي عام 1891، أثبت يوليوس بيترسن خطأ برهان تيت - وظل كل برهان خاطئًا دون دحض لمدة 11 عامًا. ^{[ 12 ]}

في عام 1890، بالإضافة إلى كشفه عن الخلل في برهان كيمب، أثبت هيوود نظرية الألوان الخمسة وعمّم تخمين الألوان الأربعة على أسطح من أي جنس . ^{[ 13 ]}

أظهر تايت في عام 1880 أن نظرية الألوان الأربعة تعادل القول بأن نوعًا معينًا من الرسوم البيانية (يسمى snark في المصطلحات الحديثة) يجب أن يكون غير مستوٍ . ^{[ 14 ]}

في عام 1943، صاغ هوغو هادويغر حدسية هادويغر ، ^{[ 15 ]} وهي تعميم بعيد المدى لمشكلة الألوان الأربعة التي لا تزال غير محلولة.

إثبات بواسطة الحاسوب

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

تبنى آخرون أساليبه، بما في ذلك نهجه المدعوم بالحاسوب. وبينما كانت فرق أخرى من علماء الرياضيات تتسابق لإكمال البراهين، أعلن كينيث أبيل وولفغانغ هاكن من جامعة إلينوي ، في 21 يونيو 1976، ^{[ 17 ]} أنهم أثبتوا النظرية. وقد ساعدهم جون أ. كوخ في بعض الأعمال الخوارزمية . ^{[ 18 ]}

لو كانت فرضية الألوان الأربعة خاطئة، لكانت هناك خريطة واحدة على الأقل بأقل عدد ممكن من المناطق تتطلب خمسة ألوان. وقد أظهر البرهان، باستخدام مفهومين تقنيين، استحالة وجود مثل هذا المثال المضاد الأدنى: ^{[ 19 ]}

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

باستخدام قواعد وإجراءات رياضية مبنية على خصائص التكوينات القابلة للاختزال، وجد أبيل وهاكن مجموعة حتمية من هذه التكوينات، مُثبتين بذلك استحالة وجود مثال مضاد أدنى لفرضية الألوان الأربعة. اختزل برهانهما عدد الخرائط الممكنة اللانهائي إلى 1834 تكوينًا قابلًا للاختزال (ثم اختُزل لاحقًا إلى 1482)، والتي تطلّب فحصها واحدًا تلو الآخر بواسطة الحاسوب، واستغرق ذلك أكثر من ألف ساعة. خضع هذا الجزء المتعلق بالاختزال من العمل لمراجعة مزدوجة مستقلة باستخدام برامج وحواسيب مختلفة. أما الجزء المتعلق بالحتمية من البرهان، فقد تم التحقق منه في أكثر من 400 صفحة من الميكروفيلم ، والتي تطلّب فحصها يدويًا بمساعدة ابنة هاكن، دوروثيا بلوستين . ^{[ 20 ]}

حظي إعلان أبيل وهاكن بتغطية إعلامية واسعة النطاق حول العالم، ^{[ 21 ]} واستخدم قسم الرياضيات في جامعة إلينوي ختمًا بريديًا كُتب عليه "أربعة ألوان تكفي". ^{[ 22 ]} في الوقت نفسه، أثارت الطبيعة غير المألوفة للبرهان - إذ كان أول نظرية رئيسية تُثبت بمساعدة حاسوبية مكثفة - وتعقيد الجزء القابل للتحقق البشري جدلًا واسعًا. ^{[ 23 ]} لم يتقبل جميع علماء الرياضيات فكرة أن البرهان الحاسوبي يُمكن اعتباره برهانًا حقيقيًا. حتى أن بعض من تقبّلوا ذلك، مثل إيان ستيوارت ، وجدوا البرهان غير مُرضٍ، لأنه جاء كأمر واقع وافتقر إلى بنية منطقية. كتب ستيوارت: "يبدو الجواب وكأنه مصادفة غريبة". ورأى إتش إس إم كوكسيتر أنه "من غير المرجح أن يتمكن أي شخص من تحليل هذا البرهان إلى شيء يُمكن اعتباره برهانًا عاديًا". ^{[ 24 ]}

في أوائل ثمانينيات القرن العشرين، انتشرت شائعات عن وجود خلل في برهان أبيل وهاكن . كان أولريش شميدت من جامعة RWTH آخن قد فحص برهان أبيل وهاكن لأطروحته للماجستير التي نُشرت عام 1981. ^{[ 25 ]} وقد راجع حوالي 40% من جزء الحتمية ووجد خطأً جوهريًا في إجراء التفريغ ( أبيل وهاكن 1989 ) . في عام 1986، طلب محرر مجلة Mathematical Intelligencer من أبيل وهاكن كتابة مقال يتناول شائعات وجود عيوب في برهانهما. فأجابا بأن الشائعات ناتجة عن "سوء فهم لنتائج [شميدت]"، وقدّما مقالًا مفصلًا. ^{[ 25 ]} وفي عام 1989، ظهر عملهما الرئيسي ، " كل خريطة مستوية قابلة للتلوين بأربعة ألوان" ، وهو كتاب يدّعي تقديم برهان كامل ومفصل (مع ملحق ميكروفيلمي يزيد عن 400 صفحة). وقد شرحت وصححت الخطأ الذي اكتشفه شميدت بالإضافة إلى العديد من الأخطاء الأخرى التي وجدها آخرون. ^{[ 20 ]}

التبسيط والتحقق

منذ إثبات النظرية، أدى نهج جديد إلى برهان أقصر وخوارزمية أكثر كفاءة لتلوين الخرائط بأربعة ألوان. في عام 1996، ابتكر نيل روبرتسون ، ودانيال ب ^.ساندرز ، وبول سيمور ، وروبن توماس خوارزمية ذات زمن تربيعي (تتطلب زمنًا قدره O ( n² ) فقط، حيث n هو عدد الرؤوس)، مُحسِّنين بذلك خوارزمية ذات زمن رباعي مبنية على برهان أبيل وهاكن. ^[²⁶^] البرهان الجديد، المبني على الأفكار نفسها، مشابه لبرهان أبيل وهاكن ولكنه أكثر كفاءة لأنه يُقلل من تعقيد المسألة ويتطلب فحص 633 تكوينًا قابلاً للاختزال فقط. يجب تنفيذ جزئيّ الحتمية والاختزال في هذا البرهان الجديد بواسطة الحاسوب، ومن غير العملي التحقق منهما يدويًا. ^[²⁷^] في عام 2001، أعلن المؤلفون أنفسهم عن برهان بديل، من خلال إثبات تخمين سنارك . ^[²⁸^] ومع ذلك، فإن هذا الدليل لا يزال غير منشور.

في عام 2005، قام بنيامين فيرنر وجورج غونتييه بصياغة برهان رسمي للنظرية داخل مساعد البرهان Coq . وقد أدى ذلك إلى الاستغناء عن الحاجة إلى الوثوق ببرامج الحاسوب المختلفة المستخدمة للتحقق من حالات معينة؛ إذ يكفي فقط الوثوق بنواة Coq. ^{[ 29 ]}

ملخص أفكار البرهان

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

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

لنفترض أن v و e و f هي عدد الرؤوس والحواف والمناطق (الوجوه) على التوالي. بما أن كل منطقة مثلثية الشكل، وكل حافة مشتركة بين منطقتين، فإن 2e = 3f . وباستخدام صيغة أويلر ، v - e + f = 2، يمكننا إثبات أن 6v - 2e = 12. الآن، درجة الرأس هي عدد الحواف المجاورة له. إذا كان _vn هو عدد الرؤوس من الدرجة n، و D هي أعلى درجة لأي رأس،

6v-2e=6\sum _{i=1}^{D}v_{i}-\sum _{i=1}^{D}iv_{i}=\sum _{i=1}^{D}(6-i)v_{i}=12.

ولكن بما أن 12 > 0 و 6 − i ≤ 0 لجميع i ≥ 6، فإن هذا يوضح أن هناك رأسًا واحدًا على الأقل من الدرجة 5 أو أقل.

إذا وُجد رسم بياني يتطلب 5 ألوان، فإنه يوجد رسم بياني أصغر منه، بحيث يُمكن تلوينه بأربعة ألوان عند إزالة أي رأس منه. لنُسمِّ هذا الرسم البياني G. إذن، لا يُمكن أن يحتوي G على رأس من الدرجة 3 أو أقل، لأنه إذا كانت درجة الرأس v أقل من أو تساوي 3، يُمكننا إزالة v من G ، وتلوين الرسم البياني الأصغر بأربعة ألوان، ثم إعادة v إليه وتوسيع نطاق التلوين الرباعي ليشمله باختيار لون مختلف عن ألوان جيرانه.

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

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

على أي حال، تتطلب معالجة حالة الرأس ذي الدرجة 5 مفهومًا أكثر تعقيدًا من مجرد إزالة رأس. بل يُعمم شكل الحجة ليشمل النظر في التكوينات ، وهي رسوم بيانية فرعية متصلة من G مع تحديد درجة كل رأس (في G). على سبيل المثال، الحالة الموصوفة في وضع الرأس ذي الدرجة 4 هي التكوين الذي يتكون من رأس واحد مُصنف بدرجة 4 في G. وكما ذُكر سابقًا، يكفي إثبات أنه إذا أُزيل التكوين ولُوِّن الرسم البياني المتبقي بأربعة ألوان، فإنه يمكن تعديل التلوين بحيث عند إعادة إضافة التكوين، يمكن توسيع التلوين الرباعي ليشمله أيضًا. يُسمى التكوين الذي يكون هذا ممكنًا تكوينًا قابلًا للاختزال . إذا كان لا بد من ظهور تكوين واحد على الأقل من مجموعة تكوينات في مكان ما في G، تُسمى هذه المجموعة تكوينًا لا مفر منه . بدأت الحجة أعلاه بإعطاء مجموعة لا مفر منها من خمسة تكوينات (رأس واحد بدرجة 1، رأس واحد بدرجة 2، ...، رأس واحد بدرجة 5) ثم شرعت في إظهار أن أول 4 منها قابلة للاختزال؛ إن إظهار مجموعة لا مفر منها من التكوينات حيث يكون كل تكوين في المجموعة قابلاً للاختزال من شأنه أن يثبت النظرية.

بما أن G مثلثي، فإن درجة كل رأس في التكوين معروفة، وكذلك جميع الحواف الداخلية لهذا التكوين، وعدد الرؤوس في G المجاورة لتكوين معين ثابت، وهي متصلة في دورة. تشكل هذه الرؤوس حلقة التكوين ؛ ويُطلق على التكوين الذي يحتوي على k رأس في حلقته اسم تكوين الحلقة k ، ويُسمى التكوين مع حلقته بالتكوين الحلقي . كما في الحالات البسيطة المذكورة أعلاه، يمكن تعداد جميع التلوينات الرباعية المختلفة للحلقة؛ ويُسمى أي تلوين يمكن توسيعه دون تعديل إلى تلوين التكوين باللون الجيد مبدئيًا . على سبيل المثال، كان التكوين ذو الرأس الواحد المذكور أعلاه، والذي يحتوي على 3 جيران أو أقل، جيدًا مبدئيًا. بشكل عام، يجب إعادة تلوين الرسم البياني المحيط بشكل منهجي لتحويل تلوين الحلقة إلى تلوين جيد، كما هو الحال في الحالة المذكورة أعلاه حيث كان هناك 4 جيران؛ أما بالنسبة للتكوين العام ذي الحلقة الأكبر، فيتطلب ذلك تقنيات أكثر تعقيدًا. نظراً للعدد الكبير من الألوان الرباعية المميزة للحلقة، فإن هذه هي الخطوة الأساسية التي تتطلب مساعدة الكمبيوتر.

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

تذكر الصيغة أعلاه:

\sum _{i=1}^{D}(6-i)v_{i}=12.

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

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

هناك تفصيل تقني لم تتم مناقشته هنا ولكنه مطلوب لإكمال البرهان وهو قابلية الاختزال بالغمر .

دحض زائف

اشتهرت نظرية الألوان الأربعة بكثرة البراهين والأدلة الزائفة التي دُحضت بها على مر تاريخها الطويل. في البداية، رفضت صحيفة نيويورك تايمز ، كسياسة عامة، نشر برهان أبيل-هاكن، خشية أن يُكشف زيفه كما حدث مع البراهين السابقة. ^{[ 21 ]} بعض البراهين المزعومة، كبرهاني كيمب وتيت المذكورين آنفًا، خضعت للتدقيق العام لأكثر من عقد قبل دحضها. لكن العديد من البراهين الأخرى، التي وضعها هواة، لم تُنشر قط.

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

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

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

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

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

ثلاثة ألوان

على الرغم من إمكانية تلوين أي خريطة مستوية بأربعة ألوان، إلا أن تحديد ما إذا كان من الممكن تلوين خريطة مستوية عشوائية بثلاثة ألوان فقط يمثل مسألة معقدة من نوع NP-complete . ^[³⁰^]

يمكن تلوين خريطة مكعبة بثلاثة ألوان فقط إذا وفقط إذا كان لكل منطقة داخلية عدد زوجي من المناطق المجاورة. [ 31 ^{] في مثال} خريطة الولايات الأمريكية، تمتلك ولاية ميسوري (MO) غير الساحلية ثمانية جيران (عدد زوجي): يجب أن يكون لونها مختلفًا عن ألوانهم جميعًا، ولكن يمكن للجيران أن يتبادلوا الألوان، وبالتالي يحتاج هذا الجزء من الخريطة إلى ثلاثة ألوان فقط. أما ولاية نيفادا (NV) غير الساحلية فلها خمسة جيران (عدد فردي): يتطلب هؤلاء الجيران ثلاثة ألوان، ويجب أن يكون لونها مختلفًا عن ألوانهم، وبالتالي يلزم أربعة ألوان هنا.

التعميمات

الرسوم البيانية اللانهائية

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

الأسطح المرتفعة

يمكن أيضًا دراسة مسألة التلوين على أسطح أخرى غير السطح المستوي. ^{[ 32 ]} تُكافئ المسألة على الكرة أو الأسطوانة تلك على السطح المستوي. بالنسبة للأسطح المغلقة (القابلة للتوجيه أو غير القابلة للتوجيه) ذات الجنس الموجب ، يعتمد الحد الأقصى لعدد الألوان المطلوبة $(p)$ على خاصية أويلر $(χ)$ للسطح. باستثناء زجاجة كلاين، تكون الصيغة كما يلي: $p=\left\lfloor {\frac {7+{\sqrt {49-24\chi }}}{2}}\right\rfloor ,$ حيث تشير الأقواس الخارجية إلى دالة الجزء الصحيح .

بالنسبة للسطح القابل للتوجيه ، فإن هذا يعني أنه يمكن إعطاء $p$ بدلالة جنس السطح $g :$ $p=\left\lfloor {\frac {7+{\sqrt {1+48g}}}{2}}\right\rfloor .$

تم اقتراح الصيغة العليا، وهي حدسية هيوود ، من قبل بي جيه هيوود في عام 1890، وبعد مساهمات من عدة أشخاص، تم إثباتها من قبل جيرهارد رينجل وجيه دبليو تي يونغز في عام 1968. الاستثناء الوحيد للصيغة هو زجاجة كلاين ، التي لها خاصية أويلر $χ = 0$ (وبالتالي تعطي الصيغة $p = 7$ ) ولكنها تتطلب ستة ألوان فقط، كما أوضح فيليب فرانكلين في عام 1934.

على سبيل المثال، يتميز السطح الحلقي بخاصية أويلر $χ = 0$ (وجنس $g = 1$ )، وبالتالي فإن $p = 7$ ، لذا لا يتطلب الأمر أكثر من سبعة ألوان لتلوين أي خريطة على السطح الحلقي. هذا الحد الأعلى البالغ $7$ دقيق للغاية : فبعض المجسمات الحلقية ، مثل مجسم زيلاسي ، تتطلب سبعة ألوان.

يتطلب شريط موبيوس ستة ألوان ( تيتز ، 1910 )، وكذلك الرسوم البيانية المستوية أحادية البعد (الرسوم البيانية المرسومة بتقاطع بسيط واحد على الأكثر لكل حافة) ( بورودين، 1984 ) . إذا تم تلوين كل من رؤوس ووجوه الرسم البياني المستوي، بحيث لا يكون لأي رأسين أو وجهين متجاورين، أو أي زوج من الرؤوس والوجوه، نفس اللون، فعندئذٍ يلزم ستة ألوان على الأكثر ( بورودين، 1984 ) .

المستوى الإسقاطي الحقيقي له خاصية أويلر $χ = 1$ والصيغة تعطي $p = 6$ ، لذلك لا يلزم أكثر من ستة ألوان.

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

بالنسبة للرسوم البيانية التي تُمثل رؤوسها بأزواج من النقاط على سطحين متميزين، مع رسم الحواف كمنحنيات غير متقاطعة على أحد السطحين، يمكن أن يكون العدد اللوني $9 على الأقل و$ $12$ على الأكثر ، ولكن الحدود الأكثر دقة غير معروفة؛ هذه هي مسألة الأرض والقمر لغيرهارد رينجل . ^[³³^]

مناطق صلبة

لا يوجد امتداد واضح لنتيجة التلوين إلى المناطق الصلبة ثلاثية الأبعاد. باستخدام مجموعة من $n$ قضيبًا مطويًا، يمكن ترتيب كل قضيب بحيث يلامس كل قضيب آخر. تتطلب المجموعة حينها $n$ لونًا، أو $n$ $+ 1$ إذا أُخذت المساحة الفارغة (التي تلامس أيضًا كل قضيب) في الحسبان. يمكن اختيار العدد $n أي عدد صحيح، مهما كان حجمه. كانت هذه الأمثلة معروفة لفريدريك غوثري عام 1880.$ ^[³⁴^] حتى بالنسبة للمكعبات المتوازية المحاور (يُعتبر مكعبان متجاورين إذا كانا يشتركان في سطح حدودي ثنائي الأبعاد)، قد يكون من الضروري استخدام عدد غير محدود من الألوان. ^[³⁵^]

العلاقة بمجالات أخرى من الرياضيات

قدم درور بار ناتان بيانًا يتعلق بجبر لي وثوابت فاسيليف وهو ما يعادل نظرية الألوان الأربعة. ^{[ 36 ]}

استخدامات خارج نطاق الرياضيات

على الرغم من الدافع وراء تلوين الخرائط السياسية للدول ، فإن هذه النظرية لا تحظى باهتمام خاص من رسامي الخرائط . فبحسب مقال للمؤرخ الرياضي كينيث ماي ، "الخرائط التي تستخدم أربعة ألوان فقط نادرة، وتلك التي تستخدمها عادةً ما تتطلب ثلاثة ألوان فقط. ولا تذكر كتب رسم الخرائط وتاريخها خاصية الألوان الأربعة". ^{[ 37 ]} كما أن هذه النظرية لا تضمن الشرط المعتاد في رسم الخرائط، وهو أن تُلوّن المناطق غير المتجاورة في الدولة نفسها (مثل ألاسكا وبقية الولايات المتحدة ) بنفس اللون. ^{[ 38 ]} ولأن نظرية الألوان الأربعة لا تنطبق عندما لا تكون المناطق على الخريطة متجاورة، فإنها لا تنطبق أيضًا على خريطة العالم. فعلى خريطة العالم، يتجاور المحيط وبلجيكا وألمانيا وهولندا وفرنسا، لأن هولندا تجاور فرنسا في جزيرة سانت مارتن .

لا تنطبق هذه النظرية أيضًا إذا اشترطنا تلوين جميع المسطحات المائية بلون واحد لا يمكن استخدامه لتمثيل دولة (كالأزرق مثلاً). عندئذٍ، لا يمكن تلوين خريطة أوروبا بأربعة ألوان. يجب تخصيص ثلاثة ألوان مختلفة لفرنسا وألمانيا وبلجيكا، نظرًا لتجاورها، ما يستلزم استخدام أربعة ألوان إجمالاً. يمكن تلوين فرنسا وهولندا بلون واحد، لكن لوكسمبورغ تتطلب لونًا خامسًا. ^{[ 39 ]}

انظر أيضاً

شبكة أبولو
نظرية الألوان الخمسة
تلوين الرسوم البيانية
نظرية غروتزش : الرسوم البيانية المستوية الخالية من المثلثات قابلة للتلوين بثلاثة ألوان.
مسألة هادويجر-نيلسون : كم عدد الألوان اللازمة لتلوين المستوى بحيث لا يكون لأي نقطتين على مسافة وحدة واحدة نفس اللون؟

ملحوظات

↑ من غونتييه (2008) : "التعريفات: الخريطة المستوية هي مجموعة من المجموعات الجزئية المنفصلة مثنى مثنى في المستوى، وتُسمى مناطق. الخريطة البسيطة هي خريطة تكون مناطقها مجموعات مفتوحة متصلة. تكون منطقتان في خريطة ما متجاورتين إذا كان لإغلاقيهما نقطة مشتركة ليست زاوية من زوايا الخريطة. تكون النقطة زاوية من زوايا الخريطة إذا وفقط إذا كانت تنتمي إلى إغلاقي ثلاث مناطق على الأقل. نظرية: يمكن تلوين مناطق أي خريطة مستوية بسيطة بأربعة ألوان فقط، بحيث يكون لأي منطقتين متجاورتين لونان مختلفان."
↑ سوارت (1980) .
↑ ويلسون (2014) ، 216-222.
↑ هدسون (2003) .
↑ توماس (1998 ، ص 849) ؛ ويلسون (2014) .
↑ هناك بعض المعتقدات الرياضية الشائعة التي تنسب إلى موبيوس ابتكار حدسية الألوان الأربعة، لكن يبدو أن هذا الاعتقاد خاطئ. انظر: بيغز، نورمان ؛ لويد، إي. كيث؛ ويلسون، روبن جيه. (1986)، نظرية الرسم البياني، 1736-1936 ، مطبعة جامعة أكسفورد، ص 116 ، ISBN 0-19-853916-9وماديسون ، إيزابيل (1897)، "ملاحظة حول تاريخ مسألة تلوين الخرائط"، نشرة الجمعية الأمريكية للرياضيات ، 3 (7): 257، doi : 10.1090/S0002-9904-1897-00421-9
↑ دونالد ماكنزي، ميكنة البرهان: الحوسبة والمخاطر والثقة (مطبعة معهد ماساتشوستس للتكنولوجيا، 2004) ص 103
↑ ويلسون (2014) ، ص 12.
↑ FG (1854) ؛ McKay (2012)
1 2 دي مورغان (مجهول)، أغسطس (14 أبريل 1860)، "فلسفة الاكتشاف، فصول تاريخية ونقدية. بقلم دبليو. ويول." ، الأثينيوم : 501-503
↑ WW Rouse Ball (1960) نظرية الألوان الأربعة ، في مقالات وتسليات رياضية، ماكميلان، نيويورك، ص 222-232.
↑ توماس (1998) ، ص 848.
↑ هيوود (1890) .
↑ تايت (1880) .
↑ هادويجر (1943) .
↑ ويلسون (2014) ، ص 139-142.
^ غاري تشارتراند وليندا ليسنياك، الرسوم البيانية والرسوم البيانية (مطبعة CRC، 2005) ص. 221
↑ ويلسون (2014) ، ص 145-146.
^ ويلسون (2014 ، ص 105 – 107) ؛ ابيل وهاكن (1989) ; توماس (1998 ، ص 852-853)
1 2 أبيل وهاكن (1989) .
1 2 ويلسون (2014) ، ص. 153.
↑ ويلسون (2014) ، ص 150.
↑ ويلسون (2014) ، ص 157.
↑ ويلسون (2014) ، ص 161-162.
1 2 ويلسون (2014) ، ص. 165.
↑ توماس (1995) ؛ روبرتسون وآخرون (1996) .
↑ توماس (1998) ، ص 852-853.
↑ توماس (1999) ؛ بيج وآخرون (2002) .
↑ غونتييه (2008) .
↑ دايلي، د.ب. (1980)، "تفرد قابلية التلوين وقابلية تلوين الرسوم البيانية المستوية المنتظمة من الدرجة 4 هي مسألة NP-كاملة"، الرياضيات المتقطعة ، 30 (3): 289-293 ، doi : 10.1016/0012-365X(80)90236-8
↑ شتاينبرغ، ريتشارد (1993)، "حالة مشكلة الألوان الثلاثة"، في جيمبل، جون؛ كينيدي، جون دبليو؛ كوينتاس، لويس في (محررون)، إلى أين تتجه نظرية الرسم البياني؟، حوليات الرياضيات المتقطعة، المجلد 55، أمستردام: نورث هولاند، الصفحات 211-248 ، doi : 10.1016/S0167-5060(08)70391-1 ، ISBN 978-0-444-89441-0MR 1217995
↑ رينجل (1974) .
↑ جيثنر، إيلين (2018)، "إلى القمر وما وراءه"، في جيرا، رالوكا ؛ هاينز، تيريزا دبليو ؛ هيديتنييمي، ستيفن تي (محررون)، نظرية الرسم البياني: التخمينات المفضلة والمسائل المفتوحة، الجزء الثاني ، كتب مسائل في الرياضيات، دار نشر سبرينغر الدولية، الصفحات 115-133 ، doi : 10.1007/978-3-319-97686-0_11 ، ISBN 978-3-319-97684-6MR 3930641
↑ ويلسون (2014) ، ص 15.
↑ ريد وألرايت 2008 ؛ ماجنانت ومارتن (2011)
↑ بار-ناتان (1997) .
↑ ويلسون (2014) ، 2.
↑ ويلسون (2014) ، 6.
↑ كوكسيتر، إتش إس إم (صيف 1971)، "رياضيات تلوين الخرائط"، ليوناردو ، 4 (3): 273-277 ، doi : 10.2307/1572306 ، JSTOR 1572306

مراجع

ألاير، فرانك (1978)، "برهان آخر لنظرية الألوان الأربعة. الجزء الأول."، في د. مكارثي؛ هـ. س. ويليامز (محرران)، وقائع المؤتمر السابع لمانيتوبا حول الرياضيات العددية والحوسبة، المجلد 20، وينيبيغ، مانيتوبا: دار نشر يوتيليتاس ماثيماتيكا، الصفحات 3-72 ، رقم ISBN 0-919628-20-6MR 0535003
أبيل، كينيث ؛ هاكن، وولفغانغ (1977)، "كل خريطة مستوية قابلة للتلوين بأربعة ألوان. الجزء الأول: التفريغ"، مجلة إلينوي للرياضيات ، 21 (3): 429-490 ، doi : 10.1215/ijm/1256049011 ، MR 0543792
أبيل، كينيث ؛ هاكن، وولفغانغ ؛ كوخ، جون (1977)، "كل خريطة مستوية قابلة للتلوين بأربعة ألوان. الجزء الثاني: قابلية الاختزال"، مجلة إلينوي للرياضيات ، 21 (3): 491-567 ، doi : 10.1215/ijm/1256049012 ، MR 0543793
أبيل، كينيث ؛ هاكن، وولفغانغ (أكتوبر 1977)، "حل مشكلة الخريطة ذات الألوان الأربعة"، مجلة ساينتفك أمريكان ، المجلد 237، العدد 4، الصفحات 108-121 ، رمز Bibcode : 1977SciAm.237d.108A ، doi : 10.1038/scientificamerican1077-108
أبيل، كينيث ؛ هاكن، وولفغانغ (1989)، كل خريطة مستوية قابلة للتلوين بأربعة ألوان ، الرياضيات المعاصرة، المجلد 98، بالتعاون مع ج. كوخ، بروفيدنس، رود آيلاند: الجمعية الرياضية الأمريكية، doi : 10.1090/conm/098 ، ISBN 0-8218-5103-9، MR 1025335 ، S2CID 8735627
بار-ناتان، درور (1997)، "جبر لي ونظرية الألوان الأربعة"، كومبيناتوريكا ، 17 (1): 43-52 ، arXiv : q-alg/9606016 ، doi : 10.1007/BF01196130 ، MR 1466574 ، S2CID 2103049
برنهارت، فرانك ر. (1977)، "ملخص لنظرية الألوان الأربعة"، مجلة نظرية الرسم البياني ، المجلد 1، العدد 3، الصفحات 207-225 ، doi : 10.1002/jgt.3190010305 ، MR 0465921
بورودين، أو. في. (1984)، "حل مسألة رينجل حول تلوين رؤوس ووجوه الرسوم البيانية المستوية وتلوين الرسوم البيانية المستوية من الدرجة 1"، Metody Diskretnogo Analiza (41): 12– 26، 108، MR 0832128
كايلي، آرثر (1879)، "حول تلوين الخرائط"، وقائع الجمعية الجغرافية الملكية ، 1 (4)، دار بلاكويل للنشر: 259-261 ، doi : 10.2307/1799998 ، JSTOR 1799998
فريتش، رودولف؛ فريتش، غيردا (1998)، نظرية الألوان الأربعة: التاريخ، والأسس الطوبولوجية، وفكرة البرهان ، ترجمة جولي بيشكه عن النسخة الألمانية الأصلية لعام 1994، نيويورك: سبرينغر، doi : 10.1007/978-1-4612-1720-6 ، ISBN 978-0-387-98497-1MR 1633950
FG (10 يونيو 1854)، "تلوين الخرائط" ، الأثينيوم : 726
جيثنر، إي .؛ سبرينغر، دبليو إم (2003)، "ما مدى خطأ برهان كيمب لنظرية الألوان الأربعة؟"، كونغرس نومر ، 164 : 159-175 ، MR 2050581 ، Zbl 1050.05049
جيثنر، إيلين ؛ كاليتشاندا، بوبانا؛ مينتيس، ألكسندر س. (2009)، "ما مدى خطأ برهان كيمبي لنظرية الألوان الأربعة؟ الجزء الثاني"، Involve ، 2 (3): 249-265 ، doi : 10.2140/involve.2009.2.249
غونتييه، جورج (2005)، برهان مُدقَّق حاسوبيًا لنظرية الألوان الأربعة (ملف PDF) ، غير منشور، مؤرشف (ملف PDF) من الأصل بتاريخ 2017-09-08
غونتييه، جورج (2008)، "برهان رسمي - نظرية الألوان الأربعة" (ملف PDF) ، إشعارات الجمعية الرياضية الأمريكية ، 55 (11): 1382-1393 ، MR 2463991 ، مؤرشف (ملف PDF) من الأصل بتاريخ 2011-08-05
هادويغر، هوغو (1943)، “Über eine Klassifikation der Streckenkomplexe”، Vierteljschr. ناتورفورش. جيز. زيورخ ، 88 : 133- 143
هيوود، بي جيه ( 1890)، "نظرية لون الخريطة"، المجلة الفصلية للرياضيات البحتة والتطبيقية، أكسفورد ، المجلد 24، الصفحات 332-338
هادسون، هاد (مايو 2003)، "أربعة ألوان لا تكفي"، المجلة الرياضية الأمريكية الشهرية ، 110 (5): 417-423 ، doi : 10.2307/3647828 ، JSTOR 3647828
كيمب، أ.ب. (1879)، "حول المسألة الجغرافية للألوان الأربعة"، المجلة الأمريكية للرياضيات ، 2 (3): 193-220 ، doi : 10.2307/2369235 ، JSTOR 2369235
ماغنانت، سي.؛ مارتن، دي إم (2011)، "تلوين الكتل المستطيلة في الفضاء ثلاثي الأبعاد"، مناقشات الرياضيات في نظرية الرسم البياني ، 31 (1): 161-170 ، doi : 10.7151/dmgt.1535
مكاي، بريندان د. (2012)، ملاحظة حول تاريخ حدسية الألوان الأربعة ، arXiv : 1201.2852 ، Bibcode : 2012arXiv1201.2852M
ناش-ويليامز، سي. سانت جيه إيه (1967)، "الرسوم البيانية اللانهائية - دراسة استقصائية"، مجلة نظرية التوافيق ، 3 (3): 286-301 ، doi : 10.1016/s0021-9800(67)80077-2 ، MR 0214501
أوكونور؛ روبرتسون (1996)، نظرية الألوان الأربعة ، أرشيف ماك تيوتور ، مؤرشف من الأصل بتاريخ 16 يناير 2013 ، تم استرجاعه بتاريخ 5 أغسطس 2001
بيج، إد الابن ؛ ميلينديز، ج.؛ بيرينغير، ر.؛ سيندرا، الابن؛ هيرنانديز، أ.؛ ديل بينو، ج. (2002)، "مراجعة كتاب: كتاب الرياضيات الضخم" (ملف PDF) ، إشعارات الجمعية الأمريكية للرياضيات ، 49 (9): 1084-1086 ، مؤرشف (ملف PDF) من الأصل بتاريخ 9 أبريل 2003
ريد، بروس ؛ أولرايت، ديفيد (2008)، "طلاء المكتب" ، دراسات حالة الرياضيات في الصناعة ، 1 : 1-8 ، مؤرشف من الأصل في 2013-02-03 ، تم استرجاعه في 2011-07-11
Ringel، G. (1974)، نظرية لون الخريطة ، نيويورك – برلين: Springer-Verlag
رينجل، ج .؛ يونغز، ج. و. ت. (1968)، "حل مسألة تلوين خرائط هيوود"، وقائع الأكاديمية الوطنية للعلوم في الولايات المتحدة الأمريكية ، المجلد 60، العدد 2، الصفحات 438-445 ، رمز Bibcode : 1968PNAS...60..438R ، doi : 10.1073/pnas.60.2.438 ، PMC 225066 ، PMID 16591648
روبرتسون، نيل ؛ ساندرز، دانيال ب .؛ سيمور، بول ؛ توماس، روبن (1996)، "تلوين الرسوم البيانية المستوية بأربعة ألوان بكفاءة"، وقائع الندوة الثامنة والعشرين لجمعية الحوسبة الآلية حول نظرية الحوسبة (STOC 1996) ، الصفحات 571-575 ، doi : 10.1145/237814.238005 ، ISBN 0-89791-785-5، MR 1427555 ، S2CID 14962541
روبرتسون، نيل ؛ ساندرز، دانيال ب .؛ سيمور، بول ؛ توماس، روبن (1997)، "نظرية الألوان الأربعة"، مجلة نظرية التوافيق، السلسلة ب، المجلد 70، العدد 1، الصفحات 2-44 ، doi : 10.1006/jctb.1997.1750 ، MR 1441258
ساعاتي، توماس ؛ كاينن، بول (1986)، مشكلة الألوان الأربعة: الهجمات والغزو ، نيويورك: منشورات دوفر، ISBN 0-486-65092-8
سوارت، إدوارد رينير (1980)، "الآثار الفلسفية لمسألة الألوان الأربعة" ، المجلة الرياضية الأمريكية الشهرية ، المجلد 87، العدد 9، الجمعية الرياضية الأمريكية، الصفحات 697-702 ، doi : 10.2307/2321855 ، JSTOR 2321855 ، MR 0602826
توماس، روبن (1998)، "تحديث لنظرية الألوان الأربعة" (ملف PDF) ، إشعارات الجمعية الرياضية الأمريكية ، المجلد 45، العدد 7، الصفحات 848-859 ، MR 1633714 ، مؤرشف (ملف PDF) من الأصل بتاريخ 29-09-2000
توماس، روبن (1995)، نظرية الألوان الأربعة
Tietze، Heinrich (1910)، “ Einige Bemerkungen über dasproblem des Kartenfärbens auf einseitigen Flächen ” [ بعض الملاحظات حول مشكلة تلوين الخرائط على الأسطح ذات الجانب الواحد ] ، Jahresbericht der Deutschen Mathematiker-Vereinigung ، 19 : 155– 159
توماس، روبن (1999)، "نظريات الاستبعاد الصغرى الحديثة للرسوم البيانية"، في لامب، جون د.؛ بريس، د.أ. (محرران)، دراسات في التوافقية، 1999 ، سلسلة محاضرات جمعية لندن الرياضية، المجلد 267، كامبريدج: مطبعة جامعة كامبريدج، الصفحات 201-222 ، doi : 10.1017/CBO9780511721335 ، ISBN 0-521-65376-2MR 1725004
تايت، بي جي (1880)، "ملاحظات حول تلوين الخرائط"، وقائع الجمعية الملكية في إدنبرة ، 10 : 729، doi : 10.1017/S0370164600044643
ويلسون، روبن (2014) [2002]، أربعة ألوان تكفي ، مكتبة برينستون للعلوم، برينستون، نيو جيرسي: مطبعة جامعة برينستون، رقم ISBN 978-0-691-15822-8MR 3235839
ويلسون، روبن؛ واتكينز، جون جيه؛ باركس، ديفيد جيه (17 يناير 2023)، نظرية الرسم البياني في أمريكا ، برينستون أكسفورد: مطبعة جامعة برينستون، رقم ISBN 978-0-691-19402-8

روابط خارجية

"مسألة الألوان الأربعة" ، موسوعة الرياضيات ، دار نشر EMS ، 2001 [1994]
ويلسون، روبن (مارس 2026). "نظرية الألوان الأربعة: 1852-1976" (ملف PDF) . إشعارات الجمعية الرياضية الأمريكية . 73 (3): 216-228 . doi : 10.1090/noti3305 .
قائمة بتعميمات نظرية الألوان الأربعة على موقع MathOverflow

[1] من غونتييه (2008) : "التعريفات: الخريطة المستوية هي مجموعة من المجموعات الجزئية المنفصلة مثنى مثنى في المستوى، وتُسمى مناطق. الخريطة البسيطة هي خريطة تكون مناطقها مجموعات مفتوحة متصلة. تكون منطقتان في خريطة ما متجاورتين إذا كان لإغلاقيهما نقطة مشتركة ليست زاوية من زوايا الخريطة. تكون النقطة زاوية من زوايا الخريطة إذا وفقط إذا كانت تنتمي إلى إغلاقي ثلاث مناطق على الأقل. نظرية: يمكن تلوين مناطق أي خريطة مستوية بسيطة بأربعة ألوان فقط، بحيث يكون لأي منطقتين متجاورتين لونان مختلفان."

[FOOTNOTESwart1980-2] سوارت (1980) .

[FOOTNOTEWilson2014216–222-3] ويلسون (2014) ، 216-222.

[FOOTNOTEHudson2003-4] هدسون (2003) .

[5] توماس (1998 ، ص 849) ؛ ويلسون (2014) .

[6] هناك بعض المعتقدات الرياضية الشائعة التي تنسب إلى موبيوس ابتكار حدسية الألوان الأربعة، لكن يبدو أن هذا الاعتقاد خاطئ. انظر: بيغز، نورمان ؛ لويد، إي. كيث؛ ويلسون، روبن جيه. (1986)، نظرية الرسم البياني، 1736-1936 ، مطبعة جامعة أكسفورد، ص 116 ، ISBN 0-19-853916-9وماديسون ، إيزابيل (1897)، "ملاحظة حول تاريخ مسألة تلوين الخرائط"، نشرة الجمعية الأمريكية للرياضيات ، 3 (7): 257، doi : 10.1090/S0002-9904-1897-00421-9

[MacKenzie-7] دونالد ماكنزي، ميكنة البرهان: الحوسبة والمخاطر والثقة (مطبعة معهد ماساتشوستس للتكنولوجيا، 2004) ص 103

[FOOTNOTEWilson201412-8] ويلسون (2014) ، ص 12.

[9] FG (1854) ؛ McKay (2012)

[Athenaeum1860-10] 1 2 دي مورغان (مجهول)، أغسطس (14 أبريل 1860)، "فلسفة الاكتشاف، فصول تاريخية ونقدية. بقلم دبليو. ويول." ، الأثينيوم : 501-503

[rouse_ball_1960-11] WW Rouse Ball (1960) نظرية الألوان الأربعة ، في مقالات وتسليات رياضية، ماكميلان، نيويورك، ص 222-232.

[FOOTNOTEThomas1998848-12] توماس (1998) ، ص 848.

[FOOTNOTEHeawood1890-13] هيوود (1890) .

[FOOTNOTETait1880-14] تايت (1880) .

[FOOTNOTEHadwiger1943-15] هادويجر (1943) .

[FOOTNOTEWilson2014139–142-16] ويلسون (2014) ، ص 139-142.

[17] غاري تشارتراند وليندا ليسنياك، الرسوم البيانية والرسوم البيانية (مطبعة CRC، 2005) ص. 221

[FOOTNOTEWilson2014145–146-18] ويلسون (2014) ، ص 145-146.

[19] ويلسون (2014 ، ص 105 – 107) ؛ ابيل وهاكن (1989) ; توماس (1998 ، ص 852-853)

[FOOTNOTEAppelHaken1989-20] 1 2 أبيل وهاكن (1989) .

[FOOTNOTEWilson2014153-21] 1 2 ويلسون (2014) ، ص. 153.

[FOOTNOTEWilson2014150-22] ويلسون (2014) ، ص 150.

[FOOTNOTEWilson2014157-23] ويلسون (2014) ، ص 157.

[FOOTNOTEWilson2014161–162-24] ويلسون (2014) ، ص 161-162.

[FOOTNOTEWilson2014165-25] 1 2 ويلسون (2014) ، ص. 165.

[26] توماس (1995) ؛ روبرتسون وآخرون (1996) .

[FOOTNOTEThomas1998852–853-27] توماس (1998) ، ص 852-853.

[28] توماس (1999) ؛ بيج وآخرون (2002) .

[FOOTNOTEGonthier2008-29] غونتييه (2008) .

[30] دايلي، د.ب. (1980)، "تفرد قابلية التلوين وقابلية تلوين الرسوم البيانية المستوية المنتظمة من الدرجة 4 هي مسألة NP-كاملة"، الرياضيات المتقطعة ، 30 (3): 289-293 ، doi : 10.1016/0012-365X(80)90236-8

[31] شتاينبرغ، ريتشارد (1993)، "حالة مشكلة الألوان الثلاثة"، في جيمبل، جون؛ كينيدي، جون دبليو؛ كوينتاس، لويس في (محررون)، إلى أين تتجه نظرية الرسم البياني؟، حوليات الرياضيات المتقطعة، المجلد 55، أمستردام: نورث هولاند، الصفحات 211-248 ، doi : 10.1016/S0167-5060(08)70391-1 ، ISBN 978-0-444-89441-0MR 1217995

[FOOTNOTERingel1974-32] رينجل (1974) .

[33] جيثنر، إيلين (2018)، "إلى القمر وما وراءه"، في جيرا، رالوكا ؛ هاينز، تيريزا دبليو ؛ هيديتنييمي، ستيفن تي (محررون)، نظرية الرسم البياني: التخمينات المفضلة والمسائل المفتوحة، الجزء الثاني ، كتب مسائل في الرياضيات، دار نشر سبرينغر الدولية، الصفحات 115-133 ، doi : 10.1007/978-3-319-97686-0_11 ، ISBN 978-3-319-97684-6MR 3930641

[FOOTNOTEWilson201415-34] ويلسون (2014) ، ص 15.

[35] ريد وألرايت 2008 ؛ ماجنانت ومارتن (2011)

[FOOTNOTEBar-Natan1997-36] بار-ناتان (1997) .

[FOOTNOTEWilson20142-37] ويلسون (2014) ، 2.

[FOOTNOTEWilson20146-38] ويلسون (2014) ، 6.

[39] كوكسيتر، إتش إس إم (صيف 1971)، "رياضيات تلوين الخرائط"، ليوناردو ، 4 (3): 273-277 ، doi : 10.2307/1572306 ، JSTOR 1572306

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[

[

[

[ 29 ]

[

] في مثال

[ 32 ]

[

[

[

[ 36 ]

[ 37 ]

[ 38 ]

[ 39 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗