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

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

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

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

نجمع صحة الحواف مع كسر تناظر الرسم

يعرف المصدر تمييز التناظر بألوان الحواف بغياب أي تناظر غير الهوية يحفظ التلوين، ثم يعرف نسخته الصحيحة بأقل عدد ألوان في تلوين حواف صحيح يحقق الشرط نفسه. [1]

التناظر هنا تبديل لرؤوس الرسم يحفظ علاقة التجاور، أي تماثل للرسم مع نفسه. [3]

وصحة تلوين الحواف تعني اختلاف لونَي أي حافتين تلتقيان عند رأس. [2]

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

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

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

لونان يصححان الدورة لكن نصف دورة يبقى

نرسم C4 بالرؤوس A B C D والحواف AB BC CD DA فقط. لا توجد الحافتان AC وBD. للدورة ثمانية تناظرات، منها الهوية وثلاثة دورانات وأربعة انعكاسات.

أعط الحواف، بهذا الترتيب، الألوان 1،2،1،2. تختلف ألوان كل حافتين متلاقيتين، فيكون التلوين صحيحًا. لون واحد لا يصح لأن كل رأس يلتقي عنده زوج من الحواف؛ لذلك الحد الصحيح المعتاد لونان.

لكن تبديل الرؤوس A→C وB→D وC→A وD→B يرسل AB إلى CD، وBC إلى DA، وCD إلى AB، وDA إلى BC. يحفظ هذا الدوران كل لون، وهو غير الهوية، فيفشل شرط التمييز.

في الحقيقة تبقى أربعة تناظرات حافظة لهذا التلوين: الهوية، ونصف الدورة، والانعكاسان اللذان يتبادلان A مع B وC مع D، أو A مع D وB مع C.

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

ثلاثة ألوان تترك انعكاسًا وأربعة تكفي

جرب AB=1 وBC=2 وCD=1 وDA=3. التلوين صحيح؛ الحافتان اللتان تكرران اللون 1 متقابلتان ولا تلتقيان عند رأس.

يبقى الانعكاس A→D وB→C وC→B وD→A. يبادل AB مع CD، ويثبت BC وDA كلًا على حدة. لذلك يحفظ الألوان 1 و 2 و 3، ويبقى مع الهوية تبديلان حافِظان.

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

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

أعط الآن AB=1 وBC=2 وCD=3 وDA=4. كل حافة تحمل لونًا مختلفًا، فيكون التلوين صحيحًا. أي تناظر يحفظ الألوان يجب أن يثبت كل حافة على حدة.

الرأس A هو تقاطع AB وDA، وB تقاطع AB وBC، وC تقاطع BC وCD، وD تقاطع CD وDA. تثبيت الحواف الأربع يثبت هذه التقاطعات، ومن ثم جميع الرؤوس؛ لا يبقى إلا الهوية.

أثبتنا حدًا أدنى أربعة باستبعاد الألوان الأقل، وحدًا أعلى أربعة بشاهد فعلي، فعدد ألوان التلوين الصحيح المميز للدورة هو أربعة.

يمكن لثلاثة ألوان أن تميز التناظر دون صحة الحواف

احذف شرط اختلاف الحواف المتلاقية، وأعط AB=1 وBC=1 وCD=2 وDA=3. اللون 2 يحدد CD وحدها، واللون 3 يحدد DA وحدها.

أي تناظر حافظ يثبت هاتين الحافتين، فيثبت تقاطعهما D، ثم طرفيهما الآخرين C وA، ثم الرأس الباقي B. لا يبقى إلا الهوية، فيكون التلوين مميزًا.

لكنه غير صحيح لأن AB وBC تلتقيان عند B وتحملان اللون 1. لهذا لا يقدم شاهدًا بثلاثة ألوان للمسألة التي تجمع الصحة والتمييز.

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

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

نثبت أسماء الألوان أثناء حركة الرؤوس

في التلوين المتناوب 1،2،1،2، الدوران ربع دورة A→B وB→C وC→D وD→A يرسل AB ذات اللون 1 إلى BC ذات اللون 2. لذلك لا يحفظ التلوين، رغم أنه يحفظ الرسم غير الملون.

يمكن أن يعوض تبديل الاسمين 1 و 2 هذا التغير، لكن المسألة لا تسمح بتعويض حركة الرؤوس بتغيير أسماء الألوان. نثبت الأسماء نفسها أثناء اختبار كل تناظر.

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

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

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

بعض التناظرات لا تستطيع ألوان الحواف كسرها

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

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

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

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

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

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

نحسب التناظرات والتلوينات في حصر محدود

فحصنا 25 نموذجًا مسمى و 64 رسمًا مسمى من أربعة رؤوس، أي جميع اختيارات الحواف من الأزواج الستة لتلك الرؤوس. استعملنا بيانات الرسوم من فحص سابق، ثم حسبنا تناظراتها وحدود التلوين من جديد.

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

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

راجعنا 15229 تبديل رؤوس في النماذج و 1536 في رسوم الأربعة. اختبر الحصر الكامل 44786 تعيينًا مسمى للحواف في النماذج و 31343 في رسوم الأربعة، بما يشمل التعيينات غير الصحيحة واللوحات الأصغر.

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

اتفق الحصران على مجموعات التناظر والعوائق والحدود والشواهد وأعداد التلوينات. في الأربعة: 10 مستحيلة، و 12 حدها 2، و 32 حدها 3، و 9 حدها 4، وواحدة حدها 5.

هذه نتائج الرسوم المحددة، وليست صيغًا عامة للعائلات. اعتمدنا تعريفَي المصدر فقط، ولم نعتمد صيغ الورقة لعائلات الرسوم أو صورها. المراجعة تحريرية آلية ولا ندعي مراجعة بشرية أو اعتماد خبير.