برهنة الألوان الأربعة
الموضوع الذي اقترحه جورج Gonthier
Georges.Gonthier @ inria.fr
مبرهنة الألوان الأربعة هي واحدة من الرياضيات المشهورة اندماجي. على الرغم من بيان بسيط ، مبرهنة هو حدس ظلت لأكثر من قرن ، تم خلالها تناول كبار علماء الرياضيات ، وأحيانا مع كاذبة. بالإضافة إلى ذلك ، يتضمن القرار 1976 ، طويلة الكمبيوتر حساب ، ولذا كان بالتالي مثيرة للجدل ، فإن معظم علماء الرياضيات ليست قادرة على التحقق من دقة البرامج المستخدمة. تكنولوجيا المعلومات في هذا المشروع ، فإننا نقترح إعادة فحص هذه الأدلة مع الوسائل الحديثة ، بدءا من دليل مبسط في وقت لاحق.


قليلا من التاريخ وكانت النتيجة محدوس في 1852 بقلم فرانسيس غوثري ، المهتمة في خريطة ملونة للمناطق انكلترا. ونشرت لأول مرة مواعيد مرجعية من عام 1879 ، ومع ذلك [2]. مظاهرتين نشرت للمرة الاولى على التوالي من قبل ألفريد كيمبي في عام 1879 من قبل بيتر غوثري تيت في عام 1880. لكنها تثبت غير صحيح ، وقد تم تحديد أخطاء فقط في عام 1890 من قبل وHeawood بيرسي في عام 1891 من قبل جوليوس بيترسن.

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

في السنوات 1960 و 1970 ، هاينريش Heesch المهتمين في إمكانية حسابيا اثبات نظرية الألوان الأربعة. أخيرا ، في عام 1976 ، ان اثنين من الامريكيين كينيث ابيل وولفغانغ Haken انها عثرت على أربع نظرية الألوان. مظاهرتهم مشاركة المجتمع العلمي لأول مرة ، في الواقع ، في مظاهرة يتطلب استخدام أجهزة الكمبيوتر لدراسة الحالات الحرجة في 1478 (أكثر من 1200 ساعة من الحساب). مشكلة التحقق من صحة نظرية ثم انتقل إلى مشكلة المصادقة :

على حصة من خوارزمية ؛
ثانيا إعماله كبرنامج.
منذ عام 1976 ، وقد كرر الخوارزمية لابيل وHaken وتبسيط روبرتسون ، ساندرز ، وتوماس سيمور [3]. برامج حاسوبية أخرى مكتوبة بشكل مستقل عن الأول ، العائد نفس النتيجة. وبالتالي هناك طابع رسمي تماما ، تقدم مع الديك من قبل جورج Gonthier وبنيامين فيرنر ، والذي يسمح لجهاز كمبيوتر تماما التحقق من نظرية الألوان الأربعة.

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

تعميمات من مبرهنة الألوان الأربعة دروس من الرسوم البيانية أعم من الرسوم البيانية مستو نحن نرى أن البيان الكلاسيكي لنظرية الألوان الأربعة ومن الواضح ان ليس لتوصيف عدد من الرسوم البيانية لوني الذي هو أقل من أو يساوي 4 منذ K3 (3) ، لا بل هو مستو الثنائية. من ناحية أخرى ، لأسباب من التعقيد الحسابي ، يمكن أن يكون هناك توصيف بسيط من الرسوم البيانية ملون ك ك ثابتة لأكثر من 3. اربع نظرية اللون يعمم على الرسوم البيانية مع أي K5 طفيفة ، إذ أن عدد وني من هذه المخططات هي في أغلبها 4 (و هو أحد الدوافع لحدس من Hadwiger). والتعميم أقوى منحت مؤخرا Guenin :

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

على الفور تقريبا ، في عام 1879 ، كيمبي Prmiere هو حدس »proof''of ، ولكن أحد عشر عاما في وقت لاحق Heawood سوف تجد خطأ كبيرا ، الا انه نجح في إنقاذ خمسة نظرية الألوان. والثانية «تيت proof''by في عام 1880 سوف يتم حتى تدحضه بيترسن في 1891.

في عام 1913 ، والد علم الجبر الحديث ، G. د. Birkhoff ، صياغة مفهوم التكوين للاختزال ، ويدل على التخمين بالنسبة لجميع بطاقات مع أقل من 26 مناطق في اللون. هذه المحطة هي تحسنت خلال القرن العشرين في ظل ظروف 1969 Heesch هي »almost''necessary وكافية لتكوين هو اختزال ، وطريقة عامة للعثور على مجموعة من تكوينات لا مفر منه.

أخيرا ، في عام 1976 ، وابيل Haken تحقيق Heesch البرنامج ، وتظهر عشرات الآلاف من الأرقام إلى أن أي دعم بطاقة 4 - ملون لا يجب أن تحتوي على واحد من 1478 تكوينات ، ومع 1200 ساعة الحساب أن كل من هذه التشكيلات هي اختزال.

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


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


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

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

خريطة التحول - الرسم البياني هو في الواقع ازدواجية. في الواقع ، فإن »road''of رسم مستو أيضا تحديد مجالات الخطة ، ودعا وجوه من الرسم البياني والرسم البياني للبطاقة وجوه لا شيء غير... الرسم على الحدود الخارجية للبطاقة الأصلي!

نلاحظ أنه قد يكون مقصورا على تلوين الرسوم البيانية لتوصيل مثلث ، حيث كل وجه تحده بالضبط ثلاثة طرق (بما في ذلك الوجه الذي يحيط انهائي الرسم البياني بأكمله). في الواقع ، يمكن للمرء الحصول على مثلث الرسم البياني جيكا طن من مجموعة الرسم البياني عن طريق إزالة أي الطرق الموازية ، واضاف ن 3 أقطار ن كل الطرق في انحاء المنطقة gonal (ن ³ 4) ، ثم كل 4 --تلوين جي تي هو ايضا 4 - التلوين من G.


1.2 وصيغة أويلر
و عدد من وجوه رسم بياني متصل مستو زاي يمكن أن يحسب في واقع الأمر من ن عدد من القمم (المدن) وحواف م (الطرق) للمجموعة ، وذلك باستخدام صيغة أويلر : n - m + f = 2
وهو ما يظهر بسهولة عن طريق الحث على m.
كيمبي تستخدم هذه الصيغة على النحو التالي : كل حافة مع اثنين من الغايات ، ودرجة (حواف عدد من الحادث) باستخدام قنة هو3f=2m, وبالتالي

d = 6 - 12n< 6
لذا فإن هناك درجة من قمة الرأس خ د كحد أقصى 5 في G. كيمبي والفكرة هي أن نفترض أن جي إكس عن طريق الحث هو 4 - ملون ، ومحاولة لتمديد 4 - التلوين للجي اكس في التلوين من G.
قنوات كيمبي
إذا كان التلوين في جي إكس جيران خ لا تستخدم أربعة ألوان ، ببساطة تعيين س إلى واحد من الألوان المستخدمة ليست بالضرورة حالة إذا د = 3. على خلاف ذلك ، فإنه من الضروري تغيير التلوين للجي إكس ؛ كيمبي درس الشروط التي بموجبها يمكن القيام بذلك.

النظر في الرسم البياني (مستو) ح 4 اللون الازرق والاصفر والاحمر والابيض. إذا كانت هناك قمة الرأس لونها أزرق ، ودعا كيمبي سلسلة الأزرق الأصفر ذ ض طريقا في لحاء من ذ ض التي المناوبين الألوان الأزرق والأصفر والأزرق والأصفر والأزرق... والأصفر مكون ذ ه من مجموعة 'لجميع لجميع القمم ض ح من هذا القبيل أن هناك سلسلة من الأزرق والأصفر كيمبي ذ لz.

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

في الواقع ، وبلاناريتي من مجموعة واحدة يعني أنه يمكن دائما العثور على التحول الذي التغييرات غير الجيران اللون تافهة من قمة الرأس x. على سبيل المثال ، افترض أن لديه أربعة خ الجيران x0 ، x1 ، x2 ، x3 ، التي هي على التوالي الأزرق والأحمر والأصفر والأبيض في 4 - التلوين من الارتفاع = جي إكس. النظر في الزرقاء x0 الصفراء ؛ فإنه لا تحتوي على أي x1 أو x3.اذا لم x2 ، ثم عكس ذلك يضع x0 الصفراء دون لمس x1 ، x2 ، x3 ، ثم تطلق سراح x. الزرقاء على خلاف ذلك ، هناك سلسلة من كيمبي الأزرق والأصفر x0 لx2. إذا كان هناك سلسلة من البيض حمراء x3 لx1 ، وقالت انها قطع من x0 لx2 ، منذ حاء مستو ، وهو أمر مستحيل. حتى عكس الحمراء البيضاء المكون من x3 ، فمن x3 الحمراء دون تغيير x0 ، x1 ، x2 ، وتحرير x. بيضاء


1.4 والحجة وتفنيد
كيمبي الحجة التي تتلخص بالتالي :
ويظهر رسم بياني مع أربعة القمم هو مسلي 4 - ملون.
والرسم البياني الثلاثي مجموعة تحتوي على أكثر بالضرورة على درجة من قمة الرأس خ د 5 جنيهات استرلينية.
يمكننا أن نفترض أنه إذا كان الارتفاع = جي اكس هو 4 - الملونة عن طريق الحث
إذا كان التلوين من الجيران لا يستخدم اللون ، فإنه يسند إلى x.
وإلا ، فإننا دراسة سلاسل كيمبي في حاء ، وهناك العكس التي تنتج لونا لx.
لتقع في هذه الحالة الأخيرة ، يجب أن يكون لدينا د = 4 أو 5 سنوات. رأينا في قضية د = 4 أعلاه. لد = 5 ، كيمبي عرضت على المنطق التالي :
اسمحوا x0 ، x1 ، x2 ، x3 ، x4 جيران x. مودولو التناظر ، يجوز لنا أن نفترض أن x1 وx3 هم من البيض ، وx0 ، x2 ، x4 التوالي الأزرق والأصفر والأحمر. إذا لم يكن هناك سلسلة من الأزرق والأصفر x2 x0 ، ثم نعكس الأصفر الأزرق المكون من x2 ، التي تصدر في العاشر الزرقاء نشرع حتى إذا لم يكن هناك سلسلة الصفراء الحمراء x2 x4. على خلاف ذلك ، x1 وx3 ليست سوى عناصر في الحمراء والبيضاء والزرقاء والبيضاء ، فإنه يكفي لوقف لاطلاق سراح x. بيضاء
الخطأ هنا هو أن سلاسل x2 -- x0 وx2 -- x4 قد تتقاطع ، بحيث مكونات x1 وx3 ليست بالضرورة منفصلة ، وبالتالي ليست بالضرورة في وقت واحد قابل للعكس. في الواقع ، أظهرت Heawood قمم الرسم البياني في 25 ، والتي لم نقض على العناصر التالية جيران خ لا لون لاطلاق سراح x.


2 تكوينات للاختزال
البرهان الحقيقي للنظرية الألوان الأربعة التالي بالضبط خطة الوسيطة (كاذبة) كيمبي ، مع فارق واحد مهم : فهو يسمح على شكل تعسفي لل»G''piece يتم إزالة للتكرار ، و بدلا من أن تكون مقتصرة على قمة الرأس واحد العاشر من درجة 3 أو 4 أو 5. مثل قطعة من الرسم البياني يسمى التكوين.

خطة الاثبات هو العثور على مجموعة محدودة من تكوينات كاف بأن أمر لا مفر منه ، وهذا يعني ، أن كل هذا الرسم البياني 4 - ملون لا تحتوي على نسخة من احد كي كاف ؛ حتمية يتجلى حتى مع صيغة أويلر ، من خلال نشر فينلي (في 1 / 10!) درجة 12 في عداد المفقودين ، حسب قواعد »التصريف« (ابيل وHaken كان 300 ، روبرتسون ، ساندرز ، وتوماس سيمور فقط 32 ).

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

والغرض من هذا المشروع هو للتحقق من هذا الجزء الثاني من الأدلة ، مع تكوينات 633 من روبرتسون ، ساندرز ، وتوماس سيمور.


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

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


مبرهنة 1 [تيت 1880] وهذه المناطق من الخريطة المكعب 4 - ملون إذا وفقط إذا كانت قطاعات هي tricoloriables الحدود.

في الواقع ، إذا كان أحد لديه 4 - خريطة ملونة مكعب مع ثلاثة ألوان أساسية (الأحمر والأصفر والأزرق) ، وبيضاء اللون »magic''we يستطيع كل جزء مع مزج الألوان المناطق التي فإنه يفصل. إذا خلط أساسي مع السحر الأبيض يعطي المكمل لها (على سبيل المثال ، أحمر أخضر = السحر) ، والذي يمزج الأولية للمرحلة الابتدائية اتباع القواعد المعتادة (على سبيل المثال ، أزرق + أصفر = أخضر) نجد أن نحصل على بطاقة جيدة tricoloriage مع ثلاثة ألوان الثانوية (الأخضر والبرتقالي والأرجواني). على العكس ، عندما وضعنا هذا اللون من المنطقة لانهائي ، مثل قطاعات tricoloriage أدت خطوة بخطوة واحدة 4 - التلوين من المناطق.

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


2.2 تكوينات
منذ عام ونحن نعمل مع الخرائط ، وسوف تكوينات شظية الخريطة. رسميا لحاء خريطة تفتيت هو تقاطع جيم بطاقة مع مد المجال ، وهي المنطقة التي تتصل بالحدود لا يمر من خلال أي فرع من فروع C. وهناك قطعة بالتالي يشمل المناطق الجزئية التي هي محاطة جزئيا في منطقة الحدود ، حتى أنها يمكن أن تحتوي على نصف شرائح التي تتصل نقطة تقاطع في منطقة الحدود ، و / أو الحبال التي تربط مباشرة بين نقطتين المنطقة الحدودية. النقاط في الحد من مد والتي تنتهي من الحبال أو نصف شرائح شكل واجهة لحاء حاء في عدد من النقاط لحاء يسمى حدود H.

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

نحن نقول ان جيم خريطة يحتوي على نسخة من كاف لتكوين في حال وجود مجال مد ان هذه القطعة جيم دال هو homeomorphic إلى K. في ما يلي سنقوم بتحديد فقط جيم ودال K. هذا التقسيم كما يعرف مكملة شظية كورونا جيم جيم = (R2 -- دال) ، التي تملك واجهة نفس جيم دال = ك.

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


2.3 chromogrammes
يعطى ك التكوين ، والتي تحتوي على الخريطة جيم كاف ، نحصل على الخريطة جيم 'أصغر بالاستعاضة ك ك جزء من' واجهة نفسها ولكنه أصغر حجما (على سبيل المثال ، عن طريق إزالة جزء من كاف) تقييد لC' - ك '= كورونا وجيم tricoloriage' الحث على tricoloriage كورونا تشيكية. من الواضح ، إذا ما هو كاف للاختزال لكل زوج من التلوين هناك ك tricoloriage الذي يدفع ز ز د على كاف = = كورونا : فقط ثم اختيار ز و د الحصول على C. tricoloriage

للأسف ، هذا صحيح فقط لتكوينات من محيط 3. ولذلك فمن الضروري تغيير د باستخدام واحد أو أكثر العكس كيمبي ، ومن ثم التفكير المنهجي على ما قمنا به من قمة الرأس لدرجة 4 في 1.3. فإنه يتجنب الخطأ في كيمبي المقلوب في وقت واحد كما بطبيعتها مكونات منفصلة ، على سبيل المثال زرقاء وصفراء أو حمراء وبيضاء واحدة تتحدث عن انقلاب في هذه القضية الخضراء. عبر جميع التلوين التي يمكن الحصول عليها عن طريق انعكاس (الأخضر أو البرتقالي أو الأرجواني) ، والتي تعتمد على طبولوجيا من القرص المدمج ويمكن تلخيص ذلك من قبل chromogramme بسيطة جدا.

والعاشر chromogramme هو مجرد قطعة من البطاقات التي تحتوي على سلاسل فقط ، والتي هي ملونة مع اثنين من الألوان ، ```` pair''and غريبة «. لو كنت (الأخضر والبرتقالي والأرجواني) هو اللون الثانوي ، ونحن نقول ان (د) والعاشر هي متوافقة ، إذا وفقط إذا
العاشر هو مجموعة من النقاط من كاف التي ليس لديها للطبيعة ،
ج إذا سلسلة من العاشر مع النهاية خ ، ذ ، ثم د (س) = د (ذ) إذا وفقط إذا ج أمر غريب.
هذه التعريفات هي الدافع وراء النتيجة التالية :


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

نأخذ على سبيل المثال = الخضراء. اسمحوا ح 'الشظايا التي تم الحصول عليها عن طريق حذف حاء من جميع قطاعات وشرائح نصف الخضراء. س يتم الحصول عليها عن طريق حذف ح 'مفارق جميع المجالات الثنائية ومعزولة. كل سلسلة من العاشر ج هو سلسلة من الشرائح ك ونصف شرائح ، أو سلاسل من ح '، و» color''of ج هو التكافؤ بين n. منذ حاء مكعب ، وذلك بإزالة جزء من كل فرع الخضراء ، وحاء هو اتحاد مفكك الخطوط المنقطة من البرتقال ، الأرجواني ، وبالتالي هو العاشر chromogramme متوافقة مع د. س يعتمد فقط على الأجزاء الخضراء من د ، و هي ثابتة في ظل انعكاس الخضراء.

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


2.4 والقدرة على التخفيض
مسلح مع هذا التحليل ، يمكننا الآن أن الدولة لشروط القدرة على التخفيض كافية للبرهنة على نظرية الألوان الأربعة.

اسمحوا كاف يمكن تكوين كل شيء ، ك * ، والتلوين كاف متوافق مع مجموعة أصغر من 3 - التلوين كاف بحيث
ز إذا هو كاف tricoloriage ، ثم كاف * غي ،
إذا كان هناك لون الثانوية ، مثل أن كل العاشر chromodendron متوافق مع د ، توجد واحدة من ك ط * متوافق مع العاشر ، ثم دي ك *.
ك * يحتوي على التلوين ولذلك فمن الممكن دائما للحد من لتلوين كاف لسلسلة من الانتكاسات كيمبي ، وأنه مهما كانت تحتوي على طبولوجيا جيم K.

إذا كان يحتوي على جميع كاف * 3 - الأصباغ ممكن من كاف ، ثم نقول إن هو كاف مد للاختزال ، لأن عندها نستطيع التكيف مع أي حارس مرمى tricoloriage لتلوين كاف مع التغييرات ، والصمغ.

تكوينات الأكثر إثارة للاهتمام هي اختزال للأسف لم مد للاختزال ، لحسن الحظ ، لا يمكننا الابتعاد مع إجبار اختيار ك 'استبدال كاف في تكرارها. سنقدم العقد ك ، وهو حزمة صغيرة من 1 4 - صحيحة الجزء كاف QUE1 مثل هذه ليس هناك أكثر من جزء واحد من كل فرع من فروع ك ك. جيم هو ان يكون سي إن اختزال جميع كاف tricoloriage 'الحث على التلوين كاف *. في الواقع أحد tricoloriage بطاقة جيم 'التي تم الحصول عليها عن طريق حذف قطاعات ك جيم هو في العودة للانضمام لtricoloriage كورونا تشيكية وtricoloriage ه ك' ، بحيث د = ك * المنظمة الدولية للتعليم ، ويمكن أن نجد د 'ز وكما لمد القدرة على التخفيض.


3 العمل المطلوب
يجب إذن أن نجعل البرنامج الذي يتحقق من جانب القدرة على التخفيض من أربع مبرهنة الألوان :
وسوف يتم توفير 633 تكوينات في شكل ملف واحد أن البرنامج سوف يكون قادرا على القراءة.
التحقق من تطبيق البرنامج القدرة على التخفيض ثلاثة خوارزميات لإجراء الحسابات وصفها في 2.4 : حساب جميع ز ز ك tricoloriage ، في نفس ك 'إذا كان هناك عقد ، وأخيرا حساب ك * أو لتكملة.
يتم اختيار دقيق للهياكل البيانات والخوارزميات التي تستخدمها هذه الخوارزميات ، وخصوصا لحساب ك *. على وجه الخصوص ، استخدام التماثل اللون لتقسيم حجم بنسبة 6 مجموعات! مع خوارزميات الحق ، وهو برنامج مكتوب في سي ربما يعامل كل منهما التكوين في أقل من دقيقة.
الملف سوف تحتوي على إحداثيات تكوينات »pretty''available. كنت تشجع على استخدامها لعرض بعض الحسابات الخاصة بك وسيطة البرنامج. نتذكر أيضا لاختبار تكوينات برنامج لا تختزل سي (الفاحص سوف).
4 ملحقات
نوعان رئيسيان من ملحقات ممكنة :
نستنتج من إثبات نظرية خوارزمية ل4 - التلوين من الخريطة مستو في الوقت المناسب من الدرجة الثانية. يمكنك بناء (جزئيا) من لاختبار القدرة على التخفيض.
يمكنك إكمال العمل الخاص بك عن طريق جعل النصف الآخر من إثبات : حتمية.
المراجع
[RSST97]
ن. روبرتسون ، D. ساندرز ، P. سيمور ، R. توماس. ذات الالوان الاربعة نظرية. مجلة اندماجي نظرية ، المجموعة باء ، 70 (1997) ، ص. 2 حتي 44.
[AH89]
ك. ابيل ، W. Haken. كل خريطة مستو هو أربعة colourable. الرياضيات المعاصرة 98 (1989).
[SK77]
ت. ساعاتي ، P. Kainen. ذات الالوان الاربعة مشكلة ، والاعتداء والغزو. مكجراو هيل (1977).
الخريطة الإدارية لروسيا مع أربعة الملونة couleursLe أربع دول نظرية اللون أنه من الممكن ، إلا باستخدام أربعة ألوان مختلفة ، والتلوين ، [1] أي خفض البطاقة في المجالات ذات الصلة ، حتى ان اثنين من المناطق المجاورة (أو الحدود) ، وهذا يعني ، وجود حرس الحدود (وليس مجرد نقطة) في عام دائما اثنين من ألوان مختلفة. الصياغة قد تختلف ، ويؤثر ذلك تماما ما يعادلها ، ولون من وجوه متعدد الوجوه ، أو القمم من الرسم البياني مستو.

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

عندما تكون المشكلة يعمم على الرسم البياني التعسفي ، ويصبح أرستها - كاملة لتحديد ما إذا كان هو مجرد ملون مع 4 لونا (وحتى 3).
وكانت النتيجة محدوس في 1852 بقلم فرانسيس غوثري ، المهتمة في خريطة ملونة للمناطق انكلترا. ونشرت لأول مرة مواعيد مرجعية من عام 1879 ، ومع ذلك [2]. مظاهرتين نشرت للمرة الاولى على التوالي من قبل ألفريد كيمبي في عام 1879 من قبل بيتر غوثري تيت في عام 1880. لكنها تثبت غير صحيح ، وقد تم تحديد أخطاء فقط في عام 1890 من قبل وHeawood بيرسي في عام 1891 من قبل جوليوس بيترسن.

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

في السنوات 1960 و 1970 ، هاينريش Heesch المهتمين في إمكانية حسابيا اثبات نظرية الألوان الأربعة. أخيرا ، في عام 1976 ، ان اثنين من الامريكيين كينيث ابيل وولفغانغ Haken انها عثرت على أربع نظرية الألوان. مظاهرتهم مشاركة المجتمع العلمي لأول مرة ، في الواقع ، في مظاهرة يتطلب استخدام أجهزة الكمبيوتر لدراسة الحالات الحرجة في 1478 (أكثر من 1200 ساعة من الحساب). مشكلة التحقق من صحة نظرية ثم انتقل إلى مشكلة المصادقة :

على حصة من خوارزمية ؛
ثانيا إعماله كبرنامج.
منذ عام 1976 ، وقد كرر الخوارزمية لابيل وHaken وتبسيط روبرتسون ، ساندرز ، وتوماس سيمور [3]. برامج حاسوبية أخرى مكتوبة بشكل مستقل عن الأول ، العائد نفس النتيجة. وبالتالي هناك طابع رسمي تماما ، تقدم مع الديك من قبل جورج Gonthier وبنيامين فيرنر ، والذي يسمح لجهاز كمبيوتر تماما التحقق من نظرية الألوان الأربعة.

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

تعميمات من مبرهنة الألوان الأربعة [ دروس من الرسوم البيانية أعم من الرسوم البيانية مستو نحن نرى أن البيان الكلاسيكي لنظرية الألوان الأربعة ومن الواضح ان ليس لتوصيف عدد من الرسوم البيانية لوني الذي هو أقل من أو يساوي 4 منذ K3 (3) ، لا بل هو مستو الثنائية. من ناحية أخرى ، لأسباب من التعقيد الحسابي ، يمكن أن يكون هناك توصيف بسيط من الرسوم البيانية ملون ك ك ثابتة لأكثر من 3. اربع نظرية اللون يعمم على الرسوم البيانية مع أي K5 طفيفة ، إذ أن عدد وني من هذه المخططات هي في أغلبها 4 (و هو أحد الدوافع لحدس من Hadwiger). والتعميم أقوى منحت مؤخرا Guenin :

الرسوم البيانية بدون K5 طفيفة ونيف هي ملونة فقط مع 4 ألوان.
(ألف قاصر غريبا إذا ان عمليات الحذف وانكماش حواف يحدث فقط على جزء من الرسم البياني. رسم بياني يحتوي على K5 طفيفة غريبا إذا كان يحتوي على K5 التي تم استبدال عشرة من عشرة حواف الطرق طول ونيف.)

من الالتصاق السهام مفردة ومزدوجة معا (على التوالي) تؤدي إلى نتوء مستدير مع سبع مناطق فى ست الى ستة وسبعة ألوان ضرورية
هذه الصورة تظهر نتيجة الالتصاق précédent.On يمكن أيضا النظر في مشكلة تلوين خرائط مرسومة على سطوح أخرى من الخطة. على المجال ، فإن المشكلة هي نفسها (لعرض ، لمجرد إزالة نقطة داخل المجال إلى واحدة من المناطق ، وتنفيذ عملية الإسقاط المجسامي). مغلق للأسطح جنس إيجابية ، وعدد الألوان المطلوبة في أسوأ الحالات ، ع يعتمد على خاصية يولر من السطح ، χ ، وذلك باستخدام صيغة
حيث الأقواس يعين الخارجية صحيحا وظيفة.

تستند إلى أدلة باستخدام نظرية الألوان الأربعة نفسها ، وبالتالي هم لا تجلب مظاهرة جديدة.

السطوح أعم من الخطة [تحرير]


للحصول على سطح orientable ز للجنس ، وهذا يرقى إلىذه الصيغة التي تم تخمين Heawood في عام 1890 وثبت من قبل Ringel ويوونغس في عام 1968. علما بأن لز = 0 ، أنه يستعيد ونظرية الألوان الأربعة ، ولكن بطبيعة الحال ، فإن الأدلة السابقة لا تنطبق إلا إذا ز> 0.

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

ليس هناك تعميم في الفضاء لجميع الرسوم البيانية ، وبصفة خاصة في الرسم البياني الكامل هو إمبدبل 3D في الفضاء ، وبعبارة أخرى ، وذلك باستخدام مرنة ن ينبع ، فمن الممكن أن يرتب حتى أن كل يؤثر على جميع الآخرين ، وبالتالي يمكن اختيار ن كبيرة كما تريد ، دون ظهور نظرية "من الألوان ن.

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

تخصيص ترددات مختلفة في الخلايا المجاورة في شبكة جي إس إم للهاتف المحمول.
تنظيم استعراض المواد اللاحقة التي يجب أن تمر كل طالب. كيفية مقارنة عدة اختبارات دون ايذاء أحد المرشحين؟
الاستخدام الأمثل للعمل الآلية. كيفية تصنيع موازية باستخدام آلات متعددة؟
مشكلة التعارض. كيف يعيش الأشخاص أو الحيوانات ، مع مراعاة عدم اتساقها؟
الحواشي والمراجع [تحرير]
↑ ومن الناحية النظرية الرسم البياني ، ونحن نتحدث عن اللون والرسم البياني التلوين لا نقول وليس ذلك اللون البني [المرجع.الضرورة].
↑ آرثر كيلي ، على الأصباغ الخرائط ، وبالمجلس. الجمعية الجغرافية الملكية 1 ، 259-261 ، 1879.
↑ للحصول على نسخة مفصلة عن هذه الخوارزمية (قدمت على انها عمل تسترشد الكمبيوتر) على هذه الصفحة نظرا لمدرسا في مدرسة الفنون التطبيقية [الأرشيف]
↑ وقال إن الأدلة لا يمكن قراءتها في سبنسر جورج براون ، والقوانين من حيث الشكل ، لوبيك ، 1997 ، الملحق 5.
[تحرير]
اربع نظرية اللون : يسترشد العمل (الذي اقترحه G. Gonthier ، الذي يدرس في جامعة بوليتكنيك) ، مستعيدا تاريخ نظرية ، ويفصل طريقة محسنة لابيل وHaken.