لكل رأس قائمة: لماذا لا يكفي أن يقبل الرسم لونين؟

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

لا تكفي قابلية التلوين العادي بلونين إذا كانت لكل رأس قائمة خاصة. على K2,4، القائمتان عند A وB هما{1,2} و{3,4}، وقوائم C وD وE وF هي{1,3} و{1,4} و{2,3} و{2,4}. كل اختيار للونَي المركزين يمنع ورقة كاملة، فلا حل لهذه القوائم. لكن أي ثلاث خيارات لكل رأس تضمن حلًا لهذا الرسم، فيكون العدد اللوني للقوائم 3 مقابل العادي 2.

• في التلوين الصحيح يختلف لون طرفي كل حافة. [2] وفي تلوين القوائم يجب أن ينتمي لون كل رأس إلى قائمة ألوانه المسموحة. [1] نموذجنا محدود وبسيط وغير موجه بلا حلقات أو أوزان، ورؤوسه غير فارغة؛ لكل رأس لون واحد.
• نقول إن الرسم k-choosable إذا أمكن تلوينه صحيحًا من كل تعيين قوائم فيه k ألوان لكل رأس؛ العدد اللوني للقوائم هو أقل k يضمن ذلك. [1] هنا k عدد الخيارات عند الرأس، لا عدد الألوان المستعملة في الرسم كله.
• في K2,4 نصل كلًّا من A وB إلى C وD وE وF، بلا AB ولا حواف بين الأوراق؛ الأقل العادي 2. قوائم المركزين{1,2} و{3,4} تعطي أربع اختيارات:1 مع 3 يمنع C ذات{1,3}، و 1 مع 4 يمنع D ذات{1,4}، و 2 مع 3 يمنع E ذات{2,3}، و 2 مع 4 يمنع F ذات{2,4}. مثال واحد من قوائم الحجم 2 بلا حل ينفي ضمان كل تلك القوائم.
• ومع أي قوائم من ثلاثة ألوان، نختار لون A ولون B من قائمتيهما لأنهما غير متجاورين. لكل ورقة ثلاثة خيارات يحجب المركزان منها اثنين على الأكثر، فتجد خيارًا؛ ولا تتعارض الأوراق. إذن الرسم قابل من كل قوائم الحجم 3، وعدده اللوني للقوائم 3. لا نقول إن كل قوائم الحجم 2 تفشل، أو إن الحل يستخدم ثلاثة ألوان إجمالًا.
• في P4 ذي AB BC CD والقوائم{1,2} و{1,3} و{1,3} و{1,2}، التوزيع 2 1 3 2 صالح ويحتاج 3 ألوان مستخدمة؛ كل لوحة عالمية من اثنين من{1,2,3} تفشل. مع ذلك، P4 قابل من كل قوائم الحجم 2: نلون A ثم B ثم C ثم D، وكل خطوة تحجب خيارًا واحدًا فقط. حجم القائمة وضمان الاختيار وعدد المستخدم أسئلة مختلفة.
• إضافة 5 إلى قائمة C وحدها تصلح قوائم K2,4 المذكورة بالشاهد A1 B3 C5 D4 E2 F2، ويحتاج هذا التعيين الجديد 5 ألوان مستخدمة؛ لا تصبح كل القوائم ثلاثية. حافة بقائمتين{1} و{1} بلا حل، و{1} و{2} صالحتان؛ قائمتان{1,2} و{3,4} صالحتان أيضًا. المعزول يلتزم قائمته، وقد تفرض قائمتا رأسين معزولين استعمال لونين، مع أن التلوين العادي لهما يحتاج لونًا واحدًا؛ والقائمة الفارغة تمنع الحل.
• راجعنا 64 رسمًا رباعيًا، ولكل منها 81 تعيين قوائم حجمها 2 من اللوحة{1,2,3}: المجموع 5184 حالة و 82944 تعيينًا كاملًا مسموحًا، منها 26160 صحيحًا. توجد 4869 حالة لها حل و 315 بلا حل؛1818 تحتاج 3 ألوان مستخدمة. اتفق الأقل مع بحث مستقل جرب 48210 تعيينات كاملة عبر مجموعات ألوان؛ التوزيع 1:45،2:3006،3:1818،بلا حل:315. هذا نطاق محدود، وK2,4 ذو ستة رؤوس خارجه.

القائمة تخص الرأس، لا الرسم كله

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

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

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

لا نختار لونًا لرأس من قائمة رأس آخر لمجرد أنه ظهر في الرسم. ولا نضيف لونًا إلى قائمته خلال الحل؛ تغيير القائمة يصنع مدخلًا جديدًا. لذلك قد تنفد خيارات رأس رغم وجود أسماء ألوان كثيرة في الاتحاد العام.

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

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

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

أربع اختيارات للمركزين تمنع ورقة في كل مرة

خذ A وB مركزين غير متجاورين، وC وD وE وF أوراقًا غير متجاورة فيما بينها. صل كل مركز بكل ورقة: AC AD AE AF BC BD BE BF. هذا هو K2,4 في مثالنا؛ كل ورقة تتصل بالمركزين فقط.

عاديًا يكفي إعطاء A وB اللون 1 وجميع الأوراق 2؛ كل حافة مختلفة الطرفين. وجود حافة يمنع لونًا واحدًا، فيكون الأقل العادي 2. اللوحة اليسرى في الصورة الرئيسية تعرض هذا التلوين دون قيود قوائم.

نفرض بدلًا من الحرية قوائم A:{1,2} وB:{3,4}، وC:{1,3} وD:{1,4} وE:{2,3} وF:{2,4}. كل قائمة فيها خياران مختلفان، لكن المركزين لا يملكان لونًا مشتركًا يسمح بإعطائهما اللون نفسه.

إذا اخترنا A1 وB3، فلا يبقى لـC لون: خيار 1 يتعارض مع A وخيار 3 مع B. وإذا اخترنا A1 وB4، تنفد خيارات D بالطريقة نفسها. لم نفترض ترتيبًا جشعًا للوصول إلى هذا العائق.

إذا اخترنا A2 وB3، تمنع الورقة E لأن قائمتها{2,3}. وإذا اخترنا A2 وB4، تمنع F ذات{2,4}. هذه كل اختيارات المركزين من قائمتيهما؛ استبعدنا الأربعة، فلا يوجد تلوين للقوائم المعطاة بأي اختيار آخر للأوراق.

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

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

ضمان كل قوائم من ثلاثة، لا تجربة قوائم واحدة

نقول إن الرسم k-choosable إذا أمكن تلوينه صحيحًا من كل تعيين قوائم فيه k ألوان لكل رأس؛ العدد اللوني للقوائم هو أقل k يضمن ذلك. [1] هنا k عدد الخيارات عند الرأس، لا عدد الألوان المستعملة في الرسم كله.

نثبت الضمان عند 3 لرسمنا دون حصر أسماء الألوان. أعطِ كل رأس أي قائمة من ثلاثة ألوان مختلفة، بأي تقاطعات بين القوائم. اختر لونًا من قائمة A ولونًا من قائمة B؛ لا توجد AB، فلا يتعارض اختيار المركزين حتى إذا كان اللون واحدًا.

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

الأوراق C وD وE وF لا تتجاور فيما بينها، فيجوز اختيارها مستقلًا بعد تثبيت المركزين. كل حافة تصل مركزًا بورقة تجنبت لونه؛ تحقق التلوين الصحيح من القوائم لجميع الرؤوس.

شمل البرهان أي قوائم حجمها 3، لا قوائم خاصة من لوحة محدودة ولا تجربة ناجحة واحدة. مع مثال الحجم 2 الفاشل صار العدد اللوني للقوائم 3، بينما الأقل العادي 2. ولهذا لا نستبدل عبارة «كل تعيين قوائم» بعبارة «وجدنا تعيينًا صالحًا».

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

ونفي الضمان عند 2 لا يلزم باختبار كل قوائم الخيارين؛ يكفي المثال المانع. في المقابل، إثبات الضمان عند 3 لا يثبت بمجرد أن نجحت قوائم واحدة؛ لذلك احتجنا الحجة التي تبقي خيارًا لكل ورقة.

خياران لكل رأس قد ينتجان ثلاثة ألوان مستخدمة

P4 على A B C D له AB BC CD. ضع القوائم A:{1,2} وB:{1,3} وC:{1,3} وD:{1,2}. التعيين 2 1 3 2 مسموح عند كل رأس، وكل حافة مختلفة الطرفين؛ استعملنا الألوان 1 و 2 و 3.

لا يمكن حل هذه القوائم باستعمال لونين عالميًا. اتحاد الخيارات{1,2,3}، فلا توجد لوحة ثنائية إلا{1,2} أو{1,3} أو{2,3}. اللون الواحد يفشل بسبب الحافة؛ سنستبعد اللوحات الثلاث.

مع{1,2} لا يملك B وC من قائمتيهما إلا 1، فيتساويان على BC. ومع{2,3} لا يملكان إلا 3، فتفشل BC أيضًا. هذان العائقان لا يتعلقان بلون الطرفين A وD.

مع{1,3} يجبر A وD على 1، لأنه الخيار الوحيد من قائمتيهما في هذه اللوحة. بعدها يجب أن يكون B3 لتجنب A1، وC3 لتجنب D1، فيتساويان على BC. استبعدنا كل لوحة من اثنين، فالشاهد الثلاثي يثبت أقل مستخدم 3 لهذه القوائم.

مع ذلك، المسار قابل للتلوين من أي قوائم حجمها 2: لون A بأي خيار، ثم اختر لـB خيارًا غير لون A، ولـC خيارًا غير لون B، ولـD خيارًا غير لون C. لكل رأس لاحق جار سابق واحد وخياران مختلفان، فيبقى خيار مسموح.

هذا برهان على كل قوائم الحجم 2 للمسار، وليس ضمانًا لاستعمال لونين عالميًا. ولا يكفي الحجم 1 لكل القوائم لأن إعطاء الجميع الخيار الوحيد 1 يفسد الحافة. إذن العدد اللوني للقوائم للمسار 2، بينما أقل مستخدم للقوائم المعروضة 3.

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

خيار إضافي في قائمة واحدة يصنع مدخلًا جديدًا

عد إلى قوائم K2,4 المانعة، وأضف 5 إلى قائمة C فقط، فتصير{1,3,5}. تبقى A:{1,2} وB:{3,4} وD:{1,4} وE:{2,3} وF:{2,4}. لم تصبح كل القوائم ذات ثلاثة خيارات.

اختر A1 وB3. صار لـC الخيار 5 خارج اللونين المحجوبين، فيأخذ C5. D لا يستطيع 1 فيأخذ 4، وE لا يستطيع 3 فيأخذ 2، وF يمكنه 2 أو 4؛ اختر F2.

حصلنا على A1 B3 C5 D4 E2 F2، وكل لون من قائمة صاحبه. الأوراق لا تتجاور، وكل واحدة تتجنب اللونين 1 و 3 عند المركزين، فتختلف أطراف الحواف الثماني. نجح المدخل المعدل، لا المدخل الأصلي.

بل أقل عدد مستخدم لهذا التعديل 5: اختيارات المركزين 1 مع 4 و 2 مع 3 و 2 مع 4 ما زالت تمنع D أو E أو F، إذ لم تتغير قوائمها. لذلك يفرض الحل A1 B3، ثم C5 وD4 وE2، فتظهر الألوان الخمسة جميعًا؛ خيار F لا يخفض العدد.

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

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

الحافة والمعزول والقائمة الفارغة تضبط السؤال

على الحافة AB، إذا كانت القائمتان{1} و{1}، يجبر الطرفان على اللون نفسه فلا حل. وإذا صارت قائمة B هي{2}، صار A1 B2 تلوينًا صحيحًا مسموحًا؛ لم تتغير الحافة، بل المدخل اللوني.

وإذا كانت A:{1,2} وB:{3,4}، فاختر A1 B3. القائمتان منفصلتان ولا يفسد ذلك صحة الحافة؛ لا نطلب أن يشترك الجيران في خيارات. الأقل المستخدم 2 بسبب الحافة رغم أن اتحاد الخيارات أربعة أسماء.

على رأسين معزولين A وB، القائمتان{1} و{2} تجبران استخدام لونين مختلفين، رغم أن التلوين العادي بلا قوائم يكفيه لون واحد. لا حافة تفرض الاختلاف هنا، وإنما عضوية اللون في القوائم.

الرسم بلا حواف قابل من كل قوائم الحجم 1: كل رأس يأخذ خياره الوحيد، ولا حافة تتعارض معها أي اختيارات. قد تكون الخيارات الوحيدة مختلفة عند الرؤوس، فيستعمل الحل عدة ألوان؛ لا يتناقض ذلك مع العدد اللوني للقوائم 1.

أما إذا كانت قائمة A فارغة وبقيت B:{1} على الرأسين المعزولين، فلا حل لأن A لا يملك خيارًا. عدم وجود الحواف لا يلغي طلب إعطاء كل رأس لونًا من قائمته؛ نسجل غياب الحل، لا عددًا مستخدمًا 0.

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

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

حصر لوحة محدودة لا يثبت الضمان لكل القوائم

ثبتنا A B C D والأزواج الممكنة AB AC AD BC BD CD، وأخذنا كل اختيار لإبقاء أو حذف الحواف الست، فصار لدينا 2^6=64 مدخلًا مسمى. لكل رأس ثلاث قوائم ممكنة من اللوحة{1,2,3}: {1,2} و{1,3} و{2,3}.

لكل رسم 3^4=81 تعيين قوائم على الرؤوس الأربعة، والمجموع 64×81=5184 حالة. ليست كل قوائم الخيارين الممكنة عبر جميع أسماء الألوان؛ هذا نطاق صريح من لوحة ثلاثة فقط.

داخل كل حالة جربنا جميع الاختيارات من القوائم، وعددها 2^4=16 تعيينًا كاملًا، فالمجموع 82944. منها 26160 تلوينًا صحيحًا مسموحًا. العدد الأول يحصي الاختيارات الكاملة، والثاني المقبول منها؛ لا يحصيان الرسوم ذات الحل.

توجد 4869 حالة لها حل و 315 بلا حل. حسب أقل عدد مستخدم، توجد 45 حالة تحتاج 1، و 3006 تحتاج 2، و 1818 تحتاج 3، و 315 لا تملك عددًا صالحًا. مجموعها 5184؛ وقد يملك المدخل عدة تلوينات صحيحة.

راجعنا الأقل بطريقة مستقلة: جربنا مجموعات ألوان من اتحاد الخيارات حسب حجمها، وداخل كل مجموعة اختيارات كل قائمة التي تنتمي إليها. نتوقف عند أول شاهد ثم أول حجم ناجح. بلغ مجموع التعيينات الكاملة المجربة 48210، واتفق الأقل أو غياب الحل في الحالات 5184.

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

الحصر لا يثبت أن رسمًا قابل من كل قوائم الحجم 2 مهما كانت أسماؤها. ضمان K2,4 عند 3 وبرهان المسار عند 2 حجتان عامتان منفصلتان، والمثال المانع لـK2,4 يستعمل ستة رؤوس ولوحة أربعة، خارج الحصر الرباعي.

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