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

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

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

• نلون الرؤوس تلوينًا صحيحًا، ثم نطلب اختلاف مجموعتي ألوان الجوار المغلق لكل متجاورين لهما جواران مغلقان مختلفان؛ الجوار المغلق يشمل الرأس نفسه. [1]
• على P4، التعيين 1،2،1،2 يفشل على الحواف الثلاث، والتعيين 1،2،3،1 يفشل على BC وحدها: جوارا B وC مختلفان كرؤوس، لكن مجموعتي ألوانهما {1,2,3} متساويتان.
• التمييز على AB يفرض اختلاف ألوان A وB وC، وعلى CD يفرض اختلاف B وC وD؛ ثم التمييز على BC يفرض اختلاف A وD، فتحتاج أربعة أسماء، ويحققها التعيين 1،2،3،4.
• المتجاوران ذوا الجوار المغلق نفسه مستثنيان؛ لذلك المثلث صحيح بثلاثة ألوان. ولا نطلب تمييز كل الرؤوس غير المتجاورة: C4 تقبل 1،2،1،3 رغم تساوي مجموعتي الجوار عند A وC.
• نقارن مجموعات الأسماء المختلفة، لا تكراراتها؛ على P4 ذي اللونين، تكرارات ألوان جواري B وC تختلف لكن مجموعتيهما {1,2} متساويتان، فيفشل التمييز.
• التلوين المحلي يقلل أكبر عدد ألوان يظهر في جوار مغلق، والديناميكي يفرض حدًا لعدد ألوان الجيران؛ مسألتنا تقارن مجموعتي الجوار على الحافة، والتعيين 1،2،3،1 على P4 ينجح ديناميكيًا ويفشل في التمييز. [3] [4]
• راجعنا 26 نموذجًا و 64 رسمًا من أربعة رؤوس. أقل عدد في هذا الحصر: 1 في رسم واحد، و 2 في تسعة، و 3 في 23، و 4 في 31. الرسم بلا حواف يحتاج اسمًا واحدًا؛ إعطاء كل رأس اسمًا خاصًا يضمن وجود حل.

جوار مغلق، وتلوين صحيح، وتمييز مشروط على الحافة

في التلوين العادي الصحيح، يأخذ كل رأس لونًا واحدًا، ويختلف لونا طرفي كل حافة مع تقليل عدد الألوان. [2]

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

الجوار المغلق للرأس هو الرأس نفسه مع جميع جيرانه. نكتبه N[A] للرأس A؛ أما الجوار المفتوح فيستثني A. نأخذ مجموعة أسماء الألوان التي تظهر على الرؤوس في N[A]، ونكتبها S[A]. [1]

على AB، افحص N[A] وN[B] أولًا؛ إذا اختلفا، افحص اختلاف S[A] وS[B]. [1]

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

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

مسار P4: اختلاف الرؤوس لا يكفي لاختلاف مجموعات الألوان

خذ الحواف AB BC CD فقط. الجوار المغلق عند A هو {A,B}، وعند B هو {A,B,C}، وعند C هو {B,C,D}، وعند D هو {C,D}. جوارا كل طرفي حافة مختلفان؛ لذلك نفحص الحواف الثلاث كلها.

لون المسار بالتناوب: A=1 وB=2 وC=1 وD=2. لا توجد حافة بلون واحد، فيصح التلوين العادي. لكن كل جوار مغلق يظهر فيه اللونان 1 و 2 فقط، فتتساوى مجموعات الألوان على الحواف الثلاث ويفشل التمييز.

جرّب A=1 وB=2 وC=3 وD=1. تظهر عند A المجموعة {1,2} وعند D {1,3}، بينما تظهر عند B وC المجموعة {1,2,3}.

ينجح التمييز على AB لأن {1,2} تختلف عن {1,2,3}، وعلى CD لأن {1,2,3} تختلف عن {1,3}. لكنه يفشل على BC؛ الجواران {A,B,C} و{B,C,D} مختلفان، ومجموعتا ألوانهما متساويتان.

لا تنشأ حافة AD في المسار لأننا أعطينا A وD اللون نفسه. المشكلة ليست اشتراكهما مباشرة في لون؛ إنما أثر هذا الاشتراك في مجموعة الألوان المرئية داخل جواري B وC المتجاورين.

أعط A وB وC وD الألوان 1،2،3،4 على الترتيب. تصبح المجموعات {1,2} و{1,2,3} و{2,3,4} و{3,4}. تختلف على الحواف الثلاث، فيكون التعيين صحيحًا ومميزًا محليًا بأربعة ألوان.

لماذا لا تنجح أي لوحة من ثلاثة أسماء على P4؟

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

على AB، مجموعة ألوان جوار A هي ألوان A وB، ومجموعة جوار B تضيف لون C. لكي تختلف المجموعتان، يجب أن يكون لون C مختلفًا عن لونَي A وB. والتلوين الصحيح يميز A عن B أصلًا، فتكون ألوان A وB وC مختلفة.

على CD، مجموعة ألوان جوار D هي ألوان C وD، ومجموعة جوار C تضيف لون B. يجب أن يختلف لون B عن لونَي C وD؛ مع التلوين الصحيح تصبح ألوان B وC وD مختلفة.

لم يبق احتمال اشتراك إلا بين A وD. إذا تساوى لونهما، صارت مجموعة ألوان A B C مساوية لمجموعة B C D؛ فتفشل الحافة BC، لأن جواريها مختلفان كرؤوس. إذن يجب أن يختلف A عن D أيضًا.

الأزواج الستة للرؤوس الأربعة كلها مختلفة الألوان: AB وBC وCD بحكم التلوين الصحيح، وAC وBD بحكم حافتي الطرفين، وAD بحكم الحافة الوسطى. لذلك نحتاج أربعة أسماء على الأقل.

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

المثلث مستثنى من التمييز، والرؤوس غير المتجاورة لا نقارنها

في مثلث الرؤوس A B C، يكون N[A]=N[B]=N[C]={A,B,C}. كل زوج متجاور له الجوار المغلق نفسه؛ لذلك تستثنى الحواف الثلاث من شرط اختلاف مجموعات الجوار.

لكن شرط التلوين الصحيح باقٍ: رؤوس المثلث متجاورة زوجيًا، فتحتاج ثلاثة ألوان مختلفة. التعيين A=1 وB=2 وC=3 صحيح ومميز محليًا، رغم أن S[A]=S[B]=S[C]={1,2,3}.

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

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

على C4 بالحواف AB BC CD AD، اختر A=1 وB=2 وC=1 وD=3. المجموعات هي S[A]={1,2,3} وS[B]={1,2} وS[C]={1,2,3} وS[D]={1,3}. تختلف على كل حافة، فتنجح ثلاثة ألوان.

تتساوى S[A] وS[C]، لكن A وC غير متجاورين، فلا يطلب التعريف تمييزهما. ولو استعملنا اللونين بالتناوب حول C4، لتساوت مجموعات الجوار على الحواف وفشل التمييز؛ لذلك ثلاثة هي الأقل هنا.

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

مجموعات الألوان ليست جداول تكرار

على P4 ذي التعيين 1،2،1،2، يرى جوار B ألوان A B C، أي 1،2،1، ويرى جوار C ألوان B C D، أي 2،1،2.

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

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

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

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

التمييز المحلي يختلف عن عدد الألوان المحلي وعن التلوين الديناميكي

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

هذا هدف عدّ داخل الجوار؛ هدفنا أقل عدد ألوان في اللوحة كلها مع شرط اختلاف مجموعتي الجوار على الحافة. حتى لو تساوى عددا عناصر مجموعتين، قد تختلف أسماؤهما، كما في {1,2} و{2,3}.

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

التلوين الديناميكي بمعامل r تلوين صحيح يطلب عند كل رأس عددًا من ألوان الجيران لا يقل عن min(r,degree)، ويقلل عدد ألوان اللوحة. [4]

عند r=2 على P4، التعيين 1،2،3،1 ينجح: جيران B لونهما 1 و 3، وجيران C لونهما 2 و 1، ولكل طرف جار واحد. لكنه يفشل في التمييز المحلي على BC كما رأينا.

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

شواهد النماذج والحصر المقيد

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

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

راجعنا 26 نموذجًا بحصر جميع تقسيمات الرؤوس إلى فئات ألوان بعد تجاهل تبديلات أسماء اللوحة فقط. فحص آخر مستقل في طريقة الحصر جرب 2724766 تعيينًا بأسماء محددة لهذه النماذج، وأعاد حساب الجوار بمجموعات بتات ومقارنة مجموعات الألوان مباشرة.

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

أقل عدد للتمييز المحلي يساوي 1 في الرسم الخالي من الحواف، و 2 في تسعة رسوم، و 3 في 23، و 4 في 31؛ المجموع 64. والفحص ذو الأسماء المحددة جرب 16384 تعيينًا، منها 7108 صحيحة عاديًا و 4720 مميزة محليًا.

راجعنا شواهد الأقل، والأزواج المستثناة، والجوار المغلق الذي يشمل الذات. وعلى P4، حصر الأسماء من 1 إلى 3 لم يعط حلًا، ومع أربعة أسماء توجد 24 تعيينًا؛ وهي تبديلات الأسماء الأربعة المختلفة.

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

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