غابة لكل لون: لماذا تقبل الشجرة لونًا واحدًا؟

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

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

• تقسيم الرؤوس إلى غابات يعني توزيعها على مجموعات، تستحث كل منها غابة؛ والعدد المطلوب أقل عدد مجموعات يحقق ذلك. [1] نسمي المجموعة فئة لون، ونأخذ جميع الحواف الأصلية بين رؤوسها. نعمل على رسم محدود وبسيط وغير موجه وغير فارغ الرؤوس. نلون كل رأس، حتى المعزول، ونقلل عدد الألوان المستعملة؛ أسماؤها قابلة للتبديل. الغابة قد تكون غير متصلة، ولا نحذف حافة أصلية داخل فئة لتصحيحها.
• لون واحد ينجح إذا وفقط إذا كان الرسم الأصلي غابة. P4 بالحواف AB BC CD يقبل 1111 بأقل 1، والنجمتان بثلاث وخمس أوراق تقبلان الجميع بلون 1؛ تفرع الدرجة 3 أو 5 لا يصنع دورة. حافة ومعزولان، وحافتان منفصلتان، والخالي من الحواف تقبل لونًا واحدًا أيضًا، لا 0.
• C4 بلون واحد يفشل لدورة A B C D A؛ 1122 ينجح بأقل 2، إذ تصبح فئتا اللون الحافتين AB وCD. C6 بالشاهد 111222 ينجح بأقل 2: فئتا اللون طريقا ABC وDEF. 112233 ينجح لكنه يستعمل 3 فلا يثبت الأقل. C5 بالشاهد 11222 تحتاج 2، والمثلث 112 يحتاج 2؛ كل دورة تستبعد اللون الواحد.
• التلوين الصحيح العادي يفرض اختلاف لون طرفي كل حافة، ويبحث عن أقل عدد ألوان. [2] تقسيم الرؤوس إلى غابات يسمح بحافة بين رأسين من اللون نفسه، ويمنع دورة كاملة بذلك اللون. P4 يحتاج 2 صحيحًا و 1 لغابات اللون. التلوين اللادوري يفرض تلوينًا صحيحًا للرؤوس، وغابة في اتحاد كل زوج ألوان. [3] هنا نفحص كل لون منفردًا ونسمح بالحواف داخله؛ هذان سؤالان مختلفان. C4 وC6 تحتاجان 3 لادوريًا و 2 لغابات اللون. في التلوين ذي العيب d، لا تتجاوز درجة أي رأس داخل مكونه أحادي اللون d. [4] عند d=1 لا يبقى في المكون إلا رأس منفرد أو حافة؛ أما غابة اللون فقد تتفرع بدرجة أكبر. P4 بلون واحد غابة صالحة، لكن رأسا وسطه بدرجة 2 فيفشل للعيب 1. كل تلوين صحيح أو ذو عيب 1 يحقق غابات اللون، ولا يلزم العكس.
• في الرسم الكامل K_n، أي ثلاثة رؤوس من لون واحد تصنع مثلثًا؛ كل فئة تسع اثنين فقط. الأقل ceil(n/2)، أي تقريب نصف n إلى أعلى عدد صحيح. K4 يقبل 1122 بأقل 2، وK5 يقبل 11223 وK6 يقبل 112233 بأقل 3. تجميع الرؤوس أزواجًا يعطي هذا الحد الأعلى لأي رسم بسيط، لكنه لا يفرض حجم 2 على كل فئة في الرسوم الأخرى؛ الشجرة كلها فئة كبيرة صالحة.
• P5 وP6 تحتاجان 1؛ الماسة 1122 تحتاج 2 بسبب مثلثها، وK2,3 وK3,3 تحتاجان 2 بسبب دورة رباعية، مع تلوين كل جانب بلون واحد. في تقسيم الحواف تتبع كل حافة مجموعة وقد تشترك المجموعات في الرأس؛ هنا يتبع كل رأس فئة واحدة، وتدخل كل حواف الفئة الأصلية فيها.
• حصر 64 رسمًا رباعيًا أعطى 960 تقسيمًا: 902 لغابات اللون، 337 صحيحًا، 778 للعيب 1، 334 لادوريًا، 322 نجميًا. الأقل 1 في 38 غابة و 2 في 26 رسمًا دوريًا؛ بحث الأقل جرب 126 تعيينًا كاملًا. قل عن الصحيح في 60 وعن العيب 1 في 28 وعن اللادوري في 63. فحص مكونات كل لون بعدد حواف يساوي الرؤوس ناقص 1 اتفق مع فحص الدورات في 18 مثالًا و 64 رسمًا والقوائم الكاملة للأقل. النطاق محدود، ومولد التقسيمات مشترك؛ K5 تحتاج 3 خارج الحصر.

نقسم الرؤوس ونبقي حواف كل فئة كلها

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

التلوين الصحيح العادي يفرض اختلاف لون طرفي كل حافة، ويبحث عن أقل عدد ألوان. [2] تقسيم الرؤوس إلى غابات يسمح بحافة بين رأسين من اللون نفسه، ويمنع دورة كاملة بذلك اللون.

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

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

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

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

الشجرة كلها بلون واحد، ولو تفرعت بخمس أوراق

خذ P4 على الرؤوس A B C D، والحواف AB BC CD فقط. التعيين 1111 يجعل فئة اللون 1 طريقًا كاملًا؛ لا دورة فيه، فينجح بلون واحد. لا يمكن النزول إلى صفر لأن الرؤوس كلها يجب أن تحمل لونًا.

عند B وC جارَان من اللون نفسه، وهذا مسموح هنا. لا نحتاج إلى قطع الطريق إلى حواف منفصلة، ولا إلى تبديل لون كل رأس تالٍ كما يفعل التلوين الصحيح.

خذ النجمة AB AC AD. إعطاء A وB وC وD اللون 1 يترك نجمة بلا دورة، فتنجح بأقل 1، رغم أن A له ثلاثة جيران من لونه. في نجمة AB AC AD AE AF يظل اللون الواحد صالحًا، ودرجة A داخل الفئة 5.

السبب عام: لون واحد يجعل الفئة كل رؤوس الرسم وكل حوافه. ينجح إذن إذا وفقط إذا كان الرسم الأصلي غابة. وجود حافة لا يمنع اللون الواحد، بينما وجود دورة يمنعه.

الحافتان المنفصلتان AB وCD تقبلان 1111: للفئة مكونان، وكل منهما حافة. حافة AB مع معزولين C وD تقبل 1111 أيضًا. إذا لم توجد حواف، يقبل الجميع اللون 1؛ المعزول ملون، ولا تصبح الإجابة 0.

الدورة تحتاج الثاني، ولا يلزم حذف حواف منها

في C4، الحواف AB BC CD AD. التعيين 1111 يفشل لأن الدورة كلها داخل فئة واحدة. جرب 1122 على A B C D: فئة 1 تضم AB، وفئة 2 تضم CD، وكل منهما حافة بلا دورة.

الحافتان BC وAD تصلان بين لونين مختلفين، فلا تدخلان في رسم لون منفرد. لم نحذفهما من الرسم الأصلي. الشاهد يثبت أن لونين يكفيان، والدورة تستبعد الواحد، فيكون الأقل 2.

التناوب 1212 ينجح لغابات اللون أيضًا: فئتا اللون مستقلتان بلا حواف. لكن 1122 يوضح السماح بحافة داخل الفئة، وهو تعيين غير صحيح بالمعنى العادي لأن AB وCD لهما طرفان متفقا اللون.

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

التعيين 112233 ناجح على C6، لكنه يستعمل ثلاثة ألوان؛ لا نسمّيه شاهدًا للأقل. شاهد 111222 هو الذي يحقق الحد الأدنى 2، كما يبين أن مكونًا أحادي اللون يمكن أن يملك درجة 2.

في C5 بالشاهد 11222، فئة 1 الحافة AB، وفئة 2 طريق C D E. ينجح بأقل 2، ولو أن التلوين الصحيح للدورة الفردية يحتاج 3. وفي المثلث ABC، التعيين 112 يجعل فئة 1 حافة AB وفئة 2 رأس C؛ الأقل 2 لأن اللون الواحد يغلق مثلثًا.

غابة اللون ليست شرط الغابة لكل زوج ألوان

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

في التلوين ذي العيب d، لا تتجاوز درجة أي رأس داخل مكونه أحادي اللون d. [4] عند d=1 لا يبقى في المكون إلا رأس منفرد أو حافة؛ أما غابة اللون فقد تتفرع بدرجة أكبر.

على C4، التلوين الصحيح بلونين يفرض 1212، واتحاد اللونين يعيد الدورة؛ لذلك يفشل لادوريًا. الشاهد 1213 صحيح، واتحاد أي زوج غابة، فيثبت الأقل اللادوري 3. لكن تقسيم الرؤوس إلى غابات يقبل 1122 بلونين.

على C6، التناوب 121212 صحيح لكنه يترك دورة في اتحاد اللونين. الشاهد 121213 ينجح لادوريًا بثلاثة: زوج 1 و 2 طريق A B C D E، وزوج 1 و 3 طريق A F E مع C معزول، وزوج 2 و 3 بلا حواف. غابات اللون تقبل 111222 بأقل 2.

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

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

أما P4 بلون واحد فغابة، لكنه يفشل للعيب 1 عند B وC. الشاهد 1122 يحقق العيب 1 بأقل 2؛ مكونا اللون حافتان. والنجمة بثلاث أو خمس أوراق تقبل 1 لغابات اللون، بينما العيب 1 والتلوين الصحيح يحتاجان 2، بالشاهد ذي لون مختلف للمركز عن الأوراق.

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

K5 تحتاج ثلاث فئات، والأزواج تعطي حدًا عامًا

في الرسم الكامل K_n، تتصل كل مجموعة من ثلاثة رؤوس بمثلث. لو أخذ لون واحد ثلاثة رؤوس، ظهر المثلث داخل فئته. لذلك لا تتسع أي فئة لأكثر من رأسين في هذا الرسم.

يلزم إذن عدد فئات لا يقل عن ceil(n/2)، حيث ceil تعني التقريب إلى أعلى عدد صحيح. تجميع الرؤوس أزواجًا، مع رأس منفرد إن كان العدد فرديًا، يحقق الحد: فئة الزوج حافة، وفئة المنفرد رأس.

K4 بالشاهد 1122 يحتاج 2؛ اللون الواحد يفشل بسبب مثلث، وفئتا الزوج تنجحان. K5 بالشاهد 11223 يحتاج 3: لونان لا يستوعبان أكثر من أربعة رؤوس إذا كانت كل فئة تسع اثنين. K6 بالشاهد 112233 يحتاج 3 بالسبب نفسه.

البناء بالأزواج يصلح لأي رسم بسيط على n رؤوس: فئة ذات رأسين لا تضم إلا حافة واحدة أو لا حواف، وكلاهما غابة. يعطي ceil(n/2) حدًا أعلى، لكنه لا يثبت أنه الأقل في كل رسم.

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

مسارات وماسة ورسم ثنائي: الشاهد ثم استبعاد الأصغر

P5 وP6 مساران بلا دورة، فيقبل كل منهما اللون 1 لجميع الرؤوس بأقل 1. الماسة ذات الحواف AB AC AD BC BD تقبل 1122: فئة 1 الحافة AB، وفئة 2 رأسا C وD بلا حافة. المثلث ABC يستبعد الواحد، فيكون الأقل 2.

في K2,3، أعط A وB اللون 1، وC وD وE اللون 2؛ حواف الرسم كلها بين الجانبين، فلا حواف داخل الفئتين. دورة A C B D A موجودة، فتمنع اللون الواحد؛ الأقل 2.

في K3,3، أعط A B C اللون 1، وD E F اللون 2. الفئتان مستقلتان، ودورة A D B E A تستبعد الواحد؛ الأقل 2 أيضًا. لا يمنع كثرة حواف الاتحاد نجاح الفئتين، لأننا نفحص كل لون وحده.

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

افحص كل فئة باستعمال قائمة الرؤوس والحواف الأصلية، لا شكل الخطوط في الرسم فقط. التقاطع البصري بين خطين ليس رأسًا جديدًا. انتبه أيضًا إلى فرق النجاح والأقل: 112233 على C6 ناجح، لكنه يزيد لونًا على 111222.

ثمان وثلاثون غابة بين أربعة رؤوس مسماة

ثبتنا A B C D والحواف المحتملة AB AC AD BC BD CD. إبقاء أو حذف كل حافة يعطي 2^6=64 رسمًا مسمى. لكل رسم 15 تقسيمًا للرؤوس بعد تجاهل إعادة أسماء الألوان؛ المجموع 960.

نجح 902 تقسيمًا لغابات اللون، و 337 للتلوين الصحيح، و 778 للعيب 1، و 334 للادوري، و 322 للنجمي. بحث الأقل بزيادة عدد الألوان جرب 126 تعيينًا كاملًا حتى أول نجاح في كل رسم. هذه أعداد تعيينات، وليست أزمنة تنفيذ.

الأقل 1 في 38 رسمًا، وهي الغابات: رسم بلا حواف، وستة بحافة، وخمسة عشر بحافتين، وست عشرة شجرة بثلاث حواف. الأشجار الأخيرة اثنا عشر طريقًا P4 وأربع نجوم بثلاث أوراق.

أي حافتين لا تصنعان دورة في رسم بسيط، لذا تدخل الرسوم الخمسة عشر كلها. الأشجار المسماة تعد هنا باثني عشر ترتيب طريق بعد تجاهل اتجاهه، وأربعة اختيارات لمركز النجمة. المجموع 1+6+15+16=38.

الرسوم الستة والعشرون الباقية تحتوي دورة، فتستبعد اللون الواحد. وكل رسم على أربعة رؤوس يقبل تقسيمًا إلى زوجين؛ كلا الفئتين غابة. لذلك أقلها 2. قل العدد عن الصحيح في 60 رسمًا، وعن العيب 1 في 28، وعن اللادوري في 63.

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

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

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