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

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

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

• نلون الرؤوس تلوينًا صحيحًا، ثم نطلب اختلاف مجموعتي ألوان الجيران لكل رأسين لهما اللون نفسه، ونقلل عدد الألوان المستخدمة؛ الجوار هنا مفتوح ويستثني الرأس نفسه. [1]
• إذا كان المركز A والأوراق B C D، فجار كل ورقة هو A وحده. أي ورقتين باللون نفسه ستريان مجموعة الألوان نفسها؛ لذلك تختلف ألوان الأوراق، ويحتاج المركز لونًا رابعًا.
• للأعداد الصحيحة الموجبة، الحجة تعطي النجمة ذات t أوراق t+1 لونًا، والرسم الكامل ثنائي الأجزاء Kp,q يحتاج p+q. وفي رسم بلا حواف، كل الرؤوس معزولة وجوارها فارغ، فتحتاج أسماء مختلفة بعدد الرؤوس.
• المعزولان يحتاجان لونين مختلفين بينهما، لكن المعزول قد يستعمل لون رأس غير معزول؛ المثلث مع معزولين يحتاج ثلاثة ألوان، لا خمسة، لأن مجموعة ألوان جيران المعزول فارغة وغير المعزول غير فارغة.
• على P4، ثلاثة ألوان تكفي هنا مقابل أربعة للتمييز المحلي؛ وعلى C4، نحتاج أربعة هنا مقابل ثلاثة هناك. التمييز المحلي يقارن جوارين مغلقين لرأسين متجاورين، بينما هنا نقارن الجيران لرأسين لهما اللون نفسه. [3]
• نقارن أسماء الألوان المختلفة، لا تكراراتها ولا ترتيبها؛ وهناك تحديد آخر يميز الرأسين من المسافات إلى فئات الألوان، وهو تعريف مختلف عن مجموعات ألوان الجيران. [4]
• راجعنا 26 نموذجًا و 64 رسمًا من أربعة رؤوس. في هذا الحصر، الأقل 2 في ستة رسوم، و 3 في 43، و 4 في 15. إعطاء كل رأس لونًا خاصًا يضمن وجود حل، لكن لا يثبت أنه الأقل.

المقارنة بين رأسين لهما اللون نفسه، والجوار يستثني الذات

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

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

نكتب N[A] لمجموعة جيران A، دون A نفسه، ونكتب T[A] لمجموعة الألوان المختلفة عند هؤلاء الجيران. هذا جوار مفتوح؛ الرأس المعزول له N[A]={} وT[A]={}. [1]

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

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

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

المركز A والأوراق B C D: كل ورقة ترى {1}

الحواف هي AB AC AD فقط. أعط المركز A اللون 1، والأوراق B C D اللون 2. هذا تلوين عادي صحيح: طرفا كل حافة مختلفان.

جيران A هم B C D، فتكون T[A]={2}. أما كل ورقة فجارها الوحيد A باللون 1، فتكون T[B]=T[C]=T[D]={1}.

الأوراق B وC لهما اللون 2 ومجموعة الجيران الملونة نفسها {1}؛ فلا ينجح تحديدهما. يفشل أيضًا الزوج B D والزوج C D. هذه أزواج أوراق لفحص الشرط، وليست حواف في النجمة.

لا ينقذ الحل أن تقول إن الورقة B عند موضع مختلف في الصورة عن C. القيد يفحص ألوان الجيران في الرسم، لا المسافة على الورقة أو أسماء الرؤوس أو اتجاه الرسم.

أعط A=1 وB=2 وC=3 وD=4. تصبح T[A]={2,3,4}، وتظل T[B]=T[C]=T[D]={1}. ومع ذلك ينجح التعيين: الأوراق مختلفة الألوان، فلا نطلب تمييز مجموعاتها عن بعضها.

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

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

تساوي مجموعتي الجيران يفرض اختلاف اللونين

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

هذا تساوٍ في الجوار المفتوح، ولا نستثني الزوج بسببه من شرط تحديد الجيران. إنه سبب لفرض اسمين مختلفين عند الرأسين، بخلاف الاستثناء في التمييز المحلي للجوار المغلق. [3]

كل أوراق النجمة ذات t أوراق لها الجوار نفسه، وهو المركز. تحتاج الأوراق t أسماء مختلفة، ويحتاج المركز اسمًا آخر بحكم الحواف؛ الأقل t+1 لأي t صحيح موجب.

في Kp,q، كل رؤوس الجزء الأول لها الجيران أنفسهم، وهم رؤوس الجزء الثاني؛ لذلك تحتاج p أسماء مختلفة. وبالمثل يحتاج الجزء الثاني q أسماء مختلفة.

كل رأس في الجزء الأول متجاور مع كل رأس في الثاني، فلا يعاد استعمال اسم بين الجزأين. نحتاج p+q أسماء، وتحققها الأسماء الخاصة لكل رأس. نفترض p وq موجبين.

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

المعزولون يختلفون فيما بينهم، ويمكنهم استعمال ألوان غير المعزولين

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

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

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

خذ مثلث A B C ومعزولين D وE. لون A=1 وB=2 وC=3، ثم D=1 وE=2. لا توجد حافة من معزول إلى أي رأس، ولا يشترك المعزولان في لون.

الزوج A D له اللون 1، لكن T[A]={2,3} وT[D]={}. والزوج B E له اللون 2، لكن T[B]={1,3} وT[E]={}. تختلف المجموعتان في الزوجين، فيصح التعيين بثلاثة أسماء.

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

P4 وC4 يوضحان الفرق عن التمييز المحلي

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

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

على P4 بالحواف AB BC CD، اختر A=1 وB=2 وC=3 وD=1. الزوج الوحيد ذو اللون المكرر هو A D؛ مجموعة الجيران الملونة عند A هي {2} وعند D {3}، فتختلفان ويصح تحديد الجيران.

لونان على P4 سيجعلان طرفي كل فئة يشتركان في مجموعة ألوان الجيران نفسها تحت التناوب، فلا يكفيان. إذن ثلاثة هي الأقل هنا. أما التعيين 1،2،3،1 نفسه، فيفشل في التمييز المحلي على BC لأن مجموعتي جوارهما المغلق متساويتان {1,2,3}؛ وبرهان الأقل هناك يفرض أربعة.

على C4 بالحواف AB BC CD AD، التعيين A=1 وB=2 وC=1 وD=3 ينجح في التمييز المحلي: مجموعات الجوار المغلق تختلف على كل حافة، وتساوي مجموعتي A وC مسموح لأنهما غير متجاورين.

لكنه يفشل هنا: A وC لهما اللون 1 والجيران أنفسهم {B,D}، فتكون T[A]=T[C]={2,3}. ولكل زوج متقابل في C4 الجيران أنفسهم، فيلزم اختلاف لونيه، وتفرض الحواف اختلاف بقية الأزواج؛ لذلك تحتاج أربعة أسماء.

إذن P4 تعطي ثلاثة هنا وأربعة هناك، وC4 تعطي أربعة هنا وثلاثة هناك. المثالان يمنعان الادعاء بأن أحد العددين أصغر من الآخر دائمًا؛ لا تنقل جواب أحد التعريفين إلى الآخر.

أسماء الجيران المختلفة لا عدد مرات ظهورها ولا مسافات الوصول

نستخرج T[A] بحذف تكرار الأسماء من ألوان الجيران. إذا ظهر الاسم 2 عند ثلاثة جيران، كان في المجموعة مرة واحدة، تمامًا كما لو ظهر عند جار واحد.

مجموعتا {2,3} و{3,2} متساويتان؛ ترتيب كتابة الأسماء لا يميز الرأسين. ومجموعتا {2,3} و{2,4} مختلفتان رغم أن لكل منهما اسمين؛ عد الأسماء وحده لا يكفي للمقارنة.

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

يوجد أيضًا تلوين محدد بالمسافات: يشترط، لكل رأسين في فئة لون واحدة، وجود فئة ألوان تختلف المسافة إليها بين الرأسين، ويقلل عدد الألوان. [4]

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

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

الحصر يراجع الشواهد، والبرهان يثبت الأقل

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

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

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

في أربعة رؤوس، ست حواف ممكنة تعطي 64 رسمًا مسمى. بين جميع تقسيمات الألوان عبر هذه الرسوم، هناك 337 تلوينًا عاديًا صحيحًا و 220 محددًا بالجيران. الأقل 2 في ستة رسوم، و 3 في 43، و 4 في 15؛ المجموع 64.

الفحص ذو الأسماء المحددة جرب 16384 تعيينًا، منها 7108 صحيحة عاديًا و 5136 محددة بالجيران. هذه أعداد تعيينات، وليست عدد الرسوم أو أزمنة تنفيذ.

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

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

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