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

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

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

• على رسم بسيط متصل له رأسان على الأقل، يقارن التلوين الكلي المميز لجميع الرؤوس مجموعة لون الرأس وألوان حوافه لكل رأسين مختلفين، ويقلل عدد الألوان؛ صحة التلوين الكلي مطلوبة. [1]
• المسار P3 بالألوان A=1 وB=2 وC=3 مع AB=3 وBC=1 يعطي {1,3} و{1,2,3} و{1,3}؛ ينجح عند الجيران، لكنه يفشل عند الزوج AC غير المتجاور.
• الشاهد A=1 وB=2 وC=1 مع AB=3 وBC=4 يعطي {1,3} و{2,3,4} و{1,4} المختلفة جميعًا؛ تكرار لون الرأسين A وC مسموح، واختلاف ألوان الرؤوس وحده لا يضمن اختلاف مجموعاتها.
• التبديل العام لأسماء الألوان يحفظ الصحة واختلاف المجموعات؛ عدد الألوان المستخدمة هو الهدف، ولا نجمع الأرقام ولا نضربها في شرط القبول.
• مجموعة الرأس في تلوين كلي صحيح حجمها درجته زائد واحد؛ كل الرؤوس ذات الدرجة نفسها تحتاج مجموعات مختلفة بهذا الحجم، فتقيّدها سعة لوحة الألوان، لكن هذا قيد لازم لا يكفي وحده للحل.
• المسار يحتاج أربعة ألوان، والمثلث خمسة، والدورة C4 أربعة في الحصر؛ ولتمديدنا الصريح إلى الرسوم غير المتصلة والمعزولة، كل المعزولين يحتاجون ألوانًا مختلفة بينهم، والرسم الخالي من الحواف بأربعة رؤوس يحتاج أربعة.
• لون مختلف لكل رأس وحافة يثبت الوجود؛ ووافق فحص منفصل كل التعيينات المسماة حصر الأنماط في 10 نماذج و 64 رسمًا من أربعة رؤوس، وتوزيع أقل الألوان للرسوم هو 6 بثلاثة و 47 بأربعة و 11 بخمسة.

نقارن جميع مجموعات الرأس والحواف في تلوين كلي صحيح

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

الصحة الكلية تلزم باختلاف لوني الرأسين المتجاورين، ولوني الحافتين المتلاقيتين، ولون الرأس عن لون كل حافة ملتقية به. [2]

نكتب C[A] للمجموعة عند A. شرط التمييز هو C[u]≠C[v] لكل u≠v، حتى إذا لم تربطهما حافة. لا نأخذ ألوان الرؤوس المجاورة بدل ألوان الحواف، ولا نحسب مجموع الأرقام أو جداءها.

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

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

الشاهد ذو ثلاثة ألوان ينجح للجيران ويفشل عند AC

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

للمسار P3 الحافتان AB BC فقط. نعطي A=1 وB=2 وC=3، والحافتين AB=3 وBC=1؛ كل رأسين متجاورين مختلفان، والحافتان مختلفتان، وكل حافة تختلف عن طرفيها.

المجموعات هي C[A]={1,3} وC[B]={1,2,3} وC[C]={1,3}. تختلف عبر AB وعبر BC، فينجح شرط الجيران.

لكن C[A]=C[C]، والرأسان مختلفان وإن لم يتجاورا. لذلك يفشل شرط جميع الرؤوس. لا نضيف حافة AC إلى المسار؛ نضيف مقارنة مجموعتيهما فقط.

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

أربعة ألوان تميز المجموعات رغم تكرار لون الرأسين

نعطي المسار نفسه A=1 وB=2 وC=1، والحافتين AB=3 وBC=4. يختلف الرأس B عن جارَيه، والحافتان مختلفتان، وكل منهما تختلف عن طرفيها، فيصح التلوين الكلي.

نحسب C[A]={1,3} وC[B]={2,3,4} وC[C]={1,4}. الزوج AB يختلف، والزوج BC يختلف، والزوج AC يختلف أيضًا؛ هذه كل الأزواج الثلاثة.

لون A يساوي لون C، لكن مجموعتيهما مختلفتان بسبب لوني الحافتين. الصحة الكلية لا تمنع تكرار لون رأسين غير متجاورين.

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

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

نتعامل مع 1 و 2 و 3 و 4 بوصفها أسماء ألوان. تبديل الأسماء لا يغير عددها، لكن تغيير بعض العناصر وحدها قد يفسد الصحة أو التمييز.

عدد الرؤوس ذات الدرجة نفسها يقيد عدد المجموعات المتاحة

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

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

إذا استخدمنا k ألوان، فعدد المجموعات الممكنة ذات الحجم d+1 هو عدد طرق اختيار d+1 من هذه الألوان. يجب ألا يتجاوز عدد رؤوس الدرجة d عدد تلك المجموعات.

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

في أربعة رؤوس معزولة، حجم كل مجموعة واحد. لوحة ثلاثة ألوان لا تعطي إلا ثلاث مجموعات مفردة، فلا تكفي لأربعة رؤوس؛ أربعة ألوان مختلفة تكفي.

في المسار P3، مجموعتا الطرفين بحجم اثنين، ومجموعة الوسط بحجم ثلاثة. اختلاف الحجم يفصل الوسط عن الطرفين، لكن يجب أن نفصل الطرفين أيضًا.

المسار يحتاج أربعة، ولا يتحول نجاح المثلث إلى قاعدة عامة

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

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

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

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

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

المعزول يحتاج لونًا مميزًا، والألوان المختلفة تثبت الوجود

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

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

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

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

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

الحافة المنفردة تقبل A=1 وB=2 وAB=3، بمجموعتين {1,3} و{2,3}. هذا يوضح أن وجود لون الرأس داخل المجموعة يجعل الحل ممكنًا، ولا ننقل استحالة نموذج ألوان الحواف وحدها إلى هنا.

فحص كل الأسماء يؤكد حصر الأنماط ونطاق المقارنة

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

راجعنا 10 نماذج و 64 رسمًا مسمى من أربعة رؤوس، باختيار الحواف من الأزواج الستة الممكنة. فحصنا كل لوحة من 1 حتى أول نجاح للجميع.

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

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

في النماذج جرب 14350589 تعيينًا؛ منها 15882 صحيح كليًا و 14250 يميز الجيران و 5892 يميز الجميع. وفي رسوم الأربعة رؤوس جرب 26134235؛ منها 56130 صحيح كليًا و 37698 يميز الجيران و 32832 يميز الجميع.

توزيع أقل لوحة للجميع في الرسوم الـ64 هو 6 بثلاثة ألوان و 47 بأربعة و 11 بخمسة. جميعها ممكنة، ولا تعني هذه الأعداد حدًا عامًا لكل الرسوم.

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