تلوين يرى فيه كل رأس بقية الألوان: متى يغيب الحل؟

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

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

• التلوين الصحيح يختلف عند طرفي كل حافة. [2] وشرط Fall coloring يطلب أن يحتوي جوار كل رأس المغلق جميع الألوان؛ نسجل مجموعة الأعداد الموجبة الممكنة. [1] الجوار المغلق هو الرأس وجيرانه، أي إن الجيران يظهرون كل الألوان الأخرى. نموذجنا محدود وبسيط وغير موجه، بلا حلقات أو أوزان، ورؤوسه غير فارغة؛ نلون كل رأس مرة واحدة.
• نعد الألوان المستخدمة فعلًا، وكل فئة غير فارغة. عند كل رأس نراجع جيرانه المباشرين فقط، لا الرسم كله ولا الرؤوس الأبعد. فئات اللون مستقلة، وكل رأس خارج فئة يحتاج جارًا داخلها؛ قد يتكرر اللون عند عدة جيران، ما دام كل لون آخر موجودًا.
• مع k ألوان يحتاج كل رأس إلى k-1 جار على الأقل، فيكون k على الأكثر درجته زائد 1، وعلى الأكثر الدرجة الدنيا زائد 1 للرسم كله. اللون الواحد يفشل إذا وجدت حافة. في السداسية درجة كل رأس 2، وشاهدا اللونين والثلاثة صالحان، فتكون المجموعة {2,3} والأقل 2 والأكبر 3.
• في C5، اللونان يجبران التناوب الذي لا يغلق على دورة فردية. ومع ثلاثة، جارَا كل رأس يجب أن يحملا اللونين الآخرين، فتُجبر الرؤوس على 1 2 3 1 2؛ يرى A عند B وE اللون 2 فقط ويفتقد 3. الحد الأعلى 3 يستبعد الأكثر، فتكون المجموعة فارغة، وليس العدد الأقل 0.
• الرباعية تقبل 2 فقط؛ ثلاثة تفرض 1 2 3 1 وتفشل عند الإغلاق. المسار P5 والنجمة تقبلان 2 فقط بسبب الورقة ذات الدرجة 1. ظهور كل زوج في الرسم لا يكفي لرؤية كل رأس بقية الألوان: شاهد P5 الكامل 1 2 3 1 2 يترك A دون جار لونه 3، رغم أن الأزواج الثلاثة موجودة.
• مع AB ورأس معزول يتعذر الشرط: الحافة تحتاج لونين، والمعزول لا يرى إلا نفسه فيفرض لونًا واحدًا. حافتان منفصلتان تقبلان 2، والرؤوس دون حواف تقبل 1؛ لا نترك المعزول بلا لون. المثلث والماسة يقبلان 3، والكامل K4 يقبل 4؛ كل مجموعة هنا تخص الرسم المحدد.
• حصرنا 64 رسمًا رباعيًا:960 تقسيمًا و 337 تلوينًا صحيحًا و 33 يحقق الشرط، موزعة على 30 رسمًا له حل و 34 بلا حل. اتفق فحص ألوان الجوار والفئات في 960 حالة، وراجع البحث المستقل الأعداد الممكنة بتجربة 921 تعيينًا مسمى كاملًا. التوزيع: واحد مجموعته {1}، و 22 مجموعتها {2}، وستة {3}، وواحد {4}؛ C5 وC6 وP5 خارج الحصر.

كل رأس مطلوب، والجوار المغلق يشمله

التلوين الصحيح للرؤوس يجعل طرفي كل حافة مختلفين. [2] وفي Fall coloring يرى كل رأس جميع الألوان في جواره المغلق؛ نسجل الأعداد الموجبة التي تسمح بهذا التلوين في مجموعة. [1]

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

الجوار المباشر لرأس يضم جيرانه الذين تصلهم به حافة. والجوار المغلق يضيف الرأس نفسه إليهم. عند A في السداسية A-B-C-D-E-F-A، الجيران B وF، والجوار المغلق A B F فقط؛ لا نضيف C لأنه على بعد خطوتين.

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

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

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

الدرجة الدنيا تعطي حدًا لكل لوحة ممكنة

لو استعملنا k ألوان، احتاج كل رأس إلى جار لكل واحد من الألوان الأخرى k-1. الجار الواحد لا يحمل لونين، فتحتاج هذه المهمة إلى k-1 جيران على الأقل. لذلك k لا يتجاوز درجة ذلك الرأس زائد 1.

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

الألوان المعدودة مستخدمة فعلًا، وكل فئة غير فارغة. إضافة اسم لون إلى المفتاح دون أن يحمله رأس لا تكبر اللوحة، ولا تسمح لنا بحذف طلب رؤية لون مستخدم بعيدًا عن رأس معين.

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

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

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

السداسية ترى كل الألوان بلونين وبثلاثة

السداسية على A B C D E F لها AB AF BC CD DE EF. لون الرؤوس بالترتيب 1 2 1 2 1 2. عند كل حافة يختلف الطرفان، وكل رأس يرى اللون الآخر عند جاريه، فينجح الشرط بلونين.

في هذا الشاهد، A لونه 1 وجاراه B وF باللون 2. يظهر في جواره المغلق اللونان 1 و 2. عند B ذي اللون 2 نجد A وC باللون 1؛ يتكرر هذا الفحص حول الدورة، دون أن نطلب اختلاف لوني الجارين عندما لا يوجد إلا لون آخر واحد.

جرب بدلًا من ذلك الرؤوس 1 2 3 1 2 3. عند A ذي اللون 1، الجاران B باللون 2 وF باللون 3. عند B ذي اللون 2 نجد A باللون 1 وC باللون 3. وعند C ذي اللون 3 نجد B باللون 2 وD باللون 1.

عند D نجد C باللون 3 وE باللون 2، وعند E نجد D باللون 1 وF باللون 3، وعند F نجد E باللون 2 وA باللون 1. جميع الرؤوس الستة ترى اللونين الآخرين، وكل حافة مختلفة عند طرفيها؛ إذن الشاهد الثلاثي صالح.

درجة كل رأس 2، فلا يمكن أكثر من 3، واللون الواحد يفشل بسبب الحواف. مع شاهدي 2 و 3، حددنا المجموعة كاملة{2,3}. أقل عدد صالح 2 وأكبر عدد صالح 3، لكن لا نحول وجودهما إلى ادعاء أن كل تلوين صحيح من ثلاثة ينجح.

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

الخماسية لا تملك أي عدد صالح لهذا الشرط

الخماسية A-B-C-D-E-A لها AB AE BC CD DE. درجة كل رأس 2، فيكون أي عدد ممكن على الأكثر 3. اللون الواحد يفشل بسبب الحافة؛ سنستبعد اللونين والثلاثة لنجزم بخلو المجموعة.

مع لونين، ابدأ A باللون 1. اختلاف الطرفين يجبر B باللون 2 وC باللون 1 وD باللون 2 وE باللون 1. لكن EA تصل رأسين باللون 1، فيفشل حتى التلوين الصحيح. تبديل أسماء اللونين يكرر العائق نفسه.

افترض ثلاثة ألوان تحقق الرؤية. ابدأ A باللون 1 وB باللون 2، بعد إعادة تسمية الألوان إن لزم. عند B يجب أن يكون الجاران A وC باللونين الآخرين، فيجبر C على 3. عند C يجبر B وD على 2 و 1، فيكون D باللون 1.

عند D يجب أن يرى 3 و 2؛ لذلك يكون E باللون 2. الآن عند A نجد الجارين B وE باللون 2 معًا، فيغيب 3 عن جواره المغلق. التوزيع 1 2 3 1 2 صحيح عاديًا، لكنه لا يحقق الرؤية.

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

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

للرباعية C4، التناوب 1 2 1 2 يحقق الرؤية بلونين. لو حاولنا ثلاثة، لفرض A1 B2 ثم C3 ثم D1، لكن DA تجعل طرفيها 1. وبحد الدرجة 2 نستبعد الأكثر؛ المجموعة {2} فقط. لا نعتمد على زوجية الدورة وحدها لإمكان ثلاثة.

فئات الألوان تفسر الفرق عن التلوين الكامل

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

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

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

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

خذ المسار P5 على A B C D E بحواف AB BC CD DE، ولون الرؤوس 1 2 3 1 2. تظهر الأزواج 12 و 23 و 13 و 12، فيكون التلوين صحيحًا كاملًا بثلاثة. لكن A لا يجاور إلا B ذات اللون 2، فيغيب 3 عنه؛ وE أيضًا لا يرى 3.

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

ورقتا المسار درجتهما 1 فتمنعان أكثر من 2 في شرط الرؤية، بينما التناوب 1 2 1 2 1 صحيح وكل رأس يرى اللون الآخر، فيثبت أن مجموعته {2}. المسار نفسه له أقل عادي 2 وأكبر كامل 3 وأقل متناغم 4؛ تختلف الأسئلة والقيود رغم ثبات الحواف.

المعزول والورقة والمثلث يضبطون الفحص

على A B C D مع AB وحدها، أعطِ A اللون 1 وB اللون 2 وC وD اللون 1. التلوين صحيح عاديًا، لكن C معزول وجواره المغلق C وحده، فلا يرى 2. وكذلك D. الصورة الداخلية اليمنى تعرض العناصر الأربعة والحافة الوحيدة دون إخفاء المعزولين.

ولا يمكن إصلاح الشرط بأي عدد آخر لهذا الرسم: الرأس المعزول درجته 0 فيفرض k على الأكثر 1، بينما AB تحتاج لونين مختلفين فيفرض k على الأقل 2. إذن المجموعة فارغة، لا {1} ولا {2}.

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

في النجمة AB AC AD، أعطِ المركز A اللون 1 والأوراق B وC وD اللون 2. كل ورقة ترى 1 عند جارها، والمركز يرى 2 عند أوراقه، فينجح اللونان. الورقة درجتها 1 تمنع أكثر من 2 والحواف تمنع 1؛ المجموعة {2}.

وفي الحافتين المنفصلتين AB وCD، التعيين A1 B2 C1 D2 يجعل كل رأس يرى الآخر عبر حافته الوحيدة. الدرجة الدنيا 1 والحواف تحددان المجموعة {2}. وجود مكون منفصل لا يمنع الشرط وحده؛ المعزول الذي لا يرى اللون الآخر هو الذي منع المثال السابق.

المثلث AB AC BC يقبل A1 B2 C3؛ كل رأس يرى اللونين الآخرين عند جاريه. التلوين الصحيح يحتاج 3، والدرجة الدنيا 2 تمنع الأكثر، فتكون المجموعة {3}.

الماسة هنا قائمة محددة على A B C D: AB AC AD BC BD دون CD. لونها A1 B2 C3 D3. عند A وB تظهر الفئتان الأخريان، وعند C وD نجد الجارين A وB باللونين 1 و 2. المثلث ABC يحتاج 3، والدرجة الدنيا 2 تمنع الأكثر؛ المجموعة {3}.

وعلى K4 بالحواف AB AC AD BC BD CD، كل رأس يجاور الثلاثة الآخرين. أربعة ألوان مختلفة صحيحة وكل رأس يرى البقية، والتلوين الصحيح يحتاج 4؛ المجموعة {4}. لا نضيف CD إلى الماسة ضمنيًا عند مقارنة المثالين.

الحصر يميز مجموعة فارغة من عدد ألوان صفر

ثبتنا A B C D والأزواج الممكنة AB AC AD BC BD CD، وأخذنا كل خيار إبقاء أو حذف للحواف الست. بلغ عدد القوائم 2^6=64، مع إبقاء الرؤوس الأربعة حتى إذا انعزل بعضها.

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

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

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

حسب مجموعة الأعداد الممكنة، يوجد رسم واحد مجموعته {1}، و 22 مجموعتها {2}، وستة مجموعتها {3}، وواحد مجموعته {4}، و 34 مجموعتها فارغة. المجموع 64؛ ليس توزيعًا على جميع الرسوم ذات خمسة أو ستة رؤوس.

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

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

في سجل المجموعة الفارغة نترك الأقل والأكبر غير محددين، ولا نحولهما إلى 0. حفظنا النماذج قبل البحث في المراجع، والصور من قوائمنا دون ادعاء ابتكار التعريف أو الأمثلة المعروفة. C5 وP5 بخمسة رؤوس وC6 بستة خارج الحصر الرباعي؛ براهين الدرجة والإغلاق وتكافؤ الفئات منفصلة عن الأعداد، ولا نستنتج صيغة عامة أو ضمان سرعة منها.