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

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

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

• نطلب تلوينًا صحيحًا للرؤوس لا يحفظه أي تناظر للرسم غير الهوية؛ العدد المطلوب هو أقل عدد ألوان مستخدمة يحقق الشرطين. [1]
• الدورة C4 تقبل تلوينًا صحيحًا بلونين A=1 وB=2 وC=1 وD=2، لكنه يترك أربعة تناظرات حافظة، منها دوران نصف دورة.
• في C4، كل تلوين صحيح بثلاثة ألوان أو أقل يكرر لونًا على رأسين متقابلين، وتبديلهما وحده يبقى تناظرًا؛ أربعة ألوان مختلفة تثبت جميع الرؤوس، فيثبت الحد أربعة.
• الرؤوس بالألوان 1،1،2،3 تميز تناظر C4 بثلاثة ألوان لأن اللونين الفريدين يثبتان الرأسين المتجاورين C وD، لكنها تخرق صحة التلوين عند AB.
• نختبر تناظر الرؤوس بأسماء ألوان ثابتة؛ إعادة تسمية الألوان عالميًا تحفظ النتيجة، ولا تسمح بتعويض دوران الرسم بتبديل الأسماء أثناء الاختبار.
• كل رسم محدود له حل بألوان رؤوس مختلفة: المعزول الوحيد يحتاج لونًا، وأربعة معزولين أربعة، وK4 أربعة، ونجمة بثلاث أوراق أربعة؛ ألوان الحواف مسألة بمتغيرات وحدود مختلفة.
• وافق حصران لكل التعيينات في 25 نموذجًا و 64 رسمًا من أربعة رؤوس؛ بين رسوم الأربعة 18 حدها 2 و 31 حدها 3 و 15 حدها 4، وجميعها قابلة للحل، دون تعميم نتائج الحصر.

يلزم اختلاف ألوان المتجاورين وتثبيت كل رأس

يعرف المصدر العدد اللوني المميز بأنه أقل عدد ألوان في تلوين صحيح لا يحفظه سوى تناظر الهوية. [1]

التلوين الصحيح للرؤوس يطلب لونين مختلفين لطرفَي كل حافة. [2]

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

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

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

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

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

لونان صحيحان في الدورة يتركان أربعة تناظرات

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

أعط A=1 وB=2 وC=1 وD=2. كل حافة تصل اللون 1 باللون 2، فيكون التلوين صحيحًا. لون واحد لا يصح لأن الرسم له حافة، فيثبت أن عدد الألوان الصحيح المعتاد اثنان.

دوران نصف دورة A→C وB→D وC→A وD→B يحفظ الحواف، ويرسل كل رأس إلى رأس من اللون نفسه. لذلك يفشل التمييز رغم تحقق الصحة.

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

ننظر هنا إلى الألوان على الرؤوس مباشرة: كلا A وC من اللون 1، وكلا B وD من اللون 2. الحواف الرمادية مجرد علاقات تجاور، ولا ندخل ألوانها في اختبار الحركة.

تبديل رأسين متقابلين يستبعد ثلاثة ألوان

جرب A=1 وB=2 وC=1 وD=3. التلوين صحيح؛ A وC غير متجاورين، وبقية طرفَي كل حافة مختلفان.

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

في أي تلوين صحيح بثلاثة ألوان أو أقل، أربعة رؤوس تفرض تكرار لون. لا يمكن أن يقع التكرار على رأسين متجاورين بسبب الصحة، فيقع على رأسين متقابلين.

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

أعط الآن A=1 وB=2 وC=3 وD=4. الألوان المختلفة تجعل التلوين صحيحًا، وأي تناظر يحفظ الألوان يثبت كل رأس، لأن لون ذلك الرأس لا يظهر في رأس آخر.

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

لاحظ أن انعكاس شاهد الرؤوس 1،2،1،3 هو A مع C مع تثبيت B وD. في شاهد ألوان الحواف بالأرقام نفسها يكون الانعكاس الحافظ مختلفًا؛ موضع إسناد اللون يغير الاختبار.

تمييز التناظر وحده يقبل لونًا مكررًا عند حافة

خذ الرؤوس A B C D بالألوان 1،1،2،3. اللون 2 يظهر عند C وحده، واللون 3 عند D وحده؛ أي تناظر حافظ يثبت C وD.

جيران C هما B وD؛ بعد تثبيت C وD يثبت B بوصفه الجار الآخر لـC. ثم يثبت A لأنه الرأس المتبقي. هكذا لا يبقى إلا الهوية.

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

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

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

إعادة تسمية الألوان تختلف عن حركة الرؤوس

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

لو سمحنا له أيضًا بتبديل الاسمين 1 و 2 لتعويض الدوران، لحصلنا على اختبار آخر. لا نفعل ذلك هنا: حركة الرؤوس تختبر والتلوين المسند ثابت.

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

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

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

الحد المطلوب عدد الأسماء المستخدمة، وليس أكبر عدد مكتوب. كتابة اللونين 7 و 9 بدل 1 و 2 لا تعني أن التلوين استخدم تسعة ألوان، لأن الأرقام هنا ليست أوزانًا عددية.

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

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

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

في أربعة معزولين، كل تبديل للرؤوس يحفظ الرسم غير الملون. إذا تشارك رأسان في لون، أمكن تبديلهما دون تغيير الألوان؛ لذلك يلزم أربعة ألوان مختلفة، وهي تكفي. صحة التلوين وحدها لا تفرض اختلافًا هنا، لأن الحواف معدومة.

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

في النجمة ذات المركز A والأوراق B C D، يلزم اختلاف ألوان الأوراق الثلاث لمنع تبديل أي زوج منها. ويحتاج المركز لونًا رابعًا لأنه متجاور مع جميع الأوراق. الشاهد A=1 وB=2 وC=3 وD=4 صحيح ومميز، والحد أربعة.

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

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

الأمثلة تثبت اختلاف المسائل: في C4 يتفق حد الرؤوس والحواف الصحيح المميز عدديًا عند أربعة، لكن في K4 والنجمة والمعزولات تختلف الحدود أو إمكانية الحل. لا ننقل نتيجة من موضع ألوان إلى الآخر.

نحصي التلوينات على الرؤوس المسماة ونفحص كل تناظر

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

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

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

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

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

اتفقت مجموعات التناظر والحدود والشواهد وأعداد التلوينات؛ جميع الرسوم المختبرة قابلة للحل. في الأربعة، 18 حدها 2 و 31 حدها 3 و 15 حدها 4. من تلك الخمسة عشر الرسم بلا حواف، إذ يحتاج أربعة ألوان لتمييز معزولاته.

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