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

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

تكفي للدورة السداسية ثلاثة ألوان لأن الحواف المتتابعة بالألوان 1،1،2،2،3،3 تعطي ست مجموعات مختلفة، والتلوين العام يسمح بتساوي ألوان حواف متلاقية، بينما لونان لا يوفران ست مجموعات غير فارغة.

• نلون الحواف وحدها، ونطلب اختلاف مجموعة ألوان الحواف الملتقية بكل رأس عن مجموعة أي رأس آخر؛ نقلل عدد الألوان، دون اشتراط تلوين الحواف الصحيح. [1]
• في الدورة C6، تعيين AB=1 وBC=1 وCD=2 وDE=2 وEF=3 وFA=3 يعطي المجموعات {1,3} و{1} و{1,2} و{2} و{2,3} و{3} المختلفة جميعًا.
• لونان يوفران ثلاث مجموعات غير فارغة فقط؛ لذلك لا يكفيان لستة رؤوس غير معزولة، وشاهد الثلاثة يثبت الحد الأدنى؛ النموذج الصحيح للجميع احتاج خمسة في الحصر السابق.
• التكرار داخل المجموعة يحسب مرة واحدة؛ قد يكون حجمها أقل من درجة الرأس، والتبديل المتقابل العام لأسماء الألوان يحفظ النجاح، بخلاف تغيير بعض الحواف وحدها.
• طرفا حافة معزولة لهما المجموعة المفردة نفسها مهما كبر عدد الألوان؛ والمعزولان لهما المجموعة الفارغة نفسها، فيمنع هذان العائقان الحل.
• إذا غاب المكون ذو الحافة الواحدة ولم يوجد أكثر من رأس معزول، فإن لونًا فريدًا لكل حافة يميز الجميع؛ الرسم ذو الرأس الوحيد بلا حواف يحتاج صفر ألوان.
• وافق فحص مستقل كل التعيينات المسماة حصر الأنماط في 25 نموذجًا و 64 رسمًا من أربعة رؤوس؛ الفشل البنيوي برهان دائم، والأعداد المحدودة لا تثبت صيغة عامة للرسوم.

نجمع ألوان الحواف فقط ونقارن جميع الرؤوس

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

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

نكتب S[A] لمجموعة ألوان الحواف الملتقية بالرأس A. نقارن S[u] وS[v] لكل رأسين مختلفين، حتى غير المتجاورين والرؤوس في مكونات منفصلة.

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

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

حواف الدورة بالألوان 1،1،2،2،3،3 تميز الرؤوس الستة

رتب رؤوس الدورة C6 هكذا: A B C D E F، وحوافها AB BC CD DE EF FA. نعطي AB=1 وBC=1 وCD=2 وDE=2 وEF=3 وFA=3.

عند A تلتقي الحافتان AB وFA، فتكون S[A]={1,3}. عند B تلتقي AB وBC وكلتاهما بلون 1، فتكون S[B]={1}، دون تكرار الاسم.

بالطريقة نفسها نحصل على S[C]={1,2} وS[D]={2} وS[E]={2,3} وS[F]={3}. هذه هي المفردات الثلاث والأزواج الثلاث من لوحة الألوان {1,2,3}.

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

الرأس ذو الدرجة 2 لا يضمن مجموعة من عنصرين هنا؛ عند B وD وF يتكرر اللون، فتكون المجموعة مفردة. هذه المخالفات لصحة تلوين الحواف مسموحة في النموذج العام.

لإثبات أن ثلاثة هي الأقل، لاحظ أن لونين لا يتيحان إلا {1} و{2} و{1,2} للرؤوس غير المعزولة. ثلاث مجموعات لا تكفي لستة رؤوس، ومع الشاهد نحصل على الحد الدقيق.

السماح بالتكرار يغير الشواهد والحدود

تلوين الحواف الصحيح يفرض اختلاف لونَي أي حافتين تلتقيان برأس. [2]

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

في الحصر السابق لذلك النموذج، احتاجت C6 خمسة ألوان. الشاهد AB=1 وBC=2 وCD=3 وDE=1 وEF=4 وFA=5 يعطي {1,5} و{1,2} و{2,3} و{1,3} و{1,4} و{4,5}.

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

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

في P3، الحافتان AB=1 وBC=2 تعطيان {1} و{1,2} و{2}. إذا جعلنا كلتيهما بلون 1 صارت المجموعات الثلاث {1} وفشل التمييز؛ السماح بالتكرار لا يضمن نجاح أي تكرار.

المجموعة قد تصغر عن الدرجة، وعددها يقيد اللوحة

الرأس ذو الدرجة d>0 يتلقى d أسماء من الحواف، لكن حذف التكرار يترك بين 1 وmin(d,k) أسماء مختلفة عند استعمال لوحة k ألوان. في التلوين الصحيح فقط لا يتكرر لون حافتين عند الرأس، فيساوي الحجم d.

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

عمومًا للوحة k ألوان 2^k مجموعات جزئية. المجموعة الفارغة لا تنتج إلا عند رأس معزول؛ لكل رأس غير معزول مجموعة من المجموعات غير الفارغة الـ2^k-1.

إذا كان عدد غير المعزولين n، فيلزم 2^k-1≥n. وإذا شملنا جميع الرؤوس في العدد n، فيلزم 2^k≥n. هذان قيدان لازمان لا يضمنان إمكان توزيع الألوان على حواف الرسم.

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

إذا بدلنا أسماء 1 و 2 و 3 كلها تبديلًا متقابلًا، بقيت علاقات تساوي المجموعات واختلافها. مثلًا يحول التبديل 1 إلى 3 و 2 إلى 1 و 3 إلى 2 حواف C6 إلى 3،3،1،1،2،2 ويظل الشاهد ناجحًا.

حافة معزولة أو معزولان يمنعان الحل بأي عدد ألوان

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

إذا كان هذا المكون AB ولون حافته c، فإن S[A]={c} وS[B]={c}. لا توجد حافة أخرى تميز أحد الطرفين، وزيادة اللوحة لا تضيف حواف إلى المكون؛ يستحيل اختلاف المجموعتين.

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

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

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

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

ألوان فريدة للحواف تثبت الوجود عند غياب العائقين

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

عندئذ تمثل مجموعة كل رأس حوافه نفسها بأسماء فريدة. إذا تساوت مجموعتا رأسين غير معزولين u وv، فكل حافة عند u يجب أن تكون عند v أيضًا.

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

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

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

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

الفحص المستقل يجرب الحواف وحدها ولا يحذف التكرار

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

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

الحصر الأول يمثل الأسماء بترتيب أول ظهور: أول لون 1 والجديد التالي 2 وهكذا. لم يحذف لونين متساويين على حافتين متلاقيتين؛ حذف هذه الحالات سيغير المسألة ويزيل شاهد C6.

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

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

بين رسوم الأربعة رؤوس، يوجد 10 مستحيلة، و 12 حدها لونان، و 42 حدها ثلاثة. جدول النماذج يعرض عينة مع الشواهد؛ هذه نتائج حصر محدد وليست صيغة لجميع الرسوم.

وافق فحص Node حصر Python في الحدود وأعداد الأنماط والتعيينات والشواهد؛ حساب الصحة كان تشخيصًا إضافيًا لا شرط قبول. لا ندعي مراجعة بشرية أو خبيرًا مستقلًا أو قراءة نتائج المصدر عن اتحادات المسارات.