التلوين الكلي: لماذا تحتاج الرباعية أربعة ألوان والمثلث ثلاثة؟

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

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

• في التلوين الكلي تختلف ألوان الرؤوس المتجاورة، والحواف المتلاقية، وكل حافة ورأسي طرفيها؛ نبحث عن أقل عدد من الألوان المشتركة. [1] النموذج هنا محدود وبسيط وغير موجه، بلا حلقات أو أوزان، وله رؤوس غير فارغة؛ نلون كل عنصر مرة واحدة.
• عند رأس درجته d، يتعارض الرأس وحوافه المتصلة بعضها مع بعض، فيلزم d+1 لونًا على الأقل. وفي المثلث تتحقق الثلاثة: A باللون 1 وB باللون 2 وC باللون 3، والحواف AB باللون 3 وAC باللون 2 وBC باللون 1.
• في C4، مع ثلاثة ألوان تكون كل حافة مضطرة إلى اللون الثالث المختلف عن طرفيها. تساوي لون رأسين متقابلين يجعل حافتين متلاقيتين باللون نفسه؛ لذلك يجب اختلاف الرؤوس الأربعة، وهو مستحيل بثلاثة. التعيين المعروض بأربعة صالح ويثبت الأقل 4.
• يمكن تحويل المسألة إلى تلوين رؤوس رسم كلي: عنصر منفصل لكل رأس وحافة أصلية، وحواف للتعارض بين العناصر. [2] وفي كل فئة لون، الرؤوس مستقلة والحواف مطابقة ولا يمس رأس مختار حافة مختارة؛ ليس العدد مجموع حدين منفصلين لتلوين الرؤوس والحواف.
• تقبل C6 ثلاثة ألوان كلية بتكرار 1 و 2 و 3 على رؤوسها وألوان الحواف المحددة في الجسم. النجمة بثلاث حواف تحتاج أربعة مع رأس المركز، والمسار ذو ثلاث حواف يحتاج ثلاثة. زوجية الدورة وحدها لا تفسر فرق C4 وC6.
• الحافة الواحدة مع طرفيها تحتاج ثلاثة، ولو أضفنا رؤوسًا معزولة. وعلى أربعة رؤوس دون حواف نحتاج لونًا واحدًا ونملكه بتلوينها كلها 1؛ تختلف هذه الحالة عن تلوين الحواف وحدها الذي لا يجد عنصرًا ليلونه.
• حصرنا كل 64 رسمًا بسيطًا على أربعة أسماء:325869 تقسيمًا مرشحًا و 4145 تلوينًا صالحًا و 300 يحقق الأقل. احتاج رسم واحد لونًا واحدًا، و 37 رسمًا ثلاثة، و 25 رسمًا أربعة، ورسم واحد خمسة ألوان. تعذر حد الدرجة القصوى زائد 1 في 13 رسمًا. اتفق فحص التعارض والفئات في جميع المرشحات، وراجع البحث المستقل الأقل بزيارة 2162 عقدة، وهي عمل بحث لا عدد حلول؛ الحصر محدود وليس صيغة عامة.

لوحة واحدة وثلاثة أنواع من التعارض

التلوين الكلي يلون الرؤوس والحواف معًا، ويمنع تساوي اللون عند رأسين متجاورين أو حافتين متلاقيتين أو رأس وحافة متصلة به. العدد الكلي اللوني هو أقل عدد من الألوان التي تحقق ذلك. [1]

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

نستعمل الأرقام 1 و 2 و 3 و 4 أسماء للألوان؛ تغيير أسمائها معًا لا يغير التلوين. اللون 1 على دائرة رأس واللون 1 على خط حافة ينتميان إلى الفئة نفسها، فلا نفصل لوحة الرؤوس عن لوحة الحواف عند العد.

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

يجوز إعادة اللون بين رأس وحافة لا تمسه، ما دامت سائر القيود صحيحة. هذا ما سنراه بين A والحافة BC في المثلث؛ الحافة المقابلة بعيدة عن A، رغم وقوعها في الرسم نفسه.

المثلث يحقق ثلاثة بإعادة اللون على الحافة المقابلة

المثلث الكامل على A B C له الحواف AB AC BC. أعطِ A اللون 1 وB اللون 2 وC اللون 3. ثم أعطِ AB اللون 3 وAC اللون 2 وBC اللون 1. هذه قائمة العناصر الستة كاملة، لا تلوين للرؤوس مع ترك الخطوط دون ألوان.

الرؤوس الثلاثة متجاورة اثنين اثنين، وألوانها مختلفة. عند A تتلاقى AB ذات اللون 3 وAC ذات اللون 2، ويختلفان أيضًا عن لون A وهو 1. عند B نجد الحافتين 3 و 1 مع رأس لونه 2، وعند C نجد الحافتين 2 و 1 مع رأس لونه 3.

كل حافة تختلف عن طرفيها: AB لونها 3 وطرفاها 1 و 2، وAC لونها 2 وطرفاها 1 و 3، وBC لونها 1 وطرفاها 2 و 3. بذلك غطينا أنواع التعارض الثلاثة؛ لا نكتفي بفحص لون الرأسين وحده.

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

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

في المثلث، كل فئة لون تضم رأسًا والحافة المقابلة فقط. يمكن أن يشترك A وBC في 1 لأن A ليس طرفًا لـBC. طلب لون منفصل لكل رأس وحافة كان سيستهلك ستة بلا حاجة.

لماذا لا تكفي ثلاثة للدورة الرباعية؟

الرباعية على A B C D لها AB AD BC CD، أي الدورة A-B-C-D-A. درجة كل رأس 2، فيعطينا البرهان السابق حدًا أدنى 3. سنثبت أن الحد لا يكفي هنا بدل افتراض أن كل رأس بدرجة 2 يسمح بثلاثة.

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

إذا كان A وC باللون نفسه، فإن AB وBC لهما زوج ألوان الطرفين نفسه، ولذلك تأخذان اللون الثالث نفسه. لكنهما تتلاقيان عند B، فيخالف ذلك شرط اختلاف الحواف. إذن يجب أن يختلف A وC.

وبالمثل يجب أن يختلف B وD، لأن AB وAD كانتا ستأخذان اللون الثالث نفسه لو تساوى B وD. الرؤوس المتجاورة مختلفة أصلًا، وأضفنا اختلاف كل زوج متقابل؛ صارت الرؤوس الأربعة مختلفة اثنين اثنين. ثلاثة ألوان لا تستطيع ذلك.

هذا يستبعد جميع التلوينات بثلاثة في الرباعية، لا محاولة واحدة فقط. أما شاهد الأربعة فيعطي A اللون 1 وB اللون 2 وC اللون 3 وD اللون 4؛ وAB اللون 3 وAD اللون 2 وBC اللون 4 وCD اللون 1.

عند A الحافتان 3 و 2 مع رأس 1، وعند B الحافتان 3 و 4 مع رأس 2، وعند C الحافتان 4 و 1 مع رأس 3، وعند D الحافتان 2 و 1 مع رأس 4. في كل موضع ثلاثة ألوان مختلفة، وكل حافة مختلفة عن طرفيها. الشاهد صالح بأربعة، فيثبت الأقل 4.

الرؤوس وحدها تقبل A وC بلون 1 وB وD بلون 2، والحواف وحدها تقبل AB وCD بلون 1 وAD وBC بلون 2. لكن ضم هذين التعيينين باللوحة نفسها يفشل مثلًا بين A وAB. جمع التلوينين دون فحص التعارض الجديد لا ينتج شاهدًا كليًا.

افحص فئة اللون أو ابنِ رسم التعارض

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

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

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

الرسم الكلي يحول كل رأس وكل حافة من الأصل إلى رأس مستقل جديد، ويصل بين عنصرين عندما يكونان متجاورين أو متصلين في الأصل. [2] نحافظ على نوع العنصر حتى لا نخلط رأس A بعنصر الحافة AB.

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

على المثلث فئة 1 هي A وBC، وفئة 2 هي B وAC، وفئة 3 هي C وAB. لا تتصل عناصر أي فئة فيما بينها في رسم التعارض. أما تلوين الحواف النجمي أو القوي فيسأل عن قيود إضافية على الحواف وحدها؛ ليس فحص فئاتنا بديلًا عن تعريفهما.

السداسية والنجمة تضبطان الحد المحلي

الدورة A-B-C-D-E-F-A لها AB AF BC CD DE EF. لون رؤوسها بالترتيب 1 2 3 1 2 3، وأعطِ AB اللون 3 وAF اللون 2 وBC اللون 1 وCD اللون 2 وDE اللون 3 وEF اللون 1. تظهر العناصر الاثنا عشر في الصورة الداخلية كاملة.

كل حافة أخذت اللون الثالث المختلف عن طرفيها. وعند كل رأس تأخذ الحافتان اللونين الآخرين المختلفين عن لون الرأس: عند A الحافتان 3 و 2 والرأس 1، وعند B الحافتان 3 و 1 والرأس 2؛ يتكرر الفحص حول الدورة. إذن شاهد الثلاثة صالح.

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

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

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

وفي المسار A-B-C-D، أعطِ الرؤوس 3 1 2 3 والحواف AB اللون 2 وBC اللون 3 وCD اللون 1. تختلف أطراف كل حافة عنها، وعند B وC الحافتان والرأس بألوان مختلفة. درجة 2 تفرض ثلاثة وتتحقق بها، فلا يؤدي وجود أربعة رؤوس وحده إلى نتيجة الرباعية.

الرأس المعزول يبقى عنصرًا مطلوب التلوين

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

مع ذلك لم نترك C وD بلا لون. في التلوين الكلي كل رأس عنصر مطلوب، ولو كانت درجته 0. يمكن إعادة لون مستخدم عليه دون مخالفة لأنه لا يمس حافة ولا يجاور رأسًا.

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

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

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

حصر أربعة أسماء يفصل الحلول عن عمل البحث

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

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

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

بلغ مجموع التلوينات التي تحقق العدد الأقل 300. وكان توزيع المدخلات حسب أقل عدد: رسم واحد يحتاج 1، و 37 تحتاج 3، و 25 تحتاج 4، ورسم واحد يحتاج 5. مجموع المدخلات 64؛ هذه أعداد رسوم مختلفة، وليست فئات ألوان في رسم واحد.

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

راجعنا العدد الأقل ببحث مستقل في تعيينات ألوان مسماة، يحاول أعداد الألوان تصاعديًا حتى يظهر شاهد صالح. زار 2162 عقدة بحث إجمالًا عبر 64 مدخلًا واتفق مع أقل عدد المستخرج من التقسيمات.

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

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