تمييز الرؤوس بألوان الحواف: لماذا تحتاج الدورة الرباعية أربعة ألوان؟

الخلاصة السريعة

تحتاج الدورة الرباعية أربعة ألوان للحواف لأن التمييز يفرض اختلاف لوني الحافتين المتقابلتين، والتلوين الصحيح يفرض اختلاف لوني الحافتين المتجاورتين، فتختلف ألوان الحواف الأربع جميعًا.

• نلون الحواف تلوينًا صحيحًا، ثم نطلب اختلاف مجموعتي ألوان الحواف الملتقية عند طرفي كل حافة، ونقلل عدد الألوان المستخدمة؛ لا نلون الرؤوس في هذه المسألة. [1]
• في الدورة AB BC CD DA، التعيين 1،2،1،2 صحيح عاديًا لكنه يعطي كل رأس {1,2}. والتعيين 1،2،1،3 يفشل على BC وDA؛ أربعة أسماء مختلفة تحقق التمييز، والحجة تجبر كل زوج حواف على الاختلاف.
• المسار P4 بحواف AB BC CD يحتاج ثلاثة أسماء: التعيين 1،2،1 يعطي B وC المجموعة نفسها {1,2}، بينما 1،2،3 يميز طرفي كل حافة.
• الحافة التي تكون مكونًا وحدها تمنع الحل بأي عدد ألوان، لأن طرفيها يريان اللون نفسه وحده. الرأس المعزول مسموح، والرسم بلا حواف يحتاج صفر ألوان؛ إذا لم توجد حافة منفردة، فإن اسمًا خاصًا لكل حافة يضمن وجود حل.
• المجموعتان {1,2} و{2,1} متساويتان، والمجموعتان {1,2} و{1,3} مختلفتان رغم تساوي حجميهما. تبديل أسماء اللوحة كلها يحفظ الحكم؛ مقارنة الأسماء لا ترتيبها ولا مجرد عددها.
• التمييز المحلي وتحديد الجيران يلونان الرؤوس ويقارنان ألوان جوارها؛ هنا نلون الحواف ونقارن مجموعاتها عند رأسين متجاورين. وعلى النجمة ذات ثلاث أوراق، الأقل للحواف هنا ثلاثة، ولتحديد الجيران بألوان الرؤوس أربعة. [3] [4] [1]
• راجعنا 24 نموذجًا و 64 رسمًا من أربعة رؤوس؛ تسعة من الرسوم بلا حل لوجود حافة منفردة. توزيع البقية: صفر في رسم واحد، و 2 في 12، و 3 في 32، و 4 في 9، و 5 في رسم واحد. الحصر يراجع الأمثلة، ولا يحل كل رسم.

نلون الحواف، ونقارن المجموعتين عند طرفي كل حافة

في التلوين العادي للحواف، يأخذ كل خط لونًا واحدًا، وتختلف ألوان أي حافتين تلتقيان عند رأس واحد؛ العدد الأدنى يقلل أسماء الألوان المستخدمة. [2]

التلوين المميز للرؤوس المتجاورة تلوين صحيح للحواف يطلب اختلاف مجموعتي الألوان الملتقية عند طرفي كل حافة؛ نبحث عن أقل عدد أسماء يحقق ذلك. [1]

نكتب S[A] لمجموعة ألوان الحواف الملتقية عند A. إذا كانت الحواف AB وAC وAD ملونة 1 و 2 و 3، كانت S[A]={1,2,3}؛ لا ندخل لونًا خاصًا للرأس A.

لكل حافة AB، يجب أن تختلف S[A] عن S[B]؛ لا نطلب مقارنة رأسين غير متجاورين ولا نستثني حافة لتشابه طرفيها. [1]

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

يجب استيفاء الشرطين معًا: اختلاف ألوان الحواف التي تلتقي، واختلاف مجموعتي الألوان عند طرفي كل حافة. صحة أحد الشرطين لا تغني عن فحص الآخر. [1]

الدورة الرباعية: لون ثالث يكسر التناوب لكنه لا يكفي

خذ الحواف AB BC CD DA، بهذا الترتيب. أعطها الألوان 1،2،1،2. أي حافتين تلتقيان مختلفتان، فيكون التلوين صحيحًا عاديًا، وبما أن عند كل رأس حافتين، فلونان هما الأقل عاديًا.

لكن S[A]=S[B]=S[C]=S[D]={1,2}. على كل حافة، تتساوى المجموعتان عند طرفيها، فيفشل التمييز على الحواف الأربع.

غير لون DA إلى 3، فتكون ألوان الحواف 1،2،1،3. صار S[A]={1,3} وS[B]={1,2} وS[C]={1,2} وS[D]={1,3}.

هذا التعيين صحيح عاديًا أيضًا، وتختلف المجموعتان على AB وعلى CD. لكنه يفشل على BC لأن مجموعتي B وC متساويتان، وعلى DA لأن مجموعتي D وA متساويتان.

قول إن عند كل رأس لونين لا يحسم المقارنة: للمجموعتين {1,2} و{1,3} الحجم نفسه وهما مختلفتان، وللمجموعتين {1,2} و{2,1} الأسماء نفسها وهما متساويتان.

لإثبات أن أربعة ضرورية، انظر إلى الحافة BC. المجموعتان عند B وC تشتركان في لون BC، ويمنع التلوين الصحيح أن يتكرر هذا اللون في AB أو CD. لذا لا تختلف المجموعتان إلا إذا اختلف لونا AB وCD.

وبمقارنة الطرفين على AB، نحتاج اختلاف لوني DA وBC. فرض التمييز إذن اختلاف لوني كل زوج حواف متقابل، وفرض التلوين الصحيح اختلاف لوني كل زوج حواف متجاور.

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

الألوان 1،2،3،4 على AB BC CD DA تعطي S[A]={1,4} وS[B]={1,2} وS[C]={2,3} وS[D]={3,4}. تختلف المجموعتان عند طرفي كل حافة؛ أربعة تكفي وضرورية.

المسار P4 يحتاج ثلاثة ألوان لحوافه الثلاث

حواف المسار هي AB BC CD. التعيين 1،2،1 صحيح عاديًا، لكن S[B]=S[C]={1,2}، فيفشل الشرط على الحافة الوسطى BC.

مجموعتا B وC تشتركان في لون BC، وتضيف الأولى لون AB والثانية لون CD. لكي تختلفا، يجب أن يختلف لونا AB وCD.

التلوين الصحيح يفرض أيضًا اختلاف AB عن BC واختلاف BC عن CD. إذن تحتاج الحواف الثلاث ثلاثة أسماء مختلفة، لا لونين.

التعيين AB=1 وBC=2 وCD=3 يعطي S[A]={1} وS[B]={1,2} وS[C]={2,3} وS[D]={3}. تختلف المجموعتان على الحواف الثلاث؛ هذا شاهد يحقق الحد الأدنى.

في التعيين الأول، تتساوى مجموعتا A وD أيضًا، لكنهما غير متجاورين؛ لم يكن ذلك سبب الرفض. سبب الرفض هو المجموعتان المتساويتان على BC.

الرأس المعزول مسموح، والحافة المنفردة تمنع الحل

الرأس المعزول لا تتصل به حافة، فتكون مجموعة ألوان حوافه فارغة. لا توجد حافة نحتاج عبرها مقارنة مجموعته بغيرها؛ وجوده لا يفسد تعيينًا صحيحًا للحواف الأخرى.

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

لا تضف ألوانًا لا تستعملها على حواف الرسم وتدعي أن ذلك حل المشكلة. ما دام الطرفان لا يريان إلا الحافة نفسها، ظلت المجموعتان المتساويتان كما هما.

مثلث A B C مع رأسين معزولين D وE يقبل AB=1 وBC=2 وCA=3. مجموعات رؤوس المثلث {1,3} و{1,2} و{2,3} مختلفة على كل حافة، وS[D]=S[E]={} مسموح. ثلاثة هي الأقل، لأن حواف المثلث الثلاث تتلاقى زوجيًا.

الرسم بلا حواف يقبل التعيين الفارغ: لا خطوط نلونها ولا حافة نحتاج عبرها مقارنة. نعد الألوان المستخدمة صفرًا، ولو كان للرسم عدة رؤوس.

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

لو تساوت مجموعتا الحواف الملتقية عند رأسين متجاورين، لكانت الحافة التي تجمعهما هي الوحيدة في المجموعتين؛ فكل حافة أخرى عند أحدهما لا يمكن أن تكون عند الآخر أيضًا في رسم بسيط.

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

مجموعات الأسماء لا أحجامها وحدها ولا ترتيب الكتابة

قارن أسماء الألوان نفسها. المجموعة {1,2} مساوية لـ{2,1}، ومختلفة عن {1,3}، رغم أن المجموعات الثلاث تحتوي اسمين.

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

على نجمة ذات ثلاث أوراق، أعط حواف المركز الألوان 1 و 2 و 3. مجموعة المركز {1,2,3}، ومجموعة كل ورقة تحوي لون حافتها وحده؛ تختلف المجموعتان على كل حافة بحكم الحجم.

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

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

ألوان الحواف تختلف عن ألوان الرؤوس في التمييز المحلي والجيران

التلوين المميز محليًا تلوين صحيح للرؤوس يقارن مجموعتي ألوان الجوار المغلق لرأسين متجاورين لهما جواران مغلقان مختلفان، ويقلل عدد الألوان. [3]

التلوين المحدد بالجيران يلون الرؤوس تلوينًا صحيحًا، ويطلب اختلاف مجموعتي ألوان الجوار المفتوح لكل رأسين لهما اللون نفسه، ويقلل عدد الألوان. [4]

المقال يلون الحواف ويقارن مجموعتي ألوانها عند طرفي كل حافة؛ لا يستعمل ألوان الرأس أو ألوان جيرانه. اشتراك التعريفات في كلمة التمييز لا يجعل الأشياء الملونة أو الأزواج المقارنة واحدة. [1]

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

وعلى الرسم بلا حواف، يحتاج تمييز الجيران بألوان الرؤوس اسمًا مختلفًا لكل رأس، بينما المقال يستخدم صفر ألوان للحواف. لا تنقل العدد من إحدى المسألتين إلى الأخرى لمجرد أن الرسم نفسه.

24 نموذجًا و 64 رسمًا: تسعة بلا حل لوجود حافة منفردة

جدول النماذج يعرض أقل عدد عادي للحواف، وأقل عدد يميز طرفي كل حافة، وتعيينًا شاهدًا عندما يوجد حل. كلمة مستحيل تعني أن الرسم يحتوي حافة تشكل مكونًا وحدها، وليست فشل محاولة بألوان قليلة.

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

في أربعة رؤوس، ست حواف ممكنة تعطي 64 رسمًا مسمى. هناك 125 تقسيمًا صحيحًا عاديًا للحواف و 82 تحقق التمييز. تسعة رسوم بلا حل، وفي البقية الأقل صفر في رسم واحد، و 2 في 12، و 3 في 32، و 4 في 9، و 5 في رسم واحد.

الفحص ذو الأسماء المحددة جرب 69853 تعيينًا في هذه الرسوم، منها 7663 صحيحة عاديًا و 5833 تحقق التمييز. هذه أعداد تعيينات لا أعداد رسوم، ولا أزمنة تنفيذ.

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

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

الطريقتان تستعملان Python، ولا ندعي مراجعة بشرية مستقلة أو برنامجًا يحل كل رسم. لإعلان عدد أدنى، نحتاج تعيينًا يحقق الشرطين ودليلًا يستبعد عددًا أقل؛ وجود شاهد وحده يثبت الكفاية.