تمييز الجيران بألوان الرأس والحواف: لماذا لا يغير تبديل الأسماء النجاح؟

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

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

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

نقارن لون الرأس وألوان حوافه، مع ثلاثة شروط للصحة

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

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

نفترض رسمًا بسيطًا غير موجه فيه رأس واحد على الأقل. نكتب C[A] لمجموعة A، ونفحص C[u]≠C[v] لكل حافة uv أصلية؛ لا نضيف مقارنة بين غير المتجاورين أو بين مكونين منفصلين.

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

نقلل عدد الألوان المستخدمة. الأرقام 1 و 2 و 3 أسماء رمزية للألوان، وليست أوزانًا عددية؛ تغيير الاسم لا يغير حجم لوحة الألوان.

المسار ينجح بمجموعتين متساويتين عند طرفيه غير المتجاورين

للمسار P3 الحافتان AB BC فقط. نعطي الرؤوس A=1 وB=2 وC=3، والحافتين AB=3 وBC=1.

كل رأسين متجاورين مختلفان، والحافتان مختلفتان، وكل حافة تختلف عن طرفيها. تكرار 3 على C وعلى AB مسموح لأن C ليس طرفًا للحافة AB؛ وتكرار 1 على A وعلى BC مسموح للسبب نفسه.

مجموعة A هي C[A]={1,3}، ومجموعة B هي C[B]={1,2,3}، ومجموعة C هي C[C]={1,3}. نضم لون الرأس نفسه إلى ألوان حوافه دون إدخال ألوان الرؤوس الأخرى.

تختلف المجموعتان عبر AB وعبر BC. تساوي مجموعتي A وC لا يفسد النجاح؛ ليست AC حافة في المسار.

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

تبديل كل الأسماء يحفظ المجموعات، لكنه قد يغير الجداء

نبدل اسم اللون 1 مع 2 في المسار كله، ونبقي 3. تصبح الرؤوس A=2 وB=1 وC=3، والحافتان AB=3 وBC=2.

المجموعات الجديدة هي C[A]={2,3} وC[B]={1,2,3} وC[C]={2,3}. يبقى الاختلاف عبر الحافتين، ويبقى تساوي الطرفين غير المتجاورين مسموحًا.

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

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

في مسألة التلوين الكلي بالجداء، نضرب عدد الرأس في أعداد حوافه ونقارن الناتجين عند الجيران، بأعداد موجبة من 1 إلى k. [3]

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

حجم المجموعة يساوي درجة الرأس زائد واحد

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

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

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

في المسار P3، درجتا الطرفين 1 ودرجة الوسط 2؛ حجما مجموعتي الطرفين 2 وحجم الوسط 3. لهذا كل تلوين كلي صحيح للمسار يميز الجيران بمجموعاته.

تساوي الدرجتين لا يعني تساوي المجموعتين: قد تتساوى الأحجام وتختلف الأسماء. المثلث التالي مثال على اختلاف ثلاث مجموعات متساوية الحجم.

المثلث يحتاج خمسة ألوان بدل ثلاثة

تجاور رؤوس المثلث يفرض ثلاثة ألوان مختلفة، فيستبعد لونًا ولونين. عند ثلاثة ألوان، الشاهد A=1 وB=2 وC=3 مع AB=3 وBC=1 وCA=2 صحيح كليًا، لكن مجموعة كل رأس هي {1,2,3} فتفشل الحواف الثلاث.

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

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

عند خمس ألوان يوجد سبعة أنماط صحيحة، منها ثلاثة تميز المجموعات؛ تقابلها 780 حالة مسماة صحيحة، منها 360 ناجحة في التمييز.

الشاهد A=1 وB=2 وC=3 مع AB=3 وBC=4 وCA=5 يعطي C[A]={1,3,5} وC[B]={2,3,4} وC[C]={3,4,5}. كل مجموعتين عند حافة مختلفتان، رغم اشتراكهما في بعض الألوان.

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

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

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

مجموعة رأس u تشمل لونه الخاص. مجموعة أي رأس آخر v لا تشمل هذا اللون: لون v مختلف، وكل ألوان الحواف مختلفة عنه أيضًا. لذا مجموعتا الرأسين مختلفتان.

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

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

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

الحافة المنفردة تقبل A=1 وB=2 وAB=3؛ المجموعتان {1,3} و{2,3} مختلفتان. العناصر الثلاثة تحتاج ألوانًا مختلفة بالصحة الكلية، فالأقل ثلاثة.

حصر الأنماط وفحص كل الأسماء يصلان إلى الحدود نفسها

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

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

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

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

الفحص المنفصل جرب بالفعل 13300636 تعيينًا للنماذج، منها 6217 صحيح كليًا و 4585 يميز مجموعات الجيران، و 4116 من الأخيرة يميز جميع الرؤوس أيضًا.

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

توزيع أقل الألوان للرسوم الـ64 هو واحد بلون، و 21 بثلاثة، و 31 بأربعة، و 11 بخمسة. وافق الفحص المنفصل الأنماط والحدود والشواهد وعدد التعيينات المقابل لكل نمط.

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