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

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

تقبل الدورة الرباعية لونين لأن ألوان الرؤوس 1،1،1،2 تعطي مجموعات الجيران ⟨1,2⟩ و⟨1,1⟩ و⟨1,2⟩ و⟨1,1⟩ المختلفة عند كل طرفَي حافة، بينما اللون الواحد يعطي المجموعة نفسها للرؤوس الأربعة.

• نلون الرؤوس، ونسجل ألوان جيران كل رأس مع التكرار دون لونه الخاص؛ نقارن طرفَي الحواف فقط، ولا نفرض صحة التلوين، ونقلل عدد الألوان. [1]
• شاهد C4 هو A=1 وB=1 وC=1 وD=2؛ مجموعتا ⟨1,2⟩ و⟨1,1⟩ تتناوبان حول الدورة، فيثبت لونان مع فشل اللوحة الواحدة.
• الشاهد A=2 وB=1 وC=2 وD=3 ينجح بالتكرارات ⟨1,3⟩ و⟨2,2⟩، لكن جمع الأرقام يعطي 4 عند الجميع فيفشل؛ الرموز ليست أوزانًا عددية.
• يكفي لون واحد بالضبط عندما تختلف درجتا طرفَي كل حافة؛ لذلك ينجح P3 والنجمة بلون واحد، ولا تمنع المعزولات النجاح.
• كل تلوين صحيح للرؤوس يحقق تمييز مجموعات الجيران، فيثبت وجود حل لأي رسم، رغم أن بعض الشواهد المقبولة هنا غير صحيحة.
• في الرسم الكامل يحتاج كل رأس اسم لون مختلفًا، فيكون الحد n للرسم K_n؛ أما الحافة الوحيدة فتقبل لونين، والرسم غير الفارغ بلا حواف يحتاج لونًا واحدًا.
• وافق فحص كل التعيينات المسماة حصر الأنماط في 25 نموذجًا و 64 رسمًا من أربعة رؤوس؛ حدود رسوم الأربعة هي 1 في 17 حالة و 2 في 42 و 3 في 4 و 4 في حالة واحدة.

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

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

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

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

نكتب ⟨1,1,2⟩ لتسجيل اللون 1 مرتين واللون 2 مرة. ⟨2,1,1⟩ هي المجموعة نفسها؛ ترتيب العرض لا يدخل في التعريف، أما ⟨1,2,2⟩ فتختلف في التكرارات.

نطلب M[u]≠M[v] عندما تكون uv حافة أصلية. لا نقارن كل زوج مختلف، ولا نضيف حافة بين غير المتجاورين؛ لا يشترط أن يختلف اسم لون u عن اسم لون v.

الدورة الرباعية تقبل لونين رغم تساوي لونَي رأسين متجاورين

خذ دورة C4 بالرؤوس A B C D والحواف AB BC CD DA، وأعط A=1 وB=1 وC=1 وD=2.

جيران A هما B وD، فيكون M[A]=⟨1,2⟩. جيران B هما A وC، فيكون M[B]=⟨1,1⟩؛ احتفظنا بالاسم 1 مرتين لأن هناك جارَين يحملانه.

جيران C هما B وD، فيكون M[C]=⟨1,2⟩. جيران D هما A وC، فيكون M[D]=⟨1,1⟩، دون إدخال لون D الخاص في مجموعته.

كل حافة تصل بين ⟨1,2⟩ و⟨1,1⟩، فتنجح المقارنات الأربع. تساوي M[A] مع M[C]، وتساوي M[B] مع M[D]، مقبولان لأن AC وBD ليستا حافتين.

لو استعملنا اسم لون واحدًا، كان لكل رأس جارَان من اللون 1، فصارت المجموعات الأربع ⟨1,1⟩. تفشل الحواف كلها، فتستبعد اللوحة الواحدة ويثبت الشاهد أن الحد الأدنى لونان.

تساوي لونَي A وB، وتساوي لونَي B وC، يجعل هذا الشاهد غير صحيح بالمعنى المعتاد، لكنه يحقق شرط المجموعات المتعددة. جدول اللوحات يحصر جميع تعيينات ألوان الرؤوس؛ تحت لونين هناك 16 تعيينًا مسمى، ينجح منها 10 في خمسة أنماط أسماء.

جمع الأرقام أو تغيير نطاق المقارنة يبدل المسألة

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

في دورة C4 نفسها، خذ A=2 وB=1 وC=2 وD=3. تكون مجموعات الجيران ⟨1,3⟩ و⟨2,2⟩ و⟨1,3⟩ و⟨2,2⟩، فتختلف عند كل حافة.

لكن ⟨1,3⟩ و⟨2,2⟩ تعطيان المجموع العددي 4. تفشل المقارنات العددية الأربع، رغم نجاح المجموعات المتعددة؛ نتيجة شاهد واحد تحت قاعدة لا تنتقل إلى قاعدة أخرى.

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

حذف التكرار يعطي مجموعة عادية بدل المتعددة. المجموعة المتعددة تميز ⟨1,1,2⟩ عن ⟨1,2,2⟩، بينما مجموعة الأسماء في الحالتين هي {1,2}. هذا مثال على المعلومات التي يحذفها الاختزال، لا شاهد رسم إضافي غير محسوب.

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

لون واحد يكفي عندما تختلف درجتا طرفَي كل حافة

يسجل المصدر معيار اللون الواحد: يتحقق عندما تختلف درجة كل رأسين متجاورين. [1]

نبرهنه مباشرة: إذا كانت الرؤوس كلها باللون 1، تكون M[u] قائمة من الدرجة d[u] نسخ من الاسم 1. تتساوى مجموعتا طرفين إذا وفقط إذا تساوت درجتاهما.

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

في P3 ذي الحافتين AB BC، لون الرؤوس الثلاثة 1 يعطي M[A]=⟨1⟩ وM[B]=⟨1,1⟩ وM[C]=⟨1⟩. ينجح الزوجان AB وBC؛ تساوي الطرفين AC لا يضر لأنهما غير متجاورين.

في نجمة ذات مركز A وثلاث أوراق B C D، لون الجميع 1 يعطي مجموعة المركز ⟨1,1,1⟩ ومجموعة كل ورقة ⟨1⟩. تفشل صحة التلوين المعتادة، لكن المقارنات المطلوبة كلها ناجحة بلون واحد.

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

التلوين الصحيح يثبت وجود حل لأي رسم

تلوين الرؤوس الصحيح يشترط اختلاف لونَي الرأسين المتجاورين، ويحسب أقل لوحة تحقق هذا الشرط. [2]

افترض تلوينًا صحيحًا وخذ حافة uv. اسم اللون c[u] لا يظهر بين جيران u، لأن جميعهم يختلفون عنه في اللون، لكنه يظهر بين جيران v لأن u جار له.

إذن عدد مرات c[u] في M[u] هو صفر، وفي M[v] واحد على الأقل، فتختلف المجموعتان. ينطبق البرهان على كل حافة، فيكون كل تلوين صحيح شاهدًا مقبولًا هنا.

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

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

الحافة الوحيدة K2 تقبل A=1 وB=2، إذ M[A]=⟨2⟩ وM[B]=⟨1⟩. اللون الواحد يفشل لأن درجتي الطرفين متساويتان؛ لا تختلط هذه النتيجة بعائق الحافة الوحيدة عندما تكون الألوان على الحواف.

الرسم الكامل يحتاج أسماء مختلفة للرؤوس كلها

في الرسم الكامل K_n، كل رأس جار لجميع الرؤوس الأخرى. لتكن T المجموعة المتعددة لألوان الرؤوس كلها؛ نحصل على M[u] بحذف ظهور واحد لاسم لون u من T.

إذا كان c[u]=c[v]، حذفنا الاسم نفسه مرة في الحالتين، فتساوت M[u] وM[v]. لأن كل زوج مختلف متجاور، يفشل تعيين اللون نفسه لرأسين.

إذا اختلف الاسمان، اختلفت المجموعتان: عند اسم c[u] ينقص العدد في M[u] مرة، ولا ينقص في M[v]. لذلك تعطي الأسماء المختلفة للرؤوس كلها شاهدًا ناجحًا.

يثبت الاتجاهان أن الحد في K_n هو n للرسم غير الفارغ. عند n=1 لا توجد حافة، لكن الرأس نفسه يحتاج لونًا؛ وعند n=2 نحصل على نتيجة الحافة الوحيدة السابقة.

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

فحصان مستقلان يقارنان ألوان الجيران دون حذف الحالات غير الصحيحة

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

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

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

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

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

في رسوم الأربعة، يوجد 17 رسمًا حده 1 و 42 حده 2 و 4 حدها 3 ورسم واحد حده 4. كلها تقبل حلًا، بخلاف عوائق النموذج الذي يلون الحواف ويقارن الجميع.

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